February 14, 2011 at 12:35Dynamic programming. Match Model
Hello, Habrahabr. In this, afterwards I want to talk about dynamic programming using the example of solving one of the problems. I recently ran into this task on the portal of Olympiad problems (the link is indicated at the end). Immediately get down to business.
Professor Samodelkin decided to make a three-dimensional model of the cubes from matches using matches for the edges of the cubes. The edge length of each cube is equal to one match.
To build a model of three dice, he used 28 matches.
What is the smallest number of matches Samodelkin needs to build a model of N cubes?
All numbers in the problem do not exceed 2 · 10 9 .
Specifications
Input
One number N - the number of cubes.
Output
One number - the number of matches.
I solved this problem using dynamic programming, but it could be solved in other ways, and even just with one formula - which we will derive at the end.
“However, among exhaustive and some other problems, one can distinguish a class of problems that have one good property: having solutions to some subproblems (for example, for a smaller number n), it is possible to find a solution to the original problem almost without enumeration.” - A class of problems that are solved by dynamic programming .
And our goal is to achieve a solution, according to the description of dynamic programming tasks, in which the solution for the current parameters is based on the solution of the previous ones.
I divided this task into 3 stages:
And so we establish the conditions of the problem:
We need to find out the minimum number of matches that is needed to build a line of N squares with a side of 1 match. To store the result, I will use the DP array . Now we look at the figure and fill this array with numbers that need to be added to the solution for the i-1 case:
And the answer for N is the sum of the elements of the DP array from 0 to N , and we immediately see the pattern - for DP [1]: = 4 , DP [> 1]: = 3
and derive the formula (N is always> 1, i.e., natural ):
Result (N) : = SUM (DP 1 -> DP N ) = 4+ (N-1) * 3
Problem:
We need to find out the minimum number of matches that is needed to build squares with a side in 1 match. You can build in 2 dimensions. In 2D, we have a new problem: what size plane does A x B need to strive to minimize the number of matches? And as many have guessed, this is of course a square. But not everything is so simple, there you need to simplify this idea. If you look at the figure above, you can see that the most favorable position for the new square will be that which has more neighbors, and in the best case, it will be 2 neighbors. That is, the best case will be to build like this: We can easily tell where to build the next cube if we do it with our hands, but how can we tell the computer about it?
If we take a piece of paper and begin to build a certain plane from a square to minimize the number of edges, we will notice how we build:
Initially, it was a 1x1 - 1 square, then we extend it to 2x1 - 2 squares, then:
2x2 - 3 and then 4
3x2 squares - 5 and 6 squares
3x3 - 7.8.9 squares
Take a close look and see the pattern: we have an A x B plane to minimize the number of edges, the next ones to build a plane will be (A + 1) x B and then (A + 1) x (B + 1), the latter is a square, as we begin to build from 1 x 1
We write a table for I have a DP array:
We analyze the table:
for DP [1] = 4
further, when we add a new row, we make a new square using 3 matches and until the end of the row we complete the squares of 2 matches. Still not what does not remind Recall the case with 1D - the first square is 4 matches, the rest are 3, in this case this is the same additional row, but with the initial square of 3 matches and the rest in 2 matches.
Now the solution algorithm: or so: And the formula: Result (N) : = 4 + 3 * (the number of full squares that are up to the number N without 1 + additional numbers that go before the full squares) + 2 * (everything else) N SQRT : = int (sqrt (N)) - 1 N ADD : = N SQRT + 1 (if N <= N SQRT * (N SQRT +1)) Result (N) : = 4 + 3 * (N SQRT + N ADD ) + 2 * (NN SQRT -N ADD )
Here we have reached the 3D case.
In the three-dimensional case, to minimize the number of matches for building, now, cubes need to strive to build a large cube, but in intermediate cases it will be:
A x B x C -> (A + 1) x B x C -> (A + 1) x (B + 1) x C -> (A + 1) x (B + 1) x (C + 1)
the solution algorithm will be the same as in the 2D case, but considering some new features:
1D (N): = 5+ (N-1) * 3
2D (N): = algorithm described above in the subsection, but with adjustment - 2D (1): = 8
3D (N): = algorithm described above in 2D case, but taking into account three-dimensionality - 3D (1): = 12, and when the coordinates increase, we will change the result so: Result: = Result + 2D ( A * B * C / max (A, B, C)), i.e., it will be necessary to get 2D from the size of the added plane by changing the parameter of our new box
And the formula for 3D The
formula will consist of the same parts as the formula for 2D, but we will also take into account not only full squares but also full Cubes
Result (N) : = 12 + 8 * (3 * N full cubes + (0 or 1 or 2 depending on N)) + 5 * (2 * N full squares + (0 or 1 depending on N)) + 3 * N else
But, unfortunately, this formula is not entirely correct and requires more mental effort to thinking over some exceptions and amendments.
In the previous sections, we examined what the minimization of matches for for a cube / square depends on and based on this we can make an algorithm for any measurement:
We need to take into account how many matches the initial N-dimensional square consists of and calculate how many matches it takes to complete new elements.
Fascination algorithm we derived the dimensions of the object - at each iteration, increase by 1 the smallest dimension.
They also realized that when changing the size of an object, the value of the function of the (N-1) -th measurement from the size of the added plane
B should be added to the result when creating the formula, you need to take into account the number of numbers in the N degree, N-1, N-2, etc. + take into account features
E-olimp - An Internet portal for the organizational and methodological support of distance programming olympiads for gifted youth of educational institutions of Ukraine.
A task on the portal that you can try to pass - registration is required
Article on dynamic programming
Task
Professor Samodelkin decided to make a three-dimensional model of the cubes from matches using matches for the edges of the cubes. The edge length of each cube is equal to one match.
To build a model of three dice, he used 28 matches.
What is the smallest number of matches Samodelkin needs to build a model of N cubes?
All numbers in the problem do not exceed 2 · 10 9 .
Specifications
Input
One number N - the number of cubes.
Output
One number - the number of matches.
I solved this problem using dynamic programming, but it could be solved in other ways, and even just with one formula - which we will derive at the end.
“However, among exhaustive and some other problems, one can distinguish a class of problems that have one good property: having solutions to some subproblems (for example, for a smaller number n), it is possible to find a solution to the original problem almost without enumeration.” - A class of problems that are solved by dynamic programming .
And our goal is to achieve a solution, according to the description of dynamic programming tasks, in which the solution for the current parameters is based on the solution of the previous ones.
Decision
I divided this task into 3 stages:
- Solve the problem for the 1D case and in it I will use a square with a side in 1 match, derive the formula
- Solve the problem for the 2D case and in it I will use a square with a side of 1 match, derive the formula
- Find patterns in the 1D and 2D case and based on them solve the problem for the 3D case, derive the formula for the 3D case
- Thoughts on the n-dimensional case
1D
And so we establish the conditions of the problem:
We need to find out the minimum number of matches that is needed to build a line of N squares with a side of 1 match. To store the result, I will use the DP array . Now we look at the figure and fill this array with numbers that need to be added to the solution for the i-1 case:
| N: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| DP: | 0 | 4 | 3 | 3 | 3 | 3 | 3 | 3 |
And the answer for N is the sum of the elements of the DP array from 0 to N , and we immediately see the pattern - for DP [1]: = 4 , DP [> 1]: = 3
and derive the formula (N is always> 1, i.e., natural ):
Result (N) : = SUM (DP 1 -> DP N ) = 4+ (N-1) * 3
2D
Problem:
We need to find out the minimum number of matches that is needed to build squares with a side in 1 match. You can build in 2 dimensions. In 2D, we have a new problem: what size plane does A x B need to strive to minimize the number of matches? And as many have guessed, this is of course a square. But not everything is so simple, there you need to simplify this idea. If you look at the figure above, you can see that the most favorable position for the new square will be that which has more neighbors, and in the best case, it will be 2 neighbors. That is, the best case will be to build like this: We can easily tell where to build the next cube if we do it with our hands, but how can we tell the computer about it?
If we take a piece of paper and begin to build a certain plane from a square to minimize the number of edges, we will notice how we build:
Initially, it was a 1x1 - 1 square, then we extend it to 2x1 - 2 squares, then:
2x2 - 3 and then 4
3x2 squares - 5 and 6 squares
3x3 - 7.8.9 squares
Take a close look and see the pattern: we have an A x B plane to minimize the number of edges, the next ones to build a plane will be (A + 1) x B and then (A + 1) x (B + 1), the latter is a square, as we begin to build from 1 x 1
We write a table for I have a DP array:
| N | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| The size | 1 x 1 | 2 x 1 | 2 x 2 | 2 x 2 | 3 x 2 | 3 x 2 | 3 x 3 | 3 x 3 | 3 x 3 |
| DP | 4 | 3 | 3 | 2 | 3 | 2 | 3 | 2 | 2 |
We analyze the table:
for DP [1] = 4
further, when we add a new row, we make a new square using 3 matches and until the end of the row we complete the squares of 2 matches. Still not what does not remind Recall the case with 1D - the first square is 4 matches, the rest are 3, in this case this is the same additional row, but with the initial square of 3 matches and the rest in 2 matches.
| N for 2D | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| N for 1D | 1 | 1 | 1 | 2 | 1 | 2 | 1 | 2 | 3 |
| The size | 1 x 1 | 2 x 1 | 2 x 2 | 2 x 2 | 3 x 2 | 3 x 2 | 3 x 3 | 3 x 3 | 3 x 3 |
| DP | 4 | 3 | 3 | 2 | 3 | 2 | 3 | 2 | 2 |
Now the solution algorithm: or so: And the formula: Result (N) : = 4 + 3 * (the number of full squares that are up to the number N without 1 + additional numbers that go before the full squares) + 2 * (everything else) N SQRT : = int (sqrt (N)) - 1 N ADD : = N SQRT + 1 (if N <= N SQRT * (N SQRT +1)) Result (N) : = 4 + 3 * (N SQRT + N ADD ) + 2 * (NN SQRT -N ADD )
DP[1]=4
A=1
B=1 // A x B плоскость
теперь нужно проходить от 1 до N и в это же время увеличивать A и B как я писал выше а также еще проходить по массиву DP но для 1D случая начиная сначала при каждом изменении A и B и идти до наибольшего из них:
j=1 // счетчик для DPfor1D, к тому же не забываем что теперь DPfor1D={3,2,2,2,2,2,2,2,...}
for i = 2 -> N
begin
if A*B
then begin
(A
j=1
end
DP[i]:= DP[i-1]+DPfor1D[j]
j++
end
Result:= 4
newN:= 1
A:= 2
B:= 1
while newN <= N
begin
Result:= Result + 1D(min(A,B)) // 1D(N):=3+(N-1)*2 если N >= 1, иначе 0
(A
newN=A*B
end
(A>B)?A--:B--
Result:= Result+ 1D(N-A*B)
3D
Here we have reached the 3D case.
In the three-dimensional case, to minimize the number of matches for building, now, cubes need to strive to build a large cube, but in intermediate cases it will be:
A x B x C -> (A + 1) x B x C -> (A + 1) x (B + 1) x C -> (A + 1) x (B + 1) x (C + 1)
the solution algorithm will be the same as in the 2D case, but considering some new features:
1D (N): = 5+ (N-1) * 3
2D (N): = algorithm described above in the subsection, but with adjustment - 2D (1): = 8
3D (N): = algorithm described above in 2D case, but taking into account three-dimensionality - 3D (1): = 12, and when the coordinates increase, we will change the result so: Result: = Result + 2D ( A * B * C / max (A, B, C)), i.e., it will be necessary to get 2D from the size of the added plane by changing the parameter of our new box
And the formula for 3D The
formula will consist of the same parts as the formula for 2D, but we will also take into account not only full squares but also full Cubes
Result (N) : = 12 + 8 * (3 * N full cubes + (0 or 1 or 2 depending on N)) + 5 * (2 * N full squares + (0 or 1 depending on N)) + 3 * N else
But, unfortunately, this formula is not entirely correct and requires more mental effort to thinking over some exceptions and amendments.
Thoughts on the n-dimensional case
In the previous sections, we examined what the minimization of matches for for a cube / square depends on and based on this we can make an algorithm for any measurement:
We need to take into account how many matches the initial N-dimensional square consists of and calculate how many matches it takes to complete new elements.
Fascination algorithm we derived the dimensions of the object - at each iteration, increase by 1 the smallest dimension.
They also realized that when changing the size of an object, the value of the function of the (N-1) -th measurement from the size of the added plane
B should be added to the result when creating the formula, you need to take into account the number of numbers in the N degree, N-1, N-2, etc. + take into account features
References
E-olimp - An Internet portal for the organizational and methodological support of distance programming olympiads for gifted youth of educational institutions of Ukraine.
A task on the portal that you can try to pass - registration is required
Article on dynamic programming
