hanfei19910905's blog

A question about 170div1 problem C 's 17th test
By hanfei19910905, 11 years ago, In English

here is my submission , which got a WA on 17th test 3219752

My solution is regarding the segments as the stones in NIM game. The correctness can be proved by SG theorem .

In the 17th test . The number of rest sticks is 1 1 4 1 1 4 (for the same Y) and 2 1 1 3 1 2 . my answer is change 3 to 1 in order to make the xor value to 0.

The system answer is to cut 2,0 2,5 . but 2,3 — 2,4 has been cut before. Is it valid ?? And why my answer is wrong ? Thx :)

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Your idea is correct, but the sizes of NIM heaps here are 2 4 2 4 (the same Y), 3 4 1 2 (the same X). Their XOR is 4. After your cut, they become 2 4 2 4, 3 2 1 2, with XOR 2. After the correct answer, they become 2 4 2 4, 3 0 1 2, with XOR 0.

So what you need to do is consider the total number of uncut segments on every line as the size of the NIM heap, not just consecutive ones. That's because your cut can intersect the previous ones.

The transition from consecutive uncut segments to total number is quite easy, so as long as the rest of your algorithm is correct, you should get OK easily.

→ Reply