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