You are not logged in. Please login at www.codechef.com to post your questions!

×

Solution for PRATABHI (LOC Jun '17)

2
1

What's the approach to solve the problem PRATABHI?

asked 04 Jul '17, 00:14

avi224's gravatar image

4★avi224
218110
accept rate: 18%

edited 04 Jul '17, 00:15


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

link

answered 04 Jul '17, 03:41

abhikalpu_123's gravatar image

5★abhikalpu_123
1475
accept rate: 8%

edited 04 Jul '17, 18:50

1

Can you provide me a relavent code?

(04 Jul '17, 04:03) bansal12325★
1

Can you please describe your poof part with pretty example?

(05 Jul '17, 00:38) bansal12325★

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

(05 Jul '17, 01:03) abhikalpu_1235★

alt text alt text

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.

link

answered 05 Jul '17, 00:59

abhikalpu_123's gravatar image

5★abhikalpu_123
1475
accept rate: 8%

edited 05 Jul '17, 01:18

2

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

(05 Jul '17, 01:08) abhikalpu_1235★

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

link

answered 04 Jul '17, 08:06

mohitrbhardwaj's gravatar image

3★mohitrbhardwaj
1713
accept rate: 0%

edited 04 Jul '17, 08:07

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) abhikalpu_1235★

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) mohitrbhardwaj3★
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_1235★

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

link

answered 06 Jul '17, 16:42

dhruvsomani's gravatar image

3★dhruvsomani
1448
accept rate: 8%

1

@abhikalpu_123 Could you please answer this?

(10 Jul '17, 18:08) dhruvsomani3★

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) abhikalpu_1235★

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) abhikalpu_1235★

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) abhikalpu_1235★

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_1235★

can you give the solution code please?

link

answered 04 Jul '17, 03:48

soham1234's gravatar image

6★soham1234
1.8k614
accept rate: 22%

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

link

answered 05 Jul '17, 00:28

avi892nash's gravatar image

5★avi892nash
823
accept rate: 20%

edited 05 Jul '17, 00:29

1

please have a look at the pictures i have uploaded.

(05 Jul '17, 01:04) abhikalpu_1235★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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