Vahagn_Grigoryan's blog

Why isn't it working?
By Vahagn_Grigoryan, history, 4 years ago, In English

Hi, Codeforces community!

I tried to solve this problem by using recursion. But my submission gives wrong answer to test 5. The input is: 20 293434130 567534945 339132630 291152695 959629878 416618095 149341899 479358017 509348379 335313693 386003521 360528367 387150541 724271523 741417449 63831275 308645820 457460287 716709394 977143845. The answer is 5734409263, but my code's output is 5774922309. Can anyone tell where's the mistake please?

  • Vote: I like it
  • -23
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Looks like you are using just a simple greedy solution. But it isn't the correct approach and dynamic programming is necessary. Consider the following testcase:

11
1 3 5 7 9 11 13 15 17 99 100

Your solution greedily favours removing elements from the left side, because it thinks that 3-1 is better than 100-99. But a correct solution has to get rid of 99 and 100 as soon as possible.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I remove elements from both sides. I compare 100-3 and 99-1. 100-3<99-1 so I remove 100.

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

      100-3 < 99-1 (which can be also rewritten as 100-99 < 3-1) so you remove 1.

      → Reply