FINELE - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

Prefix sums or Lucas’s theorem

PROBLEM:

You’re given an array A of length N.
Do the following N-1 times:

  • Create a new array B of length |A|-1 such that B_i = A_i \oplus A_{i-1} for each 1 \le i \lt |A|.
  • Then, set A := B.

The final array will have only a single element.
Find this element.

EXPLANATION:

Let A^0 denote the initial array, and A_i denote the array obtained after the i-th iteration.
Our goal is to find the single element of A^{N-1}.

We can arrange the arrays A^0, A^1, \ldots, A^{N-1} in the shape of a pyramid, from bottom to top.
For example, if A = [1, 2, 3, 4] we obtain:

\begin{array}{ccccccccc} &&&&4&&&&\\[6pt] &&&2&&6&&&\\[6pt] &&3&&1&&7&&\\[6pt] &1&&2&&3&&4& \end{array}

The value we’re looking for is the tip of the pyramid.

Clearly, each value in the pyramid is the XOR-sum of several elements from the base array.
Our goal is hence to find which elements are present in it.

Note that within the pyramid, each element equals the XOR of the two elements to its bottom-left and bottom-right.
This is quite similar to what happens in Pascal’s Triangle, just that instead of normal addition we have XOR-sums now.

In fact, if we look at things in terms of contribution from the top downwards, we end up with exactly Pascal’s triangle!
That is,

  • We end up with one copy of the topmost element.
  • This requires one copy each of the two elements in the second row; since their XOR-sum equals the top element.
  • For the third row, we’ll have one copy each of the first and third element, but two copies of the middle element - because the middle element contributes to both elements above it.
  • And so on and so forth.

This means we’ll end up with

\begin{array}{ccccccccc} &&&&&1&&&&\\[6pt] &&&&1&&1&&&\\[6pt] &&&1&&2&&1&&\\[6pt] &&1&&3&&3&&1&\\[6pt] &1&&4&&6&&4&&1\\[6pt] &&&&&\vdots \end{array}

where each value represents the number of times that element contributes to the topmost value’s XOR-sum.
This, as pointed out previously, is literally Pascal’s triangle.

Pascal’s triangle tells us that the k-th value in the n-th row from the top is \binom{n}{k}.
(Using 0-indexing for both row count and elements within a row.)

In the pyramid we created, the base array was row N-1.
So, the contribution of the element at index i (again, 0-indexing) to the overall XOR is \binom{N-1}{i} times.

Now, recall that x\oplus x = 0 for any x.
So, the XOR of k copies of x is:

  • 0 if k is even
  • x if k is odd.

So, if \binom{N-1}{i} is even, then element A_i doesn’t contribute to the XOR at all.
If it’s odd, it will contribute exactly A_i.

This reduces the problem to just being able to tell, for each 0 \le i \le N-1, whether \binom{N-1}{i} is odd or not.

There are a couple of different solutions to this.
Below is one that does not require any prerequisite knowledge.

Define \nu_2(x) to be the (exponent of the) largest power of 2 that divides x.
For example, \nu_2(3) = 0 because 3 is odd, \nu_2(8) = 3 because 2^3 = 8 divides 8, and \nu_2(12) = 2 because 2^2 = 4 divides 12.

Note that with this definition, we have \nu_2(x\cdot y) = \nu_2(x) + \nu_2(y), and in the same vein \nu_2(\frac{x}{y}) = \nu_2(x) - \nu_2(y).
Further, an integer is odd if and only if \nu_2(x) = 0.

Now we want to check if \nu_2(\binom{N-1}{i}) = 0 or not.
To do this, note that

\binom{N-1}{i} = \frac{(N-1)!}{(N-1-i)! \cdot i!}

So, by the division and multiplication rules seen above,

\nu_2\left(\binom{N-1}{i}\right) = \nu_2((N-1)!) - \nu_2((N-1-i)!) - \nu_2(i!)

Also, yet again by the multiplication rule, we have

\nu_2(N!) = \nu_2(N) + \nu_2((N-1)!)

Computing \nu_2(N) is easy, just repeatedly divide N by 2 till it’s no longer possible to do so (this takes \mathcal{O}(\log N) time if brute forced.)
This allows us to compute \nu_2(k!) for all k \le N in \mathcal{O}(N\log N) with prefix sums, after which \nu_2\left(\binom{N-1}{i}\right) can be computed in constant time, hence solving the problem.

For an alternate solution, Lucas’s theorem gives an easy condition to tell the parity of \binom{N-1}{i}: the parity is odd if and only if i is a submask of (N-1) in binary representation.

TIME COMPLEXITY:

\mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (PyPy3, prefix sums) 
N = 200005
v2 = [0]*N
for n in range(1, N):
    v2[n] = v2[n-1]
    
    x = n
    while x%2 == 0:
        v2[n] += 1
        x //= 2

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    for i in range(n):
        if v2[n-1] - v2[i] - v2[n-1-i] == 0:
            ans ^= a[i]
    print(ans)
Editorialist's code (PyPy3, Lucas's theorem) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    for i in range(n):
        if (n-1) & i == i:
            ans ^= a[i]
    print(ans)