PROBLEM LINK:Author: Gautam Saluja PROBLEMFind the minimum total energy lost to reach the cell [x, y, z] from the cell [0, 0, 0] in 3dimensional space. The energy loss is determined by the following rules:
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”. EXPLANATIONLet’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+yz$ 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 Csteps Chef makes. Obviously, $r$ ranges from $0$ to $x$. If Chef makes exactly $r$ such steps, then he needs to reach the cell $(xr,yr,zr)$ 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 nonnegative 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.
This question is marked "community wiki".
asked 12 Dec '17, 21:18

is there any proof for (x+y–z–1,x+y–z) that why these will work? answered 14 Dec '17, 22:56

In the Subtask 2 solution, how to reason about the case where A=B=C? Thanks answered 16 Dec '17, 06:03

Can you please explain the parity part? Why are we checking for r = x1 too? Thanks. answered 18 Dec '17, 17:16

What does COMMON denote in the author's solution? answered 27 Dec '17, 00:56
