Zaoly's blog

By Zaoly, history, 11 months ago, In English

A binary array is an array where all elements are either $$$0$$$ or $$$1$$$.

For any binary array $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$, we can figure out the corresponding unique array $$$b_1, b_2, \ldots, b_n$$$ of length $$$n$$$ that satisfies $$$b_1 = a_1$$$ and $$$b_i = a_i \oplus a_{i - 1}$$$ for any $$$2 \le i \le n$$$, where $$$\oplus$$$ denotes XOR operation. Then count the number of $$$1$$$-s in array $$$a$$$, count the number of $$$1$$$-s in array $$$b$$$, and find the minimum of them as the “score” of array $$$a$$$.

For example, provided $$$a = [1, 0, 1, 1, 0, 0]$$$, then $$$b = [1, 1, 1, 0, 1, 0]$$$. The number of $$$1$$$-s in array $$$a$$$ is $$$3$$$, the number of $$$1$$$-s in array $$$b$$$ is $$$4$$$, and the minimum of them is $$$3$$$, so the “score” of array $$$a = [1, 0, 1, 1, 0, 0]$$$ is $$$3$$$.

For any given $$$n$$$, what is the maximum “score” of array $$$a$$$ among all possible arrays $$$a$$$? And how to construct a possible array $$$a$$$?

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

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I believe the answer is $$$\lceil{\frac{n}{2}}\rceil$$$

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    this can be done with the array, $$$a = [1, 0, 1, 0, 1, \dots]$$$

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I don’t believe so. For $$$n = 4$$$, the answer is not $$$\big\lceil \frac n 2 \big\rceil = 2$$$ but $$$3$$$, because we can construct an array $$$a = [1, 0, 1, 1]$$$, where $$$b = [1, 1, 1, 0]$$$.

    • »
      »
      »
      11 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      My bad! Well now we have a lower bound for the answer. Also notice something: for the array $$$a = [1, 0, 1, 0, \dots], b = [1, 1, 1, 1, \dots]$$$ If we replace any 0 with a 1 in the array $$$a$$$, it will add 1 1 to the array $$$a$$$ and remove 2 (or 1) 1 from the array $$$b$$$. Hope that helps!

      • »
        »
        »
        »
        11 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        But what if we don’t make the values at odd indices $$$1$$$? That is, what if we don’t form our array like $$$a = [1, \texttt{X}, 1, \texttt{X}, \ldots]$$$? Such as, $$$a = [1, 1, 0, 0, 1, 1, 0, 0, \ldots]$$$ — just like when we move some $$$1$$$-valued elements to other positions.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Ww can get something around $$$2n/3$$$ with $$$a = [1, 1, 0, 1, 1, 0,\dots]$$$ and $$$b = [1, 0, 1, 1, 0, 1,\dots]$$$

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I bruteforced all possible sequences for $$$1 \le n \le 12$$$ and it looks like the maximum score is always $$$\lfloor \frac{2n+1}{3} \rfloor$$$. It is not hard to see that this score can be obtained by using the pattern $$$[1,0,1,1,0,1,1,0,1,\dots]$$$. Unfortunately I don't know how to prove these claims.

»
11 months ago, # |
Rev. 5   Vote: I like it +10 Vote: I do not like it

Consider having $$$x$$$ ones in array $$$a$$$.

First assume that $$$x \lt \frac{n}{2}$$$. Then, we can make a prefix of alternating zeros and ones, followed by a bunch of zeros. Then, array $$$b$$$ has something like $$$2x$$$ ones. Then the score is $$$\min(x,2x)=x$$$ (which is less than half $$$n$$$).

Now let's try $$$x \gt \frac{n}{2}$$$. Now, we can make $$$a$$$ have an alternating prefix and a suffix full of ones. The length of the alternating prefix is approximately $$$2n-2x$$$, so the score is $$$\min(x, 2n-2x)$$$, which is maximized when $$$x=2n-2x$$$ therefore $$$\text{score}=x=2n/3$$$.

I'm not being precise with my rounding and so on but you get the idea. Also, i didn't prove that this construction is optimal but it's very intuitive that the amount of ones in $$$b$$$ is maximized when we construct $$$a$$$ as described (again, sorry for lack of proof)

EDIT:

We can prove optimality by first proving an upper bound and then showing that my construction achieves it.

If there are more zeros than ones in $$$a$$$, you can only have at most $$$2x$$$ ones in $$$b$$$, because that's the amount of adjacent positions there can be next to a one.

On the other hand, if there are more ones than zeros in $$$a$$$, we are limited by the number of zeros, which is $$$n-x$$$, so there can be at most $$$2(n-x)$$$ ones in $$$b$$$. (same argument as above)

Note that the proposed construction reaches both bounds (trivial), so it must be optimal.