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.