DP problem

655_DiV_2_E

can anyone help me out with this problem ?? faced difficulty to understand the editorial.

First of all, that problem statement is really difficult to understand. The example should only be supplementary which in this case it definitely isn’t.

As for the editorial:

First we ignore that intervals belong to rows. We just see them as individual intervals, but know that there are at most N intervals that contain a given column.
Now dp_{l,r} contains the value of the best assignment if we consider only intervals that are fully contained within the interval [l,r].

Now consider the best assignment of ones for a given interval. There will be a column k in that interval that has the maximum number of one’s (though there might be more that have the same number of ones).

Claim: In the optimal solution all intervals containing the column k with the most ones will have it’s one placed in column k.

Proof: Suppose not, then there is an optimal assignment with an interval whose one is placed in another column p. Let c_p be the number of ones in column p and similarly c_k for column k. Therefore the contribution of these columns is c_p^2+c_k^2. If instead the one was in column k then these columns would contribute (c_p-1)^2+(c_k+1)^2=c_p^2+c_k^2-2c_p+2c_k+2. Then because per definition c_p\leq c_k this new value will be strictly larger than with the one in column p. Therefore the assignment with the one in column p was not optimal giving a contradiction.

To find the value of any dp_{l,r} we exploit this fact. We guess for each column k that it will be the column with the most ones. Then each interval containing column k will have it’s one already used up. We are left with all intervals lying entirely in [l,k-1] or [k+1,r] for which we already have the answers: dp_{l,k-1} and dp_{l,k+1}. Our dp recurrence will be:

dp_{l,r}=\max_{k\in[l,r]}(dp_{l,k-1}+\{\text{\# intervals [a,b] with $l\leq a\leq k\leq b\leq r$}\}+dp_{k+1,r})
1 Like