raman92's blog

Segment Trees (Flipping Coins Codechef)
By raman92, 11 years ago, In English

I am solving this question: http://www.codechef.com/problems/FLIPCOIN/ but getting wrong answer.

My solution is: http://pastebin.com/bDbfwtjM

my idea:

each time update is called if the flag==0 for the current node and current node needs to be flipped flag[left child]=(flag[left child]+1)%2 , flag[right child]=(flag[right child]+1)%2 is done and the value of the current node is changed.

if the flag==1 current flag is set to 0. current is not flipped. flag[left child]=(flag[left child]+1)%2 , flag[right child]=(flag[right child]+1)%2

Please help me where the solution is wrong.

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

It's good idea to make bruteforce solution then make random test then compare between the output of segment tree and the output of bruteforce solution and and the bug

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

flag[2*nd+1] += (flag[2*nd+1]+1)%2; flag[2*nd+2] += (flag[2*nd+2]+1)%2;

not =

→ Reply