LCH15CD - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Pavel Sheftelevich
Tester: Roman Rubanenko
Editorialist: Paweł Kacprzak

DIFFICULTY:

Easy Medium

PREREQUISITES:

DP, Implementation

PROBLEM:

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.

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++):

  • 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[i] 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[i]

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

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.
Tester’s solution can be found here.

RELATED PROBLEMS:

2 Likes
2

good question, I wasn’t able to write DP in time.

3
3 Likes
4

@pavel1996 what is the get function in your code?

5

@sherwin21990: we calculate dp result for each cell in cube. Each cell has coordinate vector with coordinates between 0 and D-1. 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.

6

Can you tell me why my code fails. I know I haven’t used DP but still I didn’t get what am I doing wrong. Can anyone please help me. Here is the link to my solution.

7

The key to this problem is that transformation from a n-dimensional 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 forward-dp (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.

1 Like
8

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

9

@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?

10

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 )
{
pos[i]–;
mint = min( mint, rec(pos) );
pos[i]++;
}
Author’s code with above modification leads to AC

11

@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 (3-based numeral system) == 12 decimal and correspondent cell will be dp[12]. If you still don’t get it try to google numeral systems.

@dragonemperor: sure, it can be done without recursion and many contestants did it. In my opinion recursive representation of dp is often easier to understand and implement.

If we don’t have dXdXd structure we can use just some kind of map from a vector to int or maybe usual array, but we should have some function(like get in author’s solution) that converts a vector to int and guarantees that different cells correspond to different keys in a map or an array.

1 Like
12

@pavel1996 In author’s solution, if I use int for dp[1<<16] instead of long long, I am getting WA only for first sub-task 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

13

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:d-1 which can be very large since the value of d can be 2^16. hope it Helps!!!

1 Like
14

Thanks. I didn’t think of that

15

What is the constraint on D? How is it supposed to be inferred from the problem statement?

16

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.

17

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- n-2 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

18

@code_overlord: max D=pow(65536,1/N)

maximum cells are 2^16=65536.

For N dimensions,for maximum value of D, DDD…n times=65536 or max D=nth root of 65536.

19

we can skip the calls for cost evaluation by maintaing sum and xor value separately…and when we subtract 1…then sum=sum-1…xor=xor^value^(value-1)
https://www.codechef.com/viewsolution/7494686