# How to solve XORGON

How to solve this…

4 Likes

In the Final array,for each i in 1 to k, a_i=a_{i+k}=a_{i+2*k}=..., So I declared dp[k+1][2] where dp[j][k] is the minimum number of flips for a_i=a_{i+k}=a_{i+2*k}=... for each i in 1 to j and the xor of a_1 to a_j is k. Answer will be dp[k][1]

5 Likes

Consider a window of k elements in array ( let it be a[i] to a[i+k-1] ). Now when we shift this window forward one step then the element which left the window is a[i] and which get inserted into the window is a[i+k], now notice that i mod k = (i+k) mod k and if for previous window number of ones are odd then for next window number of ones can be odd if a[i]=a[i+k]=1 or 0 (simultaneously both should be same). Hence we can now see that in final obtained array, all a[i] will be equal to a[i mod k]. Now which values should be assigned can be calculated via minimum number of flips needed so to minimize the answer.
Now to ensure that whether the number of ones in the window is odd we can calculate the window elements of first k elements and if number of ones is even then we can change any flip any one series of a[i mod k] which minimizes the answer.
More details refer my solution → MySolution

8 Likes

I wasted 1 hour in contest trying some greedy heuristics just to learn that this problem is of dp. Such a nice observation, thanks for sharing.

Now to ensure that whether the number of ones in the window is odd we can calculate the window elements of first k elements and if number of ones is even then we can change any flip any one series
but how did you check it is even or odd??
i did not understand this much part of your code
mini=min(mini,abs(has[i][0]-has[i][1]));
if(has[i][1]>has[i][0])
odd^=1;
}
if(odd==0)
{
ans+=mini;
}

How to solve the 4th problem of the contest?

1 Like

you have to check in 1 st window no. of set bits are even or not. and if has[i][1]>has[0] it means u r making 1 of that series so we count as it 1. and if this condition false it means u r making 0 of that series . hence u will count it as 0. hence in last u will check this count is even or not, if it is even then u have to flip one series. which minimizes the answer.

1 Like

Can anyone explain a reason why we consider a window of k elements ? Thank you

@napatnicky
Since its asked that the xor of all elements in any subarray of length k should be 1, if you closely observe then you can conclude that for that to happen, the pattern should repeat in a cyclic manner, or we can say that every k elements from 0 to i will have the same pattern! So now, the given pattern of length N can be compressed to a pattern of length k by noting the number of zero’s and the number of ones at every i % k position.

1 Like

why are u helping this guy whose intention is to cheat??
he made a post about ENGXOR which is from ongoing contest and then he edited

@vivek_rathi_53 @aditya_sheth @enem sir pls respond ??