PROBLEM LINK:Author: Pavel Sheftelevich DIFFICULTY:Easy Medium PREREQUISITES:DP, Implementation PROBLEM:You are given a ndimensional cube of size d in which you have to find the cheapest way to get from (0, 0, ..., 0) to (d1, d1, ..., d1) 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 = (a_{0}, a_{1}, ..., a_{n1}) equals (a_{0} ^ a_{1} ^ ... ^ a_{n1}) * (a_{0} + a_{1} + ... + a_{n1}) where ^ denotes the XOR operation. QUICK EXPLANATION: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. EXPLANATION: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[i] 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[i] 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[i] 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++):
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. ALTERNATIVE SOLUTION: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. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. RELATED PROBLEMS:
This question is marked "community wiki".
asked 25 Jan '15, 14:19

The key to this problem is that transformation from a ndimensional point to a number in base D.You can also use a map declared < cell , int >,where cell is a class of form a[10] (for every dimension we have a coordinate). But I know that there is some problem with maps and classes/structs ,and it is easier if we transform the coordinates in a number :D. Helpful problem and editorial :). But I don't think that forwarddp (the one in which we are in layer[i] and update layer[i+1]) is a good aproach,maybe if we sort the queue by values,like a dijkstra. answered 25 Jan '15, 17:34

@sherwin21990: I think examples can be heplful. If n = 4 and d = 2 then each cell has binary coordinate vector like (1, 0, 1, 1). We can consider this binary vector as binary number and 1011 binary == 11 in decimal number system. That means that we will store dp value for cell (1, 0, 1, 1) in dp[11]. If d = 3 and n = 3 then example (1, 2, 0) > 120 (3based numeral system) == 12 decimal and correspondent cell will be dp[12]. If you still don't get it try to google numeral systems.
answered 25 Jan '15, 20:08

@sherwin21990: we calculate dp result for each cell in cube. Each cell has coordinate vector with coordinates between 0 and D1. To store results in array we convert this vector to a number(just imagine that this vector is a number in D number system). That helps us avoid writing a lot of for loops for each possible N. answered 25 Jan '15, 16:24

@pavel1996 Is the get function a formula?what is the logic behind converting n point vector into a number? Is there any material on this topic? I can't understand it. answered 25 Jan '15, 17:54

@pavel1996 Can we do it without recursion? I mean in similar problem in 2D, we just find the cost of reaching a point as the minimum of the point in top and point in left. Can we use a similar approach Here? Also, representing number in base D works if both side of each dimension is D. What will happen if instead of nXdXd structure, we have nXdXe structure? answered 25 Jan '15, 19:48

In author's solution, there is no need of the line dp[id] = inf; as we are always visiting some previous dp position and hence it is always either visited or set to 1. Also there is no need for using another vector go. We can also use it as if ( pos[i] > 0 ) answered 25 Jan '15, 20:02

@pavel1996 In author's solution, if I use int for dp[1<<16] instead of long long, I am getting WA only for first subtask and AC for rest two. How can it be? I mean when n=1, I should get AC and as n increases, there would be overflow and we would get WA. Correct me if I am wrong answered 25 Jan '15, 20:42
1
If n=1, then the ans would be the sum of i*i(because there would be only one term so xor=term and sum=term) for i=1:d1 which can be very large since the value of d can be 2^16. hope it Helps!!!
(25 Jan '15, 21:46)
Thanks. I didn't think of that
(26 Jan '15, 00:38)

What is the constraint on D? How is it supposed to be inferred from the problem statement? answered 28 Jan '15, 19:13

I have a doubt in the explanation its written that there are n*d layers. How this can be suppose n=2 and d=3 so possible coordinates are (0,0),(0,1),(1,0),(0,2),(1,1),(1,1),(2,0),(1,2),(2,1)and (2,2) our aim is to reach 2,2 so there are only four layers layer[0],layer[1],layer[2], layer[3] and layer[4] please explain.
link
This answer is marked "community wiki".
answered 31 Jan '15, 12:31

Time complexity here is O(d^n * n) since total no of cells id n*d how ? can someone please explain with an example. ex n2 d=3 so possible coordinates are[0,0],[0,1],[1,0],[0,2],[2,0],[1,1],[1,2],[2,1] and [2,2] so total no of coordinates 9 similarly n=2,d=4 total no of coordinates 16 not 8 please explain
link
This answer is marked "community wiki".
answered 31 Jan '15, 12:42

@code_overlord: max D=pow(65536,1/N) answered 02 Apr '15, 01:06

we can skip the calls for cost evaluation by maintaing sum and xor value separately...and when we subtract 1...then sum=sum1....xor=xor^value^(value1) https://www.codechef.com/viewsolution/7494686 answered 18 Jul '15, 02:18

good question, I wasn't able to write DP in time.
http://discuss.codechef.com/questions/62643/mosthorriblecodeeverwrittenbyme