PROBLEM LINK:
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:
- 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.
- 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.
- 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.