Editorial for COCI '21 Contest 2 #4 Magneti

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
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 $d$ $d$ . If the length of the permutation is greater than $l$ $l$ , then it's impossible to place the magnets on the board in that order. If the length of the permutation is less than or equal to $l$ $l$ , then what's left is to arrange the remaining $l-d$ $l - d$ empty slots among the magnets so that there are a total of $l$ $l$ slots on the board. Each of these $l-d$ $l - d$ remaining empty slots can be arranged among $n+1$ $n + 1$ "gaps" in the array, that is either before all magnets or after all magnets or between any two adjacent magnets. The number of ways to arrange these empty slots can be calculated with a combinatorial trick called Stars and bars and it equals $\binom{l-d+n}{n}$ $(\binom{l - d + n}{n})$ .

For the first subtask, the length of each permutation of magnets is $(n-1) \cdot r + 1$ $(n - 1) \cdot r + 1$ (if $r$ $r$ denotes the radius of activity of the magnets), so the answer is $n! \cdot \binom{l-(n-1) \cdot r-1+n}{n}$ $n! \cdot (\binom{l - (n - 1) \cdot r - 1 + n}{n})$ . The binomial coefficients can be precomputed using Pascal's triangle.

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 $\mathcal O(n! \cdot n)$ $O (n! \cdot n)$ .

For the entire solution, we use dynamic programming to calculate for each $d$ $d$ between $1$ $1$ and $l$ $l$ how many permutations have length $d$ $d$ , and then multiply this number by $\binom{l-d+n}{n}$ $(\binom{l - d + n}{n})$ .

We sort the magnets by increasing radius and build the permutation with the following dp:

$dp[i][j][d] =$ $d p [i] [j] [d] =$ number of ways to arrange the first $i$ $i$ magnets in $j$ $j$ groups such that the sum of the lengths of the groups is $d$ $d$ .

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 $d$ $d$ will be stored in $dp[n][1][d]$ $d p [n] [1] [d]$ (all of the magnets are in a single group of length $d$ $d$ ). The time complexity of this solution is $\mathcal O(n^2 \cdot l)$ $O (n^{2} \cdot l)$ because there are $n \cdot n \cdot l$ $n \cdot n \cdot l$ states and the transitions are calculated in $\mathcal O(1)$ $O (1)$ .

Comments

There are no comments at the moment.