Mahmoud and Ehab DP Concept Doubt

#1

Codeforces Problem 959F
if ‘a’ element is already present in the set, then
dp[i-1][x]=p (let)

how dp[i-1][a^x] is also equals to p?
where a^x is means [a XOR x]

Recurrence relation: dp[i][x]=dp[i-1][x] + dp[i-1][a^x]

#2

hello @Kinjal
dp[i][x]= ways to choose subsequence from [0…i] such that their xor is x right?
now we have two options for i .
either we include it or we exclude it.
case a) we excluded current element it. in that case
dp[i][x]=dp[i-1][x] right? (ways to form subsequnce from [0…i-1] whose xor is x )

case b) we included current element . in that case
because we have included a[i] .
so we can write a[i] ^ something = x where something is xor we need from [0…i-1]

take xor with a[i] on both sides
we get something = x^a[i] right?
now that means when we include a[i] ,then from remaining sequence [0…i-1] we need to make xor whose value is x^a[i]
which is given by dp[i-1][x^a[i]]

overall answer will be
case a + case b
dp[i][x] = dp[i-1][x] + dp[i-1][a[i]^x]

#3

Bhaiya, I guess that we should include a[i] to get dp[i][x] because
dp[i][x] denotes the xor of first i elements in the array whose value is x.

toh hume a[i] include karna hi padega na?

#4

nahi . aise nahi hai.
dp[i][x] -> all subsequence that u can generate from first [0…i] such that their xor is x.
isme ye jaruri nahi hai ki i ko include hi karna hai.

try to relate it with susbet sum problem.

dp[i][sum]=dp[i-1][sum] (excluded) + dp[i-1][sum-a[i] ] (included)

yaad aaya kuch?

#5

Iska matlb dp[i][x] ka do state ban rha hai…
with a[i] and without a[i]

#6

Ha correct … … …

#7

Isse mujhe kya fayda hoga iss problem meh? a[i] ko first hand meh lena behtar nhi hai?

#8

First hand means?

IS TABLE KO BANAN KE BAAD ANSWER EASILY KAR SAKTE HAI QUERY

#9

Accha thik hai… iss table ko banane ke lea kya kya parameter use kar rhe hai?
Yah do value use kar rhe hai kya?
(xor value till i) and i itself?

#10

I aur maximum value of x.

Ek baar ye padh lo clear ho jayega
https://codeforces.com/blog/entry/58712

#11

Bhaiya, hum ek set le rhe hai, right?
Aur usme bas xor value hi add ho rha hai ya element bhi?

I mean, set meh bas xor value hi add ho rha hai na…

#12

Humne abhi naive approach discuss kiya hai without set.

#13

Bhaiya, naive approach ko bhi proof karne ke lea set ka use kiya gya hai na…

Jaise ki,

  1. agar x set meh hai aur a[i] bhi set meh hai tab x^a[i] bhi set meh rahega
  2. agar x set meh nhi hai aur a[i] bhi set meh nhi hai tab x^a[i] bhi set meh nhi rahega
#14

Naive mein set ki jarurat nahi hai.
Ek baar ye problem solve karo

Actual problem solve karne se pehle

#15

Bhaiya, actual problem ka naive approach code
magar, dp[i][j]=dp[i-1][j]+dp[i-1][j^a[i-1]];

j^a[i-1] isme, a[i-1] se kyun kiya wo samajh nai aya…a[i] se karna chahiye tha…

j^a[i] karte hai toh seg fault de rha hai…

#16

bro inhone 0 based indexing li hai.

agar 1 index se store karoge to a[i] use hoga

#17

Aur yah indexing a[] ke bare meh bol rhe hai ya dp[][] ke bare meh?
Bhaiya, thora specifically boliye kaha 0 based indexing liya hai?
I guess, a[] ke bare meh bol rhe hai

#18

given array mein 0 based hai.

#19

Accha…thik hai…
Iss naive approach ka time complexity O(2^n) hoga ya isse kam like (row*col)?

#20

O(N * X)
.
where N is no of element
X-> maximum xor value