Spaces:
Running
Running
| Idea: BledDest | |
| **Tutorial** | |
| The operations described in the statement are kinda similar to the identities for Fibonacci numbers, so maybe the solution will be connected to them. | |
| Let's assign each chip placement a weight: if chips are placed in points $$$x_1, x_2, \dots, x_n$$$ (repeating if multiple chips are in the same position), the weight of this placement is $$$f_{x_1} + f_{x_2} + \dots + f_{x_k}$$$, where $$$f_i$$$ is the $$$i$$$-th Fibonacci number ($$$f_1 = f_2 = 1$$$; $$$f_{i+2} = f_i + f_{i+1}$$$). | |
| We can show that two placements can be transformed into each other if and only if their weights are identical. First of all, the operations described in the statement don't change the weight, so two placements with different weights cannot be transformed into each other. To show how to transform two placements with identical weight into each other, let's bring them into "canonical" form as follows: | |
| while there is a chip with coordinate $$$i > 2$$$, convert it into two chips with coordinates $$$i-1$$$ and $$$i-2$$$; | |
| if all remaining chips are in points $$$1$$$ and $$$2$$$, move all chips from $$$2$$$ to $$$1$$$. | |
| After performing this sequence of actions, we will transform a placement of chips into the form "all chips are in point $$$1$$$, and the number of these chips is equal to the weight of the placement". And since all operations we apply are invertible (for every operation, there is an operation which "rolls it back"), we can transform any placement to any other placement with the same weight through this "canonical form". | |
| So, instead of counting the placements, let's group them according to their weights and work with them. For every possible weight of a placement (which is an integer from $$$1$$$ to $$$f_x \cdot n$$$), we need to answer two questions: | |
| Is it true that the minimum cost of a placement of this weight is exactly $$$m$$$? | |
| How many placements with this weight are there? | |
| The former is simple: this is just checking that the minimum number of Fibonacci numbers used to represent an integer is equal to $$$m$$$. We can precalculate this minimum number of Fibonacci numbers to represent each integer with a simple dynamic programming. | |
| The latter is a bit more tricky: we need to count the number of ways to represent the given number as a sum of exactly $$$n$$$ Fibonacci numbers from $$$f_1$$$ to $$$f_x$$$, where the order of these Fibonacci numbers does not matter. There are different ways to calculate it, the model solution uses a dynamic programming which uses $$$O(f_x \cdot n^2 \cdot x)$$$ time and $$$O(f_x \cdot n^2)$$$ memory. | |
| Let $$$dp_{i,j}$$$ be the number of ways to partition the integer $$$i$$$ into $$$j$$$ Fibonacci numbers. Initially, we will consider the situation when we can't use any Fibonacci numbers, so $$$dp_{0,0} = 1$$$ and everything else is $$$0$$$. And then we will "add" Fibonacci numbers one by one, so first we will update our dynamic programming in such a way that we can only use $$$f_1$$$; then, only $$$f_1$$$ and/or $$$f_2$$$; and so on. | |
| Let's show how to "update" our dynamic programming when we can use a new number $$$k$$$ in partitions. The simple way to do this is as follows: for every $$$dp_{i,j}$$$, iterate on the number $$$c$$$ of new elements we will use, and get a partition of integer $$$i + c \cdot k$$$ into $$$j+c$$$ numbers. However, that is too slow. | |
| Instead, let's iterate on the states of our dynamic programming in ascending order of $$$i$$$, and in each state, add at most one element to the partition (so, increase $$$dp_{i+k,j+1}$$$ by $$$dp_{i,j}$$$). At the first glance, it only allows us to use one element equal to $$$k$$$; however, when we consider the state $$$dp_{i+k,j+1}$$$ we updated, it will already store both the partitions which didn't use elements equal to $$$k$$$, and the partitions which used at least one element equal to $$$k$$$ (which came from the state $$$dp_{i,j}$$$); and by transitioning from $$$dp_{i+k,j+1}$$$ to $$$dp_{i+2k,j+2}$$$, we will "expand" all these partitions. | |
| If the previous paragraph is a bit unclear to you, you can try viewing it as a three-state dynamic programming of the form "let $$$dp_{i,j,k}$$$ be the number of partitions of $$$i$$$ into $$$j$$$ Fibonacci numbers from $$$f_1$$$ to $$$f_k$$$", where we dropped the third state of our dynamic programming in favor of maintaining only one layer and being more memory efficient. | |
| **Solution (BledDest)** |