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.
Consider reversing the subarray $$$a[l \dots r]$$$. The array is now split into three parts:
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.
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]);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}$$$.
Didn't got what you mean by this.
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?
Say for the sake of example, $$$dp_{i,1} > dp_{i,0}$$$ and the entire right argument is greater than $$$dp_{i+1,1}$$$, so $$$dp_{i+1,1} = dp_{i,1} + a_{i+1}$$$.
Now what happens when we transition from $$$dp_{i+1,1}$$$ to $$$dp_{i+2,1}$$$? Do you see how $$$a_{i+1}$$$ is added again?
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.