I have been stuck on CAKECUT asked on cook71 . Half of the tutorial is clear but I cant understand the last part of the tutorial where bits[] is formed and xor operations are performed on the bits[]. Every help will be appreciated.
Problem link : https://www.codechef.com/problems/CAKECUT
Editorial link : https://discuss.codechef.com/questions/82646/cakecut-editorial
Thanks!
bitset is actually a vector of bits which lets you perform operations bitwise operations on the complete array. read more about it over here . so back to the solution , lets store prefix sum for every rectangle starting from 1,1 to i,j in sum[i][j] .
so basically for a rectangle (x1,y1),(x2,y2) to have an even sum this should be true:
((sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+ sum[x1-1][y1-1])%2==0). -EQUATION 1
for example, let input be
corresponding prefix sum will be
so now you can consider a few pairs to verify pair .
okay , now a bit modification , incase of storing sum[i][j] directly , we will store sum[i][j] = sum[i][j]%2 .this wont effect anything just be careful with minus signs in the formula and things still remain the same , you can still apply the same formula to find rectangles . But to find all the rectangles you have to iterate over x1,y1,x2,y2 which makes it O(n^4) , lets look more into the formula that we are using.
for EQUATION 1 to be true or sum to be even , as it involves 4 (plus/minus) terms , there are only three possible cases :
all the above mentioned cases have interesting property that the xor of all four terms will 0 . so we can say that , for a rectangle to have even sum, sum[x2][y2]^sum[x1-1][y2]^sum[x2][y1-1]^sum[x1-1][y1-1]==0 .
where sum[i][j] =prefixum[i][j]%2
hope you are clear about everything explained till this point.
sum[x2][y2]^sum[x1-1][y2]^sum[x2][y1-1]^sum[x1-1][y1-1]=0
sum[x2][y2]^sum[x1-1][y2]==sum[x2][y1-1]^sum[x1-1][y1-1]. EQUATION 2 {so if for a given x1,y1,x2,y2 this equation is true we find one solution}
so now the actual algorithm. consider any two rows x1,x2 (x1<=x2) which will be lower and upper side of rectangle , now if we fix any two columns y1,y2 , we will get a rectangle , right? .
now what we do is , fill the sum[x1-1] array in a bitset B1 and sum[x2] in bitset B2 and find B2^B1 .
what actually B2^B1 contains? it will contain sum[x2][0]^sum[x1-1][0] sum[x2][1]^sum[x1-1][0] . . . sum[x2][m-1]^sum[x1-1][m-1]
To make EQUATION 2 true , we have already fixed x1,x2 and now to make it true , we pick any two values from B2^B1 which are equal , think about it !
so there are two cases either we can pick a 0 , so if there are Z zeroes in this bitset then solution+=(Z*(Z-1))/2.
or we can pick a 1 ,so if there are Z ones in this bitset then solution+=(Z*(Z-1))/2.
RUNTIME : O(N^2*(M/32)) where N^2 is to fix x1,x2 and M/32 to find xor of the bitset .
Hope you are getting it , ask your doubts if you have any.
Thanks! 