You are given a n-dimensional cube of size d in which you have to find the cheapest way to get from (0, 0, …, 0) to (d-1, d-1, …, d-1) in such a way that that you can move from point a to b if b differs from a in exactly one coordinate by 1 and the sum of coordinates of a is less than the sum of coordinates of b while the cost of visiting a point a = (a0, a1, …, an-1) equals (a0 ^ a1 ^ … ^ an-1) * (a0 + a1 + … + an-1) where ^ denotes the XOR operation.
This is a multidimensional version of a very classic dynamic programming problem. Let b be a point in the cube and let PREV be a set of points from b can be reached. The cheapest way to reach b is the cheapest way to reach a point from PREV plus the cost of visiting b and the cost of reaching (0, 0, 0, …, 0) equals 0 by the definition.
If you read the quick explanation you know that the only difficulty here is the implementation, but first let me go through the idea in details again.
Let divide out the cube in layers, layer* consists of all points for which the sum of its coordinates equals i. Clearly there are exactly n * d layers, because there are n coordinates and for each one there are d possible values. From the statement we know that in one move we can go from any point in layer* to any point in layer[i + 1]. The goal is start in the first layer which contains only the point (0, 0, 0, …, 0) and to reach the one and only point in the last layer in the cheapest way. If you are familiar with dynamic programming you know already how to solve it: iterate over layers starting in the lowest one and while we are in layer* we iterate over all points in it and update the cheapest way of reaching all reachable points in layer[i + 1] from the current point.
I really encourage you to implement a solution, because if you haven’t done it yet, you can learn a few useful techniques in this type of problems.
Here are a few tips (for exact implementation please check solutions section down below, there is a tester solution in java and mine in c++):
represent points as numbers in base d. This allows you to iterate easily over them and to extract coordinates from representation very straightforward.
define a simple mapping from a point a = (a0, a1, …, an-1) to a point which has exactly one, let’s say i-th coordinate, bigger by 1 than a. You can check for this mapping in tester’s solution, where he compute a deg array which helps to move between these points using only one addition
in this problem, it’s easier to update a result in layer[i + 1] while being in layer* which is an opposite technique to a standard dynamic programming approach where you would update a result for layer[i + 1] while being in it and iterating over all points in layer*
remember to define the initial results for each point in a cube first. It should be the INFINITY value for all points but (0, 0, 0, …, 0) which has a cost of reaching it 0
Time complexity here is O(d^n * n) because there are d^n cells in a cube and we perform O(n) atomic operations for each of them.
Subtasks can be solved using the similar dynamic programming approach but they are easier to implement if N = 1 or N = 2. For example, if N = 1 you are basically moving along a line and each layer contains exactly one point.