429A. XOR-TREE

Revision en1, by yongwhan, 2016-01-31 14:40:37

I am confused by this problem: 429A - Xor-tree

As far as I understand, in the sample test, after applying operation on node 4, we have:

0 0 1 0 0 0 1 1 1 0

Now, if we apply operation on node 7, we get the original sequence back; that is:

1 0 1 1 0 1 0 1 0 1

So, the upshot is if we apply operations on the nodes that are even distance apart, they completely cancel each other out, leading to only four distinct states.

I am now convinced that I am thinking about the problem in a wrong way. Is it perhaps that the initial node that you are applying the operation to does not flip its state? (I read the problem statement multiple times but it is not written that way)

Could anyone point out what I am missing from the problem statement? Judging from so many AC's I am sure I am missing something but at the moment I stay puzzled. I read the editorial but still could not make sense out of the problem.

Thanks!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English yongwhan 2016-01-31 14:40:37 948 Initial revision (published)