By BanazadehAria, history, 15 months ago,

Hi can anyone tell any dp approach to this?

I can think of a O(n*m*2^10) dp But it will not pass.

• 0

 » 15 months ago, # |   0 Auto comment: topic has been updated by ContestFucker (previous revision, new revision, compare).
 » 15 months ago, # | ← Rev. 2 →   +15 a non dp approach Spoilersyou get new information each time you open a new spoiler please think more before openuse the fact that0 ^ x = x another facta ^ b != 0 (a != b) what ifif you choose random number in each rowif xor_sum > 0 -> doneelse if you get xor_sum = 0try to use above fact still not get it?lets choose one random row and xor_sum is the xor sum of all selected interger except current onexor_sum ^ (the value we chose in this row) = 0-> xor_sum = (the value we chose in this row) ^ 0keep in mind that a ^ b = c -> a = b ^ c think moreyou can choose a different number than chosen one in that row-> the xor sum of all selected interger = the xor sum of all selected interger except current one ^ (number != current chosen in this row)= 0 ^ (the value we chose in this row) ^ (number != current chosen in this row)= 0 ^ (old ^ new) = 0 ^ (!0) != 0 conclusionselect first number in all rowthen if xor sum > 0 -> print all of chosen numberelse try to choose a different number with chosen number in a rowprint all of chosen
•  » » 15 months ago, # ^ |   0 The whole point of this post was to find a DP approach, and you missed that
•  » » » 15 months ago, # ^ |   +8 I edited the comment, thanks for pointing that out
•  » » 15 months ago, # ^ |   +8 Not dp but amazing :(
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 But instead of this its just enough to proof(Not a really hard one) That if we have a1^...^an = 0 We can be sure that ==> a1^...^x !=0 (x != an)==>1-If a1^...^an-1 is 0 then x^0 = x (Correct)2-else==>We know the fact that any number is ^ itself is zero.And its the only number that if we xor it it will get zero.(2)So now we know that an equals to a1^.....^an-1 and also we know that (x!=an)==>(3) So a1^...^an-1 ^ x is not zero because of (2) and (3).Please Correct Me if i have any mistake in my proof.
•  » » » 15 months ago, # ^ |   +8 I think you have the same proof
 » 15 months ago, # |   +8 You can write dp such as you think but for each bit separate.
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 what you mean "for each bit seperate"dp[i][mask] ==> The maximum we can get using [1..i](repesant rows) and the mask is the result of the xor of the numbers that we have.And i think the update is O(m).And now were not going through any bits please clarify that thank you.
•  » » » 15 months ago, # ^ |   0 dp[i][bit][bitonoroff] answer it is possible to get no zero after i-th row. For row if arr[i][j]&(1<
•  » » » » 15 months ago, # ^ |   0 Thanks, 1-What is the time complexity ?2-And Please Compelete Your state statement what is usage of bit and bitonoroff?
•  » » » » » 15 months ago, # ^ |   0 1 time complexity is n*10*2*m 2 Main idea is that dp[i][mask] answer is exist such columns for each row that xor of all is non zero. We want to change mask to some another state. Answer is exist if for some bit(one of 10) (we change matrix such that matrix[i][j]=bool(arr[i][j]&(1<
•  » » » » » » 15 months ago, # ^ |   0 so we loop through 10 bits and make a dp for all of the 10 states?
 » 15 months ago, # | ← Rev. 2 →   0 My dp approach: For each row and for each possible "xored" value try to combine it with every item of the next row. Return the first value which is not zero. My sub: 56398315
•  » » 15 months ago, # ^ |   0 Why You pass ? I think test cases are weak because You run in O(n*m*1024(Possible Mask Value) ==> (500*500*1024) ?