lucius_fox's blog

By lucius_fox, history, 3 months ago, In English

In C, how do you prove that if no character appears more than floor(n/2) times, we can always achieve n%2 length of the final string? (where 'n' is the length of the given string) Please help.

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +22 Vote: I do not like it

Let

  • $$$n$$$ equal the current length of the string
  • $$$\mathrm{maxf}_1$$$ equal the current largest frequency of any character
  • $$$\mathrm{maxf}_2$$$ equal the current second largest frequency of any character.

First, notice that we can do some operation exactly when $$$\mathrm{maxf}_1 < n$$$.

Case 1: $$$n\equiv0\pmod{2}$$$

Claim: If $$$\mathrm{maxf}_1 \le n/2$$$ and $$$n > 0$$$, we can do an operation such that after the operation, $$$\mathrm{maxf}_1 \le n/2$$$.

Proof:

  • If $$$\mathrm{maxf}_1 < n/2$$$, we can do any operation. After the operation $$$n_{\mathrm{new}} = n-2$$$ and $$$n_{\mathrm{new}}/2 = (n-2)/2 = n/2-1$$$ and because $$$\mathrm{maxf}_1 < n/2$$$, then $$$\mathrm{maxf}_1 \le n/2-1 = n_{\mathrm{new}}/2$$$.
  • If $$$\mathrm{maxf}_1 = n/2$$$ and $$$\mathrm{maxf}_2 < n/2$$$, we can do one operation which decreases $$$\mathrm{maxf}_1$$$ by one. Now $$$\mathrm{maxf}_{1\mathrm{new}} = \mathrm{maxf}_1-1 = n/2-1 = n_{\mathrm{new}}/2$$$, meaning that $$$\mathrm{maxf}_{1\mathrm{new}} \le n_{\mathrm{new}}/2$$$. Similar to the previous case, $$$\mathrm{maxf}_2 \le n/2-1 = n_{\mathrm{new}}/2$$$.
  • If $$$\mathrm{maxf}_1 = n/2$$$ and $$$\mathrm{maxf}_2 = n/2$$$, we have $$$\mathrm{maxf}_1 + \mathrm{maxf}_2 = n$$$. This means that there are no other characters than those two, so we can delete one of each. Now $$$\mathrm{maxf}_{1\mathrm{new}} = \mathrm{maxf}_1-1 = \mathrm{maxf}_{2\mathrm{new}} = \mathrm{maxf}_2-1 = n/2-1 = n_{\mathrm{new}}/2$$$, meaning that $$$\mathrm{maxf}_{1\mathrm{new}} = \mathrm{maxf}_{2\mathrm{new}} \le n_{\mathrm{new}}/2$$$.

This means that if we have $$$\mathrm{maxf}_1 \le n/2$$$ and $$$\mathrm{maxf}_1 < n$$$, we can do an operation and keep the first condition satisfied. Thus, we can do operations while $$$n/2 < n\ \Leftrightarrow\ 0 < n/2\ \Leftrightarrow\ n > 0$$$. Thus we can always reach the state with $$$n = 0$$$. $$$\square$$$

Case 2: $$$n\equiv1\pmod{2}$$$

Claim: If $$$\mathrm{maxf}_1 \le \lceil n/2\rceil$$$ and $$$n > 1$$$, we can do an operation such that after the operation, $$$\mathrm{maxf}_1 \le \lceil n/2\rceil$$$.

Proof:

  • If $$$\mathrm{maxf}_1 < \lceil n/2\rceil$$$, we can do any operation. After the operation $$$n_{\mathrm{new}} = n-2$$$ and $$$\lceil n_{\mathrm{new}}/2\rceil = (n_{\mathrm{new}}+1)/2 = (n-2+1)/2 = (n+1)/2 - 1 = \lceil n/2\rceil-1$$$ and because $$$\mathrm{maxf}_1 < \lceil n/2\rceil$$$, then $$$\mathrm{maxf}_1 \le \lceil n/2\rceil-1 = \lceil n_{\mathrm{new}}/2\rceil$$$.
  • If $$$\mathrm{maxf}_1 = \lceil n/2\rceil$$$ and $$$\mathrm{maxf}_2 < \lceil n/2\rceil$$$, we can do one operation which decreases $$$\mathrm{maxf}_1$$$ by one. Now $$$\mathrm{maxf}_{1\mathrm{new}} = \mathrm{maxf}_1-1 = \lceil n/2\rceil-1 = \lceil n_{\mathrm{new}}/2\rceil$$$, meaning that $$$\mathrm{maxf}_{1\mathrm{new}} \le \lceil n_{\mathrm{new}}/2\rceil$$$. Similar to the previous case, $$$\mathrm{maxf}_2 \le \lceil n/2\rceil-1 = \lceil n_{\mathrm{new}}/2\rceil$$$.
  • Notice that the case with $$$\mathrm{maxf}_1 = \lceil n/2\rceil$$$ and $$$\mathrm{maxf}_2 = \lceil n/2\rceil$$$ doesn't exist as $$$\mathrm{maxf}_1 + \mathrm{maxf}_2 = 2\lceil n/2\rceil = 2(n+1)/2 = n+1 > n$$$, which is not possible.

This means that if we have $$$\mathrm{maxf}_1 \le \lceil n/2\rceil$$$ and $$$\mathrm{maxf}_1 < n$$$, we can do an operation and keep the first condition satisfied. Thus, we can do operations while $$$\lceil n/2\rceil < n\ \Leftrightarrow\ (n+1)/2 < n\ \Leftrightarrow\ n+1 < 2n\ \Leftrightarrow\ 1 < 2n-n\ \Leftrightarrow\ n > 1$$$. Thus we can always reach the state with $$$n = 1$$$. $$$\square$$$