Hi can anyone tell any dp approach to this?

Problem link==> http://codeforces.com/contest/1151/problem/B

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

Thanks in advance.

# | User | Rating |
---|---|---|

1 | tourist | 3533 |

2 | Um_nik | 3459 |

3 | maroonrk | 3394 |

4 | ksun48 | 3384 |

5 | ecnerwala | 3347 |

6 | Benq | 3301 |

7 | boboniu | 3300 |

8 | Petr | 3293 |

9 | Radewoosh | 3288 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 207 |

2 | Monogon | 197 |

3 | SecondThread | 191 |

4 | pikmike | 187 |

5 | antontrygubO_o | 186 |

6 | vovuh | 185 |

7 | Um_nik | 183 |

8 | Ashishgup | 182 |

9 | Radewoosh | 169 |

10 | pashka | 168 |

Hi can anyone tell any dp approach to this?

Problem link==> http://codeforces.com/contest/1151/problem/B

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

Thanks in advance.

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/01/2020 18:17:07 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been updated by ContestFucker (previous revision, new revision, compare).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 row

if xor_sum > 0 -> done

else if you get xor_sum = 0

try 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 one

xor_sum ^ (the value we chose in this row) = 0

-> xor_sum = (the value we chose in this row) ^ 0

keep 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 row

then if xor sum > 0 -> print all of chosen number

else try to choose a different number with chosen number in a row

print all of chosen

The whole point of this post was to find a DP approach, and you missed that

I edited the comment, thanks for pointing that out

Not dp but amazing :(

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.

I think you have the same proof

You can write dp such as you think but for each bit separate.

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.

dp[i][bit][bitonoroff] answer it is possible to get no zero after i-th row. For row if arr[i][j]&(1<<bit) if dp(i+1,bit,bitonoroff^1) dp[i][bit][bitonoroff]=1 else if dp(i+1,bit,bitonoroff) dp[i][bit][bitonoroff] When you on last row you return bitonoroff. If you find that at some bit dp[0][bit][0] is 1 than you find an answer, and it is easy to know which column for each row you must get

Thanks, 1-What is the time complexity ?

2-And Please Compelete Your state statement what is usage of bit and bitonoroff?

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<<bit))) and we for each bit have mask with two states.

so we loop through 10 bits and make a dp for all of the 10 states?

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

Why You pass ? I think test cases are weak because You run in O(n*m*1024(Possible Mask Value) ==> (500*500*1024) ?