×

# ANKNIM2 - Editorials

Author: Ankit Srivastava and Uttam Kanodia
Tester: Roman Rubanenko
Editorialist: Amit Pandey

Medium

# PREREQUISITES:

Fast Fourier Transform.

# PROBLEM:

Given an array of $N$ integers. You have to find count of all subarrays of size $m$, such that if a Nim Game is played on the subarray, second player will win. Do it for all possible values of $m$, $1 \le m \le N$.

# EXPLANATION:

It can be claimed using Nim Game theory that second player will win the game if $XOR$ of the selected subarray is $0$. We can find XOR of any subarray in $O(1)$ time by creating a prefix XOR array.

$$preXOR[0] = 0 \hspace{3 mm}\& \hspace{3 mm}preXOR[i] = A[0] \oplus A[1] \oplus \cdots \oplus A[i-1]$$

$$A[i] \oplus A[i+1] \oplus \cdots A[j] = preXOR[i-1] \oplus preXOR[j]$$.

Now, let me present an $O(N^2)$ solution for the problem.

answer[n] = 0;
for i in range(0,n):
for j in range(i+1,n):
if preXOR[i] == preXOR[j]:      //subarray having size (j-i) has XOR 0.


Consider a number $k$. If it appears $l$ times in the $preXOR$ array, then there will be $^lC_2$ subarrays in array $A$ whose XOR is zero. We can create an array corresponding to indices of $k$ in $preXOR$ array, and call it $S$. It means $preXOR[S[i]] = k$ for all $i < l$.

      for i = 0 to l-1:
for j= i+1 to l-1:
ans[j-i]++;       // there is a subarray of size (j-i) having XOR 0.


It can be explained further,Consider that preXOR array is $[1,2,3,1,1,4,1]$, then the array $S$ for $k=1$ will be $[0,3,4,6] \text{(0 based indexing)}$.

The above solution can take up to $O(N^2)$ time in the worst case, as size of $S$ can be $O(N)$. To improve it, we can do the following modifications:

1) If size of the array $S$ is lesser than $\sqrt{N}$, then we can use brute force as given above.

2) If size of the array $S$ is greater than $\sqrt{N}$, then the above solution will take more time. So, we can use the FFT to optimize the solution to time $Nlog(N)$.

Number of sub-arrays of size $K$ having XOR $0$, will be coefficient of $x^K$ in following polynomial:

$$(x^{S[0]} + x^{S[1]} + \cdots + x^{S[L-1]}) (x^{-S[0]} + x^{-S[1]} + \cdots + x^{-S[L-1]})$$

The powers of $x$ in the above polynomial are negative as well, therefore we do a small modification in above polynomial to make all the powers positive. It will be equivalent to the coefficient of $x^{N+K}$ in the following polynomial:

$$(x^{S[0]} + x^{S[1]} + \cdots + x^{S[L-1]}) (x^{N-S[0]} + x^{N-S[1]} + \cdots + x^{N-S[L-1]})$$

Which can be done in $O(Nlog(N))$ time using Fast Fourier transform. The FFT will give answer corresponding to all possible value of $m$ altogether.

We can repeat the above procedure for each distinct element $k$ of $preXOR$ array. The total count of subarrays corresponding to each value of $m$ will be the count of subarrays of size $m$ for each distinct value of $k$.

Worst case complexity of the above procedure will be $O(N \sqrt{N} \log{(N)})$.

Problems to solve:

# Solution:

Setter's solution can be found here
Tester's solution can be found here

This question is marked "community wiki".

25911522
accept rate: 0%

19.8k350498541

 1 I found an $O(N \sqrt N \log N)$ solution using FFT during contest, but I find hard to believe that it could run on 300000 numbers in 5 seconds. With that complexity, That's a problem even for simple algorithms, never mind FFT that has a horrible constant factor. We could use NTT, which is faster, but not that much faster (modulos vs complex numbers). answered 22 Jun '15, 00:16 7★xellos0 5.9k●5●42●92 accept rate: 10%
 1 Shouldn't it be ans[S[j]-S[i]]++;  in the second code block? answered 26 Jun '15, 03:02 196●1●2●5 accept rate: 0%
 1 Both setter's and tester's solution aren't available. Have you in fact tried to solve it with threshold equal to sqrt(N)? I guess you should have very good implementation of FFT to make it pass. That FFT part works in NlogN, which is much more than running time of naive part (for sqrt(N) it will work in O(N)) - therefore we are interested in picking higher threshold to make things better; I've checked several AC solutions, all of them use much higher constant - 2000, 5000, 6000, 10000 and even 12000. answered 25 Jul '15, 03:01 7★lebron 3.3k●3●17 accept rate: 24%
 0 Why do we need to handle $S$ differently for $|S|<\sqrt{N}$ and $|S|\geq\sqrt{N}$? I think for whatever $|S|$ we can just do FFT directly. The total running time would be $O(N\log{N})$. Am I missing sth? answered 22 Jun '15, 02:22 46●5 accept rate: 50% You can handle one group of identical xor-prefix-sums (at which starting and ending points can be) in O(N log N) using FFTs. The number of elements in that group doesn't matter very much. (22 Jun '15, 02:46) xellos07★ @yubowenok, for each |S|, check whether brute force will faster or FFT. and use the faster version. (22 Jun '15, 11:28)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,238
×334
×317
×81
×1

question asked: 18 Jun '15, 15:19

question was seen: 3,375 times

last updated: 09 Feb '16, 20:05