×

# MMC - Editorial

Author: Michael Nematollahi
Tester: Teja Vardhan Reddy
Editorialist: Michael Nematollahi

DP

# EXPLANATION:

1_ $d_0[r][cnt]$ is equal to the minimum time required to eat $cnt$ cheese wedges from the first $(r-1)$ rows and getting to the first column of the $r^{th}$ row.

2_ $d_1[r][cnt]$: similar to $d_0$ except you need to get to the last column of the $r^{th}$ row.

3_ $ans[r][cnt]$ is equal to the minimum time required to eat $cnt$ cheese wedges from the first $r$ rows.

4_ $c_0[1][r][cnt]$ is equal to the minimum time required to start from the first column of the $r^{th}$ row and go to the right and eat $cnt$ of the cheese wedges on the $r^{th}$ row.

5_ $c_0[2][r][cnt]$ is equal to the minimum time required to start from the first column of the $r^{th}$ row and go to the right and eat $cnt$ of the cheese wedges on the $r^{th}$ row and get back to the first column.

6_ $c_1[1][r][cnt]$ is the same as $c_0[1][r][cnt]$ except that it's for the last column.

7_ $c_1[2][r][cnt]$ is the same as $c_0[2][r][cnt]$ except that it's for the last column.

8_ $z[r][cnt]$ is equal to the minimum sum of $cnt$ cheese wedges from row $r$.

9_ $g[r]$ is equal to the number of cheese wedges on row $r$.

Alright, now we're done with definitions. The answer to the problem would be stored in $ans$. So all that's left is to calculate these arrays. Here we go through them one by one and explain how you can calculate them:

1_ $d_0[r][cnt] = \min(\min_{0 \leq i \leq g[r-1]} (d_0[r-1][cnt-i]+1+c_0[2][r-1][i]), \min_{0 \leq i \leq g[r-1]} (d_1[r-1][cnt-i]+m+z[r-1][i])$. If we ignore the rows with no cheese on them, the complexity of this part would be $O(K^2)$.

The first part of the min function above is for the case where we eat $cnt-i$ wedges from the first $r-2$ rows, climb up from the first column and reach row $r-1$, eat $i$ wedges from the $(r-1)^{th}$ row, come back to the first column and then go up.
The second part is for the case where we do the same thing as the first case, except that we climb up to row $r-1$ from the last column.

2_ Similar to 1.

3_ $ans[r][cnt] = \min (ans[r-1][cnt], \min_{1 \leq i \leq g[r]} (d_0[r][cnt - i] + c_0[1][r][i]), \min_{1 \leq i \leq g[r]} (d_1[r][cnt-i] + c_1[1][r][i]))$. If we ignore the rows that don't have any cheese on them, the complexity of this part would be $O(K^2)$.

The first part of the min function above is for the case where we take the wedges from the first $r-1$ rows.
The second part is for the case where we climb up to the $r^{th}$ row from the first column and eat $i$ wedges from the row.
The third part is for the case where we climb up the $r^{th}$ row from the last column and eat $i$ wedges from the row.

4_ The answer depends on the position of the rightmost cheese wedge we eat on this row. Let's loop over this rightmost cheese. Assume that the wedges on row $r$ are numbered from left to right. Assume the rightmost wedge we eat is the $i^{th}$ one. It's easy to see that if we want to eat $cnt$ wedges, it's best to eat the $cnt$ wedges with minimum $t$ amongst these $i$ wedges. This observation gives us the following solution:

Let $i$ be the rightmost cheese wedge we eat. Sort the first $i$ wedges and set $c_0[1][r][cnt] = \min (c_0[1][r][cnt], pt[cnt])$ where $pt$ is the partial sum array over the sorted cheese wedges. Note that since we have the sorted array for the first $i-1$ wedges, the sorting can be done in $O(i)$. Hence, this part of the solution runs in $O(g[r]^2)$, which leads to the overall complexity of $O(K^2)$ over all rows.

5_ Similar to 4.

6_ Similar to 4.

7_ Similar to 5.

8_ To calculate $z[r][cnt]$, we can sort the cheese wedges on row $r$ based on $t$(the time required to eat a wedge). Then, $z[r][cnt]$ would be equal to the sum of the first $cnt$ $t$s. If we ignore the rows that have no cheese on them, this array can be calculated in $O(K \times log(K))$.

The total complexity of this solution is $O(K^2)$. Refer to the setter's solution to see the implementation.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

7★watcher
35
accept rate: 0%

19.8k350498541

 1 I have found that the reason for the NZEC was simply that the output buffer was too small. You can find the revised submission at https://www.codechef.com/viewsolution/22751148 where I have also changed some of the function names for clarity and added more explanatory comments. answered 02 Feb, 08:22 4★david_s 111●1 accept rate: 11%
 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:

×15,683
×2,172
×39

question was seen: 322 times

last updated: 02 Feb, 08:22