What's the approach to solve the problem PRATABHI? asked 04 Jul '17, 00:14

$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 $ a1=(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 indices2,4. for second bit we store indices1,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. answered 04 Jul '17, 03:41
1
Can you provide me a relavent code?
(04 Jul '17, 04:03)
1
Can you please describe your poof part with pretty example?
(05 Jul '17, 00:38)
please have a look at the pictures i have uploaded below....
(05 Jul '17, 01:03)

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. answered 05 Jul '17, 00:59

@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. answered 04 Jul '17, 08:06
1
$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.
(04 Jul '17, 13:34)
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).
(04 Jul '17, 15:17)
2
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.. :)
(04 Jul '17, 18:49)

@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? answered 06 Jul '17, 16:42
No, it is not possible. $S[i]$ XOR $S[i1]$ will contain those bits whose values are $0$ in $S[i]$ and $1$ in $S[i1]$(case 1) or $1$ in $S[i]$ and $0$ in $S[i1]$(case 2). But the 1st case is not possible as $S[i]=$ $S[i1]$ OR $a[i]$ i.e. all those bits which are $1$ in $S[i1]$ 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[i1]. Then its a easy conclusion that $S[i]$ XOR $S[i1]$ will contain only those bits whose first occurrence is $i$.
(12 Jul '17, 13:15)
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_11$,$i_2$,$i_21$,$i_3$,$i_31$,....,$i_n$,$i_n1$}. why did i write $Fans$ like this?? $S[i_1]$XOR$S[i_11]$ will contain some bit of the number asked in the problem, $S[i_2]$XOR$S[i_21]$ will contain some other bits of the number asked in the problem, and so on... also all these bits are distinct :)
(12 Jul '17, 13:16)
Hence, we can show that $S[i_1]$XOR$S[i_11]$XOR$S[i_2]$XOR$S[i_21]$...... $S[i_n]$XOR$S[i_n1]$ $=$ the number asked in the problem.
(12 Jul '17, 13:17)
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...
(12 Jul '17, 22:53)

@abhikalpu_123 I can not get your proof ? can you please describe it with an example..? answered 05 Jul '17, 00:28
