← All solutions

Shortest judge solution: 1396 bytes. Shortest team solution (during contest): 1531 bytes.

Let us write x₀ , . . . , x_n−1 for the sizes, S(i, j) for the minimum number of operations needed to assemble the dolls in positions i, i + 1, . . . , j − 1 to a single group (not necessarily consisting of consecutive dolls), and M(i ) for the minimum number of operations to assemble the dolls in positions i, i + 1, . . . , n − 1 into complete sets (consisting of consecutive dolls). Finally let us say that an interval (i, j) is ok if x_i , . . . , x_j−1 is a permutation of the integers from 1 to ( j − i ).

What we seek is then M (0). We can write the following recurrence for M (i ), with base case M (n) = 0.

M(i ) = min S(i, j) + M ( j).
        j∈{i +1,...n}
         (i, j) is ok

Thus with access to S(i, j), computing the M(·) function can be done in O(n² ) time using dynamic programming.

Computing the S(·, ·) values is another dynamic programming exercise. The optimal way of combining the dolls in the interval has as last operation the combination of a group consisting of the dolls from i to k − 1 with a group consisting of the dolls from k to j − 1 for some k between i + 1 and j − 1 (inclusive), so we can write the following recursion when j ≥ i + 2 (the base case when j < i + 2 is left as an exercise):

S(i, j) = min S(i, k ) + S(k, j) + C (i, k, j),
         i <k< j

where C (i, k, j) is the cost of combining a group [ x_i , . . . , x_k−1 ] with the group [ x_k , . . . , x_j−1 ]. The cost C (i, k, j) can be computed as follows: if the group that contains the smallest dolls contains the t smallest dolls among x_i , . . . , x_j−1 , then C (i, k, j) = j − i − t (because we have to open all but those t smallest dolls in order to combine the two groups).

If implemented naively, this leads to an O(n⁴ ) solution which is too slow, but with a little care the recursion for S(·, ·) can be implemented to give an O(n³ ) solution.