Hi can anyone tell any dp approach to this?
Problem link==> http://mirror.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.
Hi can anyone tell any dp approach to this?
Problem link==> http://mirror.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.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 164 |
| 2 | adamant | 150 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
Auto comment: topic has been updated by BanazadehAria (previous revision, new revision, compare).
a non dp approach
you get new information each time you open a new spoiler
0 ^ x = x
a ^ b != 0 (a != b)
if you choose random number in each row
if xor_sum > 0 -> done
else if you get xor_sum = 0
try to use above fact
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
you 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
select 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) ?