Блог пользователя AyanoGod

Автор AyanoGod, 4 года назад, По-английски

Hello, Hope you are doing well.

Problem link: https://codeforces.me/problemset/problem/1373/D Author's Editorial: https://codeforces.me/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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Didn't got what you mean by this.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.