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!

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

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

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 is where we keep the last dish A_{i,k} negative, and in dp_2 we keep it positive. Then finally

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.

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

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.