×

# Solution for PRATABHI (LOC Jun '17)

 2 1 What's the approach to solve the problem PRATABHI? asked 04 Jul '17, 00:14 4★avi224 218●1●10 accept rate: 18%

 5 $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 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. answered 04 Jul '17, 03:41 147●5 accept rate: 8% 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)
 3 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 147●5 accept rate: 8% 2 sorry for my bad hand-writing o.O..feel free to ask any further doubts..... (05 Jul '17, 01:08)
 2 @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 171●3 accept rate: 0% 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
 2 @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 144●8 accept rate: 8% 1 @abhikalpu_123 Could you please answer this? (10 Jul '17, 18:08) 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$. (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_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 :) (12 Jul '17, 13:16) 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. (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)
 1 can you give the solution code please? answered 04 Jul '17, 03:48 1.8k●6●14 accept rate: 22%
 1 @abhikalpu_123 I can not get your proof ? can you please describe it with an example..? answered 05 Jul '17, 00:28 82●3 accept rate: 20% 1 please have a look at the pictures i have uploaded. (05 Jul '17, 01:04)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×135
×77
×11

question asked: 04 Jul '17, 00:14

question was seen: 1,155 times

last updated: 12 Jul '17, 22:53