×

# MARRAYS (Dynamic programming)

 0 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 asked 16 Oct '17, 22:55 94●4 accept rate: 0%

 6 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{align} 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{align} \begin{align} 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{align} \begin{align} 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{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_{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. answered 17 Oct '17, 13:25 6★meooow ♦ 7.0k●7●18 accept rate: 48% 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 dp[i][j] = max(+i⋅Ai,j+max0≤k
 0 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 1 accept rate: 0%
 0 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 15.2k●1●18●59 accept rate: 18%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×23

question asked: 16 Oct '17, 22:55

question was seen: 655 times

last updated: 17 Oct '17, 17:52