AyanoGod's blog

By AyanoGod, 4 years ago, In English

Hello, Hope you are doing well.

Problem link: https://codeforces.net/problemset/problem/1373/D Author's Editorial: https://codeforces.net/blog/entry/79376

According to the Author, we should use 2d DP but I am having a hard time understanding how and why these works.

"State of our dynamic programming is dpi,j where i∈[0;n] and j∈[0;2]. dpi,0 denotes the answer on the prefix of length I if we didn't start reversing the subarray, dpi,1 denotes the answer if we started reversing the subarray but didn't end it and dpi,2

denotes the answer if we ended reversing the subarray. Transitions are pretty easy:"

dpi+1,0=max(dpi+1,0,dpi,0+[i%2==0?ai:0]);

dpi+2,1=max(dpi+2,1,max(dpi,0,dpi,1)+[i%2==0?ai+1:ai]);

dpi+1,2=max(dpi+1,2,max(dpi,0,dpi,1,dpi,2)+[i%2==0?ai:0])

Please help me with how and why this works also how are we making sure that we don't reverse the array more than once?

PS: I have already searched and commented on editorial blog but no help from there.

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

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

Consider reversing the subarray $$$a[l \dots r]$$$. The array is now split into three parts:

  1. $$$a[0 \dots l - 1]$$$, denoted by $$$j = 0$$$
  2. $$$a[l \dots r]$$$, denoted by $$$j = 1$$$
  3. $$$a[r + 1 \dots n - 1]$$$, denoted by $$$j = 2$$$

The DP simply tracks the best value if we consider ourselves to be within each of the three sections. Since we only transition from lower $$$j$$$ to equal or higher $$$j$$$, we cannot possibly perform more than one reverse operation.

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

    And why do we need to have i+2 instead of i+1 here ?
    dpi+2,1=max(dpi+2,1,max(dpi,0,dpi,1)+[i%2==0?ai+1:ai]);

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

      Well, if we transition to $$$dp_{i+1,1}$$$, then we would be adding $$$a_i$$$ for odd $$$i$$$ twice, once when transitioning from $$$dp_{i-1}$$$ and once from $$$dp_{i}$$$.

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

        Didn't got what you mean by this.

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

          I mean just look at the formula.

          $$$dp_{i+2,1}=max(dp_{i+2,1},max(dp_{i,0},dp_{i,1})+ (i \% 2 == 0 ? a_{i+1} : a_i)$$$

          Let's say we replace $$$i + 2$$$ with $$$i + 1$$$:

          $$$dp_{i+1,1}=max(dp_{i+1,1},max(dp_{i,0},dp_{i,1})+ (i \% 2 == 0 ? a_{i+1} : a_i)$$$

          What happens when $$$i$$$ is even?

          Spoiler

          Anyways, there's only so much words can convey. If you're still confused, I recommend just plugging an example into the formula and seeing what happens. Most of your doubts can probably be answered that way.