What’s the approach to solve the problem PRATABHI?

a[i] can go up to 10^9 (i.e. 30 bits in binary representation).for each bit we store in a set where they occurs(at which indexes of array their value is 1) a. also we maintain an array count[i]= number of times i th bit occurs in array a.

For example- if the given array is a[1]=(001010)_2 , a[2]=(001001)_2 , a[3]=(100010)_2 , a[4]=(111011)_2 (assuming 1 based indexing and right most bit as 1st bit) for 1st bit store indices-2,4. for second bit we store indices-1,3,4 and so on.

Given a number H we have to check H can be made by XORing a subset of elements of array S (definition of array S is same as in problem statement). The answer is NO if any bit which is 1 in H and has a count zero. Suppose set S_1 denotes the set of indexes of the first occurrence of all the bits where value of the bits are 1 in H and set S_2 denotes the set of indexes of the first occurrence of all the bits where value of the bits are 0 in H . First occurrence of i th means the minimum index of array a at which value of i th bit is 1.

Suppose H= (1011000)_2 (as you can see the value of 4th,5th,7th bit is one)

Then S_1= {first occurrence of 4th bit , first occurrence of 5th bit, first occurrence of 7th bit in the array a}

S_2= {first occurrence of remaining bits}

Clearly S_1 ,S_2 can be found easily by the sets we made for each bit in the starting.

The answer is YES if both sets are disjoint.

Proof- If the the first occurrence of a bit whose value is 0 in H (lets denote it as bit_m) is same as first occurrence of a bit whose value is 1 in H (lets denote it as bit_n) then all the elements in array S will contain either both the bit(i.e. bit_m ,bit_n) as 1, or both the bit as 0. i.e. for all S[i] Value of bit_m = value of bit_n. so XORing any subset of s will give a result R whose value of bit_m=value of bit_n. so answer is NO.

Modification query is simple …

check this out-

https://www.codechef.com/viewsolution/14398702

(it’s not my solution, but has same logic as mine.)

only change here is priority queue is used instead of set.

can you give the solution code please?

Can you provide me a relavent code?

@abhikalpu_123 what will be output according to your solution for the following case:

4 2

1 1 16

2 16

Since the first occurrence of all the bits(of 16) is same(ie index 1). Therefore the sets S1 and S2 will not be disjoint and the answer must be “NO”.

But I think correct answer is “YES”.

Correct me if I am wrong.

16= (10000)_2

S_1={first occurrence of 5th bit} = {1}

S_2= {first occurance of 4th, 3rd, 2nd ,1st bits}={}

S_1 , S_2 are disjoint as they dont have anything common…

So answer is YES.

Why s2 is empty?

First occurrence of ith bit(0<i<5) is 1 as binary representation of 16 is 10000 which has zero at ith position (0<i<5).

My apologies , I did not mention first occurrence of i th means the minimum index of array a at which value of i th bit is 1. Fixed…

Can you please describe your poof part with pretty example?

![alt text][1]

![alt text][2]

Also see both columns in S[i] corresponding to 2nd bit and 3rd bit are same. So for any subset of S[i] Xor_result obtained at 2nd bit will be same as result obtained at 3rd bit. But look at the query we want 1 in 3rd bit and a 0 at 2nd bit. which can not be achievable.

[1]: https://discuss.codechef.com/upfiles/2_1.jpg

[2]: https://discuss.codechef.com/upfiles/1_2.jpg

please have a look at the pictures i have uploaded below…

please have a look at the pictures i have uploaded.

sorry for my bad hand-writing o.O…feel free to ask any further doubts…

@abhikalpu_123 I really like your proof. But I have a doubt. You have a solution which proves that it is not possible if a certain condition is verified. Is is also true that if the condition is not satisfied you can create a subset XORing which we will get the required answer? I think that your solution fails to address this. I mean, is it possible that the two sets are disjoint still the answer is NO?

No, it is not possible.

S[i] XOR S[i-1] will contain those bits whose values are 0 in S[i] and 1 in S[i-1](case 1) or 1 in S[i] and 0 in S[i-1](case 2).

But the 1st case is not possible as S[i]= S[i-1] OR a[i] i.e. all those bits which are 1 in S[i-1] will remain 1 in S[i]. So only the second case is possible. Remember you know that only the bits whose first occurrence is i will have value 1 in S[i] and 0 in S[i-1].

Then its a easy conclusion that S[i] XOR S[i-1] will contain only those bits whose first occurrence is i.

Now moving to your question( Or you have already got it ;D )-

Consider S_1 , S_2 are disjoint . let S_1 = {i_1,i_2,i_3…,i_n}. we can prove that there exists a subset which will be the final answer to the problem (name it Fans).

Fans is = {i_1,i_1-1,i_2,i_2-1,i_3,i_3-1,…,i_n,i_n-1}.

why did i write Fans like this??

$S[i_1]$XOR$S[i_1-1]$ will contain some bit of the number asked in the problem,

$S[i_2]$XOR$S[i_2-1]$ will contain some other bits of the number asked in the problem, and so on…

also all these bits are distinct

Hence, we can show that $S[i_1]$XOR$S[i_1-1]$XOR$S[i_2]$XOR$S[i_2-1]$… $S[i_n]$XOR$S[i_n-1] =$ the number asked in the problem.

Really sorry for my late reply. I know its really frustrating to get answer after 6 days.Regret for the inconvenience caused (for my proof) . Ask any further doubts happy to help :D…