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

×

XOR with subset.Not understanding the logic of dp!

</>dp[i][j] = dp[i - 1][j] | dp[i - 1][j ^ a[i]]</>

How is this arrived at.Why does A[0...i-1] having value j necessarily mean that A[0...i] should also posses the value j?

And why is this :

if there exists a subset P of A[1..i - 1] such that F(P) = j ^ a[i], then F(P) ^ a[i] = j ?

asked 11 Nov '15, 13:45

getsuga's gravatar image

3★getsuga
613
accept rate: 0%


Let us first solve a simple subtask : Given a set $A$ of $n$ integers and you have listed all the subsets of it

Consider $A = \{ 1,2 \} $ Now $P(A) = \{ \phi, \{1\},\{2\},\{1,2\}\} $

If we add a element $3$ to our current set then, $A = \{ 1,2,3 \} $ and $P(A) = \{ \phi, \{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\} $

While adding the element $3$ we have $2$ choices, either we add it to the existing subset or we leave the existing subset as it is

For example, $\{1\}$ will results in $2$ subsets, $\{1\}$ and $\{1,3\}$ and similarly for the other subsets

Now considering the original problem, main observation is that XOR value of the subset will be always between $0$ to $1023$

Let the $DP$ state be $(i,j)$, in which we have considered all the subsets of $A[1..i]$ and $j$ is the possible XOR value

if $DP[i][j]$ is $true$, the one of the subset of $A[1..i]$ will gives the XOR value $j$, $false$ otherwise

Now consider the $DP[i][j]$, in this we are considering all subsets of $A[1..i]$, so let us consider the $i^{th}$ element $i.e. A_i$

If we not consider this element then sub-problem reduces to $DP[i-1][j]$, else if we consider this element then one of the subsets of $A[i..i-1]$ must be XORed to $j \oplus A_i$ , because $j \oplus A_i \oplus A_i = j$

Thus we can say that $DP[i][j] = DP[i-1][j] \hspace{1 mm} \vert \hspace{1 mm}DP[i-1][j \oplus A_i]$

I hope you get the idea :)

link

answered 11 Nov '15, 18:31

pulkitsinghal's gravatar image

6★pulkitsinghal
36729
accept rate: 43%

edited 11 Nov '15, 18:37

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:

×2,718
×2,167
×1,405
×228
×24

question asked: 11 Nov '15, 13:45

question was seen: 1,478 times

last updated: 11 Nov '15, 18:37