×

# XOR with subset.Not understanding the logic of dp!

 1 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 3★getsuga 61●3 accept rate: 0%

 1 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 :) answered 11 Nov '15, 18:31 367●2●9 accept rate: 43%
 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:

×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