MARRAYS (Dynamic programming)

marrays

#1

Hey i am not able to understand the editorials solution . The solution i intially came up with is also based on dynamic programming but i got a TLE . Can some one help me with it!

link


#2

Not quite sure but I’ve passed the problem with a similar algorithm except for reusing the DP array.
https://www.codechef.com/viewsolution/15799713
(See GetAns())

Probably generating whole 2D array is taking time with your solution.


#3

For first 2 subtasks, those are cases with very small N and number of ingredients ~{10}^{6}. If you directly start from max or min dish of dish 1, 3 out of 4 TLE will be removed. I am still trying to figure out how to remove the last TLE.


#4

If x is the total number of ingredients and two adjacent dishes have \approx x/2 ingredients each, that is the worst case scenario where complexity would be \mathcal{O}(x^2). And since x \le 10^6, this approach should give TLE. But the test cases are weak so many such solutions in faster languages like C++ have passed.

I can attempt to explain the editorial’s approach.
For the i^{th} dish, let M_i be the number of ingredients in it and A_{i,j} be the tastiness of the j^{th} ingredient. From your solution I understand that you are using dp*[j] to store the answer for dishes 0..i with j as the first ingredient in the i^{th} dish. You are calculating

\DeclareMathOperator{\abs}{abs} dp*[j] = \max_{0 \le k < M_{i-1}} \{ \abs(A_{i,j}-A_{i-1,k})\cdot i + dp[i-1][k+1] \}

Now let’s try to separate the A_{i,j} and A_{i-1,k} terms using the fact that \abs(x) = \max(x, -x).

dp*[j] = \max_{0 \le k < M_{i-1}} \{ \max(A_{i,j}-A_{i-1,k}, -A_{i,j}+A_{i-1,k})\cdot i + dp[i-1][k+1] \} \\ \begin{align} dp*[j] = \max_{0 \le k < M_{i-1}} \{ \max(&+i \cdot A_{i,j} - i \cdot A_{i-1,k} + dp[i-1][k+1], \\ &-i \cdot A_{i,j} + i \cdot A_{i-1,k} + dp[i-1][k+1] ) \}\ \end{align}
\begin{align} dp*[j] = \max(&\max_{0 \le k < M_{i-1}} \{+i \cdot A_{i,j} - i \cdot A_{i-1,k} + dp[i-1][k+1] \}, \\ &\max_{0 \le k < M_{i-1}} \{-i \cdot A_{i,j} + i \cdot A_{i-1,k} + dp[i-1][k+1] \} ) \end{align}
\begin{align} dp*[j] = \max(&+i \cdot A_{i,j} + \max_{0 \le k < M_{i-1}} \{ - i \cdot A_{i-1,k} + dp[i-1][k+1] \}, \\ &-i \cdot A_{i,j} + \max_{0 \le k < M_{i-1}} \{ + i \cdot A_{i-1,k} + dp[i-1][k+1] \} ) \end{align}

Now look at what we got. To think of it intuitively, for dp*[j] we get two choices, we can keep A_{i,j} positive or negative. If we keep A_{i,j}, the first element of the i^{th} dish, positive we should add it to the maximum of - i \cdot A_{i-1,k} + dp[i-1][k+1] where the last element of the previous dish A_{i-1,k} was kept negative, and vice versa.

The inner max terms only depend on i, so let’s say

dp_1* = \max_{0 \le k < M_i} \{ -(i+1) \cdot A_{i,k} + dp*[k+1] \} \\ dp_2* = \max_{0 \le k < M_i} \{ +(i+1) \cdot A_{i,k} + dp*[k+1] \}

dp_1 is where we keep the last dish A_{i,k} negative, and in dp_2 we keep it positive. Then finally

dp*[j] = \max(+i \cdot A_{i,j} + dp_1[i-1], -i \cdot A_{i,j} + dp_2[i-1])

After computing all dp*[j] for each dish i we can compute dp_1* and dp_2* which will be used for the next dish.

The complexity is now \mathcal{O}(x). If you have understood this far then you’ll also realize that there is no need to store each dp*[j], the maximums can be computed on the fly. Hope this was clear, please ask in case of any doubts.


#5

We can keep A*[j] positive or negative what does it mean ,A*[j] is always positive as given in constraints ,please explain


#6

I can’t understand the third equation.


#7

@meooow i dont understand this part

dp*[j] = max(+i⋅Ai,j+max0≤k<Mi−1{−i⋅Ai−1,k+dp[i−1][k+1]},−i⋅Ai,j+max0≤k<Mi−1{+i⋅Ai−1,k+dp[i−1][k+1]})
Thank really for taking the time and explaining it to me!


#8

@beginner_1111 I mean that in the sense that when we say \abs(a-b) = \max(+a-b, -a+b), then in one of the terms a is “kept positive” and in the other negative.
@underdog_eagle and @phantomhive I have added an intermediate step, is it better now? First the inner and outer max are swapped and then since the i \cdot A_{i,j} term is independent of k we can take it out of the inner max.