Solution for PRATABHI (LOC Jun '17)

general
, ,
1

What’s the approach to solve the problem PRATABHI?

2 Likes
2

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.

5 Likes
3

can you give the solution code please?

1 Like
4

Can you provide me a relavent code?

1 Like
5

@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.

2 Likes
6

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.

1 Like
7

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).

8

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… :slight_smile:

2 Likes
9

@abhikalpu_123 I can not get your proof ? can you please describe it with an example…?

1 Like
10

Can you please describe your poof part with pretty example?

1 Like
11

![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

3 Likes
12

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

13

please have a look at the pictures i have uploaded.

1 Like
14

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

2 Likes
15

@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?

2 Likes
16

@abhikalpu_123 Could you please answer this?

1 Like
17

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.

18

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 :slight_smile:

19

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.

20

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…