Anyone willing to help me on this question ?

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

  • 1010
  • 0101
  • 1110

corresponding prefix sum will be

  • 1 1 2 2
  • 1 2 3 4
  • 2 4 6 7

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 :

  1. any two terms are 1 and other two are 0.
  2. all four terms are 0.
  3. all four terms are 1.

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.

2 Likes

Thanks! :smiley:

//