vsanjay_nitdgp's blog

266-div2(c)-doubt
By vsanjay_nitdgp, history, 9 years ago, In English

could any one explain the logic for his problem.

i couldn't understand the editorial.

thanks in advance.

http://codeforces.com/problemset/problem/466/C

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I haven't read the editorial, my idea was pretty simple. You know before hand the value that each segment should have. Just that sum / 3. And one segment should be a prefix and the other a sufix, now you just notice that if you pick a non overlaping prefix and suffix which sum would be (global_sum / 3) the middle segment also will satisfy this condition. So the problem looks simple now. For every prefix that satisfy the condition count how many suffix starts after the end of this prefix (just preprocess this calculations to do it in O(1)) The sum of this values is the answer to the problem. I hope it will be useful to you. Here is my code: 7952017.

→ Reply