Блог пользователя farmersrice

Автор farmersrice, история, 6 лет назад, По-английски

http://codeforces.me/contest/1074/submission/45462396

http://codeforces.me/contest/1074/submission/45462405

These two codes are exactly the same, except for this part:

In the Wrong answer on test 14 submission:

for (int i : inTree[rootp]) {
	inTree[rootq].pb(i);
	distToRoot[i] = distToRoot[i] ^ distToRoot[p] ^ edgeWeight ^ distToRoot[q];
	root[i] = rootq;
}

In the Accepted submission:

edgeWeight ^= distToRoot[p] ^ distToRoot[q];

for (int i : inTree[rootp]) {
	inTree[rootq].pb(i);
	distToRoot[i] ^= edgeWeight;
	root[i] = rootq;
}

(This is the end of the method, so xor-equals edgeWeight shouldn't change anything later on.)

I thought xor sum is both commutative and associative? What's the difference between these two snippets? Am I missing something really obvious? Thanks in advance.

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

Not my bug, xor's bug

»
6 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

The for loop also modifies the values of distToRoot[p] and distToRoot[q] hence the WA.In your second submission, the original values of distToRoot[p] and distToRoot[q] are used to update other indices. There is no problem with xor here.

»
6 лет назад, # |
Rev. 4   Проголосовать: нравится +13 Проголосовать: не нравится

The xor summing rule is simple: and . In the Accepted submission, the logic value xor summed with distToRoot[i] in each iteration is computed before the loop. Therefore, the logic value of distToRoot[p] ^ edgeWeight ^ distToRoot[q] is invariant to the iteration variable i, i.e. does not change inside the loop. In the Wrong Answer submission, when the number of negation operations made to distToRoot[p] and distToRoot[q] in previous iterations of the loop is an odd number, the logic value xor summed with distToRoot[i] is the complement of edgeWeight in the AC code.