ANKNIM2 - Editorials

general
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Ankit Srivastava and Uttam Kanodia

Tester: Roman Rubanenko
Editorialist: Amit Pandey

DIFFICULTY:

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.
			answer[j-i]++;

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:

  1. FARASA

Solution:

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

1 Like
2

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).

1 Like
3

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?

4

Shouldn’t it be

ans[S[j]-S[i]]++;

in the second code block?

1 Like
5

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.

1 Like
6

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.

7

@yubowenok, for each |S|, check whether brute force will faster or FFT. and use the faster version.