MARRAYS (Dynamic programming)

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

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.

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.

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[i][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[i][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[i][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{aligned} dp[i][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{aligned}
\begin{aligned} dp[i][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{aligned}
\begin{aligned} dp[i][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{aligned}

Now look at what we got. To think of it intuitively, for dp[i][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[i] = \max_{0 \le k < M_i} \{ -(i+1) \cdot A_{i,k} + dp[i][k+1] \} \\ dp_2[i] = \max_{0 \le k < M_i} \{ +(i+1) \cdot A_{i,k} + dp[i][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[i][j] = \max(+i \cdot A_{i,j} + dp_1[i-1], -i \cdot A_{i,j} + dp_2[i-1])

After computing all dp[i][j] for each dish i we can compute dp_1[i] and dp_2[i] 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[i][j], the maximums can be computed on the fly. Hope this was clear, please ask in case of any doubts.

6 Likes

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

1 Like

I canā€™t understand the third equation.

@meooow i dont understand this part

dp[i][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!

@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.

1 Like