You are not logged in. Please login at www.codechef.com to post your questions!

×

ANKNIM2 - Editorials

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

This question is marked "community wiki".

asked 18 Jun '15, 15:19

amitpandeykgp's gravatar image

4★amitpandeykgp
25911522
accept rate: 0%

edited 09 Feb '16, 20:05

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 22 Jun '15, 00:16

xellos0's gravatar image

7★xellos0
5.9k54292
accept rate: 10%

Shouldn't it be

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

in the second code block?

link

answered 26 Jun '15, 03:02

johnathan79717's gravatar image

4★johnathan79717
196125
accept rate: 0%

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.

link

answered 25 Jul '15, 03:01

lebron's gravatar image

7★lebron
3.3k317
accept rate: 24%

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?

link

answered 22 Jun '15, 02:22

yubowenok's gravatar image

6★yubowenok
465
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) amitpandeykgp4★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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