Editorial for COCI '21 Contest 2 #4 Magneti
Submitting an official solution before solving the problem yourself is a bannable offence.
Define the length of a permutation of magnets as the least number of adjacent slots used for placing the magnets in that order without attracting each other. Say that the order of the magnets is fixed and that the length of the permutation is
For the first subtask, the length of each permutation of magnets is
For the second subtask, it's possible to go over each permutation of the magnets, for each one calculate its length and the number of ways to arrange the remaining slots. The total complexity of this is
For the entire solution, we use dynamic programming to calculate for each
We sort the magnets by increasing radius and build the permutation with the following dp:
number of ways to arrange the first magnets in groups such that the sum of the lengths of the groups is .
One group represents a segment of the permutation that is being built and is comprised of magnets and the least amount of empty space between them. The transition of the dp actually consists of adding a new magnet to one of the groups, which can be done in three ways:
- creating a new group that is made just from this magnet,
- adding a magnet to one of the ends of one of the already existing groups, or
- connecting two existing groups by placing the new magnet between them
The number of permutations which have length
Comments