Can anyone help me in solving Kiljee and XOR problem from hackerearth.

Ok so since the max element is 10^3,max xor can be 2047. So lets create a dp table :- dp[2048] where dp[i] stores the maximum size of subset who xor is i.We construct it as follows:

initialise all values to 0.

Now iterate the array and do the following ,

for i =(1,n):

on all x from 1 to 2047,update dp[x^arr[i]]=max(dp[x^arr[i],dp[x]+1) (while writting i’ll suggest u to take two arrays prev and curr and then we’ll have curr[x]=prev[x] (first do this for all x) and curr[x^arr[i]]=max(curr[x^arr[i]],prev[x]+1)

)

so since now we have all values u can calculate it easily ,(u can use modular exponentiation to calculate pow(31,j))

Help guys.

Hey! I will be able to help after long. Sorry for the delay.

@mathecodician @vijju123 @meooow @wangrq @taran_1407 @assassin28

Long challenge is over, kindly reply.

Yes, I agree with this explanation. Nicely said!!

Can you please explain why this solution is incorrect.

Yeah sorry!! I didnt saw that ‘l’ thing.

The mistakes i could found out where these:

1)dp[0][0]=0 size of subset with 0 xor is 0 :- {}

2)while doing dp[i][j] = dp[i][j^a[i-1]]+1 u should check whether dp[i][j^a[i-1]] was possible(so u could initialise dp with -1 ),if its not possible then dp[i][j]=dp[i-1][j])

3)u should do res=(res+(x*y)%M)%M

4)And if possible try using long if u still get wa.

I did dp[0][0]=1 so that there could be a base case.

Suppose if dp[0][0]=0 then say first element of the an array is 3 then dp[1][3]=max(dp[0][3],dp[0][0]+1)

and since we will check dp[0][0] will not be possible. then dp[1][3]=0 and all the following would get to zero.

No No…

dp[0][0] is possible ,as u can have an xor of 0 by taking no elements

dp[0][x!=0] is not possible as u cant have an xor of x if u have 0 elements.

Thats the reason why i said to initialise dp[0][0]=0 and other elements to -1.

I have used the similar approach, but not working. this is my code. can you please check the fillDp() function.

I dont know why u are running your inner loop till 7.

The main reason for WA is basically the inner loop.You should run inner loop from 0 to 1023 and not 0 to maxElement.

The reason is j^a[i] can have a value upto 1023.

And use two arrays 1)curr 2)prev

or dp[i][j] as u did previously.

I am getting WA even if I run inner loop up to 1023.

you did with the single array, I want to understand that logic.

My solution is same as using curr,prev.

Could u send ur solution…

Hey @vivek_1998299 Can you please provide the proof of above relation? I mean how do you approach such a elegant solution in one time?