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! asked 16 Oct '17, 22:55

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. Now let's try to separate the $A_{i,j}$ and $A_{i1,k}$ terms using the fact that $\abs(x) = \max(x, x)$. $$dp[i][j] = \max_{0 \le k < M_{i1}} \{ \max(A_{i,j}A_{i1,k}, A_{i,j}+A_{i1,k})\cdot i + dp[i1][k+1] \} \\ \begin{align} dp[i][j] = \max_{0 \le k < M_{i1}} \{ \max(&+i \cdot A_{i,j}  i \cdot A_{i1,k} + dp[i1][k+1], \\ &i \cdot A_{i,j} + i \cdot A_{i1,k} + dp[i1][k+1] ) \}\ \end{align} $$ $$ \begin{align} dp[i][j] = \max(&\max_{0 \le k < M_{i1}} \{+i \cdot A_{i,j}  i \cdot A_{i1,k} + dp[i1][k+1] \}, \\ &\max_{0 \le k < M_{i1}} \{i \cdot A_{i,j} + i \cdot A_{i1,k} + dp[i1][k+1] \} ) \end{align} $$ $$ \begin{align} dp[i][j] = \max(&+i \cdot A_{i,j} + \max_{0 \le k < M_{i1}} \{  i \cdot A_{i1,k} + dp[i1][k+1] \}, \\ &i \cdot A_{i,j} + \max_{0 \le k < M_{i1}} \{ + i \cdot A_{i1,k} + dp[i1][k+1] \} ) \end{align} $$ 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_{i1,k} + dp[i1][k+1]$ where the last element of the previous dish $A_{i1,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[i1], i \cdot A_{i,j} + dp_2[i1])$$ 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. answered 17 Oct '17, 13:25
1
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
(17 Oct '17, 14:03)
I can't understand the third equation.
(17 Oct '17, 14:25)
@meooow i dont understand this part
(17 Oct '17, 15:43)
1
@beginner_1111 I mean that in the sense that when we say $\abs(ab) = \max(+ab, a+b)$, then in one of the terms $a$ is "kept positive" and in the other negative.
(17 Oct '17, 17:28)

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. answered 17 Oct '17, 08:18

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. answered 17 Oct '17, 10:22
