You are not logged in. Please login at www.codechef.com to post your questions!

×

MARRAYS (Dynamic programming)

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

phantomhive's gravatar image

4★phantomhive
944
accept rate: 0%


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.

link

answered 17 Oct '17, 13:25

meooow's gravatar image

6★meooow ♦
7.0k718
accept rate: 48%

edited 17 Oct '17, 17:52

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) beginner_11114★

I can't understand the third equation.

(17 Oct '17, 14:25) underdog_eagle4★

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

(17 Oct '17, 15:43) phantomhive4★
1

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

(17 Oct '17, 17:28) meooow ♦6★

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.

link

answered 17 Oct '17, 08:18

yambe2002's gravatar image

4★yambe2002
1
accept rate: 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.

link

answered 17 Oct '17, 10:22

vijju123's gravatar image

4★vijju123 ♦♦
15.2k11859
accept rate: 18%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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