fille_code's blog

Flipping Coin
By fille_code, 9 years ago, In English

Hi friends,can anyone suggest away of doing the following problem in O(n) time using DP. 327A - Игра с переворачиванием

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

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

A solution was posted in this editorial. The algorithm the author is referring to at the end of his solution is called Kadane's Algorithm. You can find an explanation here.

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

I don't understand why are you asking when there is an editorial? Is it so hard to click on the tutorial button on the right of the problem statement? And BTW, this is one of the few good and detailed editorials on codeforces.

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

    Because my O(n) submission using Kadane's algo is giving wrong answer! :) 10026842

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

      Then you should have mentioned that in your post, shouldn't you?

      → Reply