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

×

CHEFUNI - Editorial

3
2

PROBLEM LINK:

Practice
Contest

Author: Gautam Saluja
Tester: Mugurel Ionut Andreica
Editorialist: Kirill Gulin

PROBLEM

Find the minimum total energy lost to reach the cell [x, y, z] from the cell [0, 0, 0] in 3-dimensional space. The energy loss is determined by the following rules:

  1. Going from [p, q, r] to [p+1, q, r] or [p, q+1, r] or [p, q, r+1] takes $A$ units of energy.
  2. Going from [p, q, r] to [p+1, q+1, r] or [p, q+1, r+1] or [p+1, q, r+1] takes $B$ units of energy.
  3. Going from [p, q, r] to [p+1, q+1, r+1] takes $C$ units of energy.

QUICK EXPLANATION:

For each test case let $x \leq y \leq z$. Solve the problem in $O(1)$ time if steps only of the first two types are allowed. Now we can solve a test case in $O(x)$ time by fixing how many steps of the third type we use. For solving it in $O(1)$ time notice there is no need to check all values, only a few of them are “interesting”.

EXPLANATION

Let’s call moves of the first, the second and the third type as $A$-moves, $B$-moves and $C$-moves respectively.

First, reorder the coordinates in such a way that $x \leq y \leq z$. Obviously, the answer will not change since reordering a pair of coordinates and making some move is equivalent if we do not reorder anything and make other step of the same type by the principle of symmetry.

Now imagine moves only of the $A$ and $B$ types are available. Let’s solve the problem in this case and denote the answer for the cell $(x, y, z)$ as $f(x, y, z)$. For instance suppose if $x < 0$ then $f(x, y, z)$ is $\infty$ (like $10^{18}$). Now there are two possible cases: $2a \leq b$ and $2a > b$. In the first case, it is unprofitable to do $B$-move since it can be replaced by two $A$-moves. Therefore, in this case we use only $A$-moves and the answer is $A \cdot (x + y + z)$. In the second case, it is profit to make as many steps of the second type as possible. Suppose $z \leq x + y$. Then we can reach $(x,y,z)$ cell only with $B$-steps if $x + y + z$ is even (by making steps in $(x, z)$ and $(y, z)$ direction in total $z$ times and the remaining $(x, y)$ steps $x+y-z$ times) or do one $A$-step making this sum even. Otherwise, we can make only $x + y$ $B$-steps and $z – x – y$ remaining $A$-steps.

Subtask 1 solution.

The first way. Let’s calculate dynamic programming $dp[i][j][k]$ – minimum loss of energy need to reach cell $(i,j,k)$. Obviously, $dp[0][0][0] = 0$. It’s very easy to calculate such dp if you know the idea of dynamic programming. From any cell $(i,j,k)$ we can reach any of the cells $(i+1, j, k)$, $(i,j+1,k)$,$(i,j,k+1)$ with $dp[i][j][k] + A$ energy, any of the cells $(i+1,j+1,k)$, $(i,j+1,k+1)$,$(i+1,j,k+1)$ with $dp[i][j][k] + B$ energy and the cell $(i+1,j+1,k+1)$ with $dp[i][j][k] + C$ energy. Just update the appropriate states of $dp$ and print $dp[x][y][z]$. Time complexity per testcase is $O(xyz)$.

The second way uses the subproblem above. Let’s try each number $r$ of C-steps Chef makes. Obviously, $r$ ranges from $0$ to $x$. If Chef makes exactly $r$ such steps, then he needs to reach the cell $(x-r,y-r,z-r)$ with only the first two types of moves with extra $r \cdot C$ energy. All you need is to choose the minimum such value over all possible $r$. Time complexity per testcase is $O(x)$.

Subtask 2 solution.

Let’s upgrade the second solution of subtask 1 by thinking what “interesting” values of $r$ can be used instead of checking all of them. Let’s look at the function $f$. It depends on values of $A$ and $B$. If $B$ is quite expensive or $C$ is very cheap it’s better to make $C$-step as many times as possible and $r = x$ (and also you should check $r = x – 1$ since $f$ depends on parity of $x + y + z$, it’s just a corner case). If $C$ is quite expensive, it is better to do not make $C$-steps at all, so $r = 0$ (and $r = 1$ because of the parity) in this case. If $A$ is expensive then we want to make $C$-step as much times as possible with an ability to don’t make $A$-steps at all. As mentioned in function $f$ description it’s possible if $z \leq x + y$. So $r = x + y – z$ (and $r = x + y – z – 1$) for this case.

So instead of checking all possible values choose $r$ only from the set $\{0, 1, x + y – z – 1, x + y – z, x – 1, x\}$ (only non-negative values).

Time complexity per test is $O(1)$ hence the overall time complexity is $O(T)$.

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

asked 12 Dec '17, 21:18

kefaa's gravatar image

6★kefaa
1138
accept rate: 0%

edited 16 Dec '17, 19:40

srd091's gravatar image

5★srd091
1.6k111


is there any proof for (x+y–z–1,x+y–z) that why these will work?

link

answered 14 Dec '17, 22:56

anno's gravatar image

4★anno
266211
accept rate: 12%

In the Subtask 2 solution, how to reason about the case where A=B=C? Thanks

link

answered 16 Dec '17, 06:03

ryuxin's gravatar image

3★ryuxin
1
accept rate: 0%

Can you please explain the parity part? Why are we checking for r = x-1 too? Thanks.

link

answered 18 Dec '17, 17:16

harshmmodi's gravatar image

6★harshmmodi
243110
accept rate: 0%

What does COMMON denote in the author's solution?

link

answered 27 Dec '17, 00:56

kishu18_agar's gravatar image

4★kishu18_agar
21
accept rate: 0%

why my solution getting wr?

link

answered 02 Jan '18, 12:46

gautamcse27's gravatar image

2★gautamcse27
375
accept rate: 0%

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:

×15,497
×188
×19

question asked: 12 Dec '17, 21:18

question was seen: 2,470 times

last updated: 02 Jan '18, 12:46