Problem in solving Kiljee and XOR problem from hackerearth.

general
, , ,
1

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

2

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

please answer

3

Help guys.

4

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

5

@vijju123

Thanks for the reply, but please check once you are done with the long.

6

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

Long challenge is over, kindly reply.

7

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

1 Like
8

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

9

@vivek_1998299 @vijju123

Can you please explain why this solution is incorrect.

https://pastebin.com/g0GdB9pq

10

@vivek_1998299

And I guess max xor would only be up wto 1024.

11

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.

12

@vivek_1998299

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.

13

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.

14

@vivek_1998299
Why do we need to initialize other elements to -1, what is advantage of that.

15

This is my ac solution : https://ideone.com/C0kl8a

If u have any doubt feel free to ask.

16

@vivek_1998299

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

17

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.

18

@vivek_1998299

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.

19

My solution is same as using curr,prev.

Could u send ur solution…

20

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?