Ball Sorting
Contest: Codeforces Round 876 (Div. 2)
Difficulty rating: 2100
Tags: data structures, dp, sortings

There are $$$n$$$ colorful balls arranged in a row. The balls are painted in $$$n$$$ distinct colors, denoted by numbers from $$$1$$$ to $$$n$$$. The $$$i$$$-th ball from the left is painted in color $$$c_i$$$. You want to reorder the balls so that the $$$i$$$-th ball from the left has color $$$i$$$. Additionally, you have $$$k \ge 1$$$ balls of color $$$0$$$ that you can use in the reordering process.

Due to the strange properties of the balls, they can be reordered only by performing the following operations:

1. Place a ball of color $$$0$$$ anywhere in the sequence (between any two consecutive balls, before the leftmost ball or after the rightmost ball) while keeping the relative order of other balls. You can perform this operation no more than $$$k$$$ times, because you have only $$$k$$$ balls of color $$$0$$$.
2. Choose any ball of non-zero color such that at least one of the balls adjacent to him has color $$$0$$$, and move that ball (of non-zero color) anywhere in the sequence (between any two consecutive balls, before the leftmost ball or after the rightmost ball) while keeping the relative order of other balls. You can perform this operation as many times as you want, but for each operation you should pay $$$1$$$ coin.

You can perform these operations in any order. After the last operation, all balls of color $$$0$$$ magically disappear, leaving a sequence of $$$n$$$ balls of non-zero colors.

What is the minimum amount of coins you should spend on the operations of the second type, so that the $$$i$$$-th ball from the left has color $$$i$$$ for all $$$i$$$ from $$$1$$$ to $$$n$$$ after the disappearance of all balls of color zero? It can be shown that under the constraints of the problem, it is always possible to reorder the balls in the required way.

Solve the problem for all $$$k$$$ from $$$1$$$ to $$$n$$$.

Input format:
The first line contains integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases. The descriptions of the test cases follow.

The first line contains one integer $$$n$$$ ($$$1 \le n \le 500$$$) — the number of balls.

The second line contains $$$n$$$ distinct integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le n$$$) — the colors of balls from left to right.

It is guaranteed that sum of $$$n$$$ over all test cases doesn't exceed $$$500$$$.

Output format:
For each test case, output $$$n$$$ integers: the $$$i$$$-th ($$$1 \le i \le n$$$) of them should be equal to the minimum amount of coins you need to spend in order to reorder balls in the required way for $$$k = i$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case there are $$$n = 6$$$ balls. The colors of the balls from left to right are $$$[\, 2, 3, 1, 4, 6, 5 \,]$$$.

Let's suppose $$$k = 1$$$. One of the ways to reorder the balls in the required way for $$$3$$$ coins:

$$$[\, 2, 3, 1, 4, 6, 5 \,]$$$ $$$\xrightarrow{\, 1 \,}$$$ $$$[\, 2, 3, 1, 4, \color{red}{0}, 6, 5 \,]$$$ $$$\xrightarrow{\, 2 \,}$$$ $$$[\, 2, 3, \color{blue}{4}, 1, 0, 6, 5 \,]$$$ $$$\xrightarrow{\, 2 \,}$$$ $$$[\, \color{blue}{1}, 2, 3, 4, 0, 6, 5 \,]$$$ $$$\xrightarrow{\, 2\,}$$$ $$$[\, 1, 2, 3, 4, 0, 5, \color{blue}{6} \,]$$$

The number above the arrow is the operation type. Balls inserted on the operations of the first type are highlighted red; balls moved on the operations of second type are highlighted blue.

It can be shown that for $$$k = 1$$$ it is impossible to rearrange balls in correct order for less than $$$3$$$ coins.

Let's suppose $$$k = 2$$$. One of the ways to reorder the balls in the required way for $$$2$$$ coins:

$$$[\, 2, 3, 1, 4, 6, 5 \,]$$$ $$$\xrightarrow{\, 1 \,}$$$ $$$[\, 2, 3, 1, 4, 6, \color{red}{0}, 5\,]$$$ $$$\xrightarrow{\, 2 \,}$$$ $$$[\, 2, 3, 1, 4, 0, 5, \color{blue}{6}\,]$$$ $$$\xrightarrow{\, 1 \,}$$$ $$$[\, 2, 3, \color{red}{0}, 1, 4, 0, 5, 6 \,]$$$ $$$\xrightarrow{\, 2 \,}$$$ $$$[\, \color{blue}{1}, 2, 3, 0, 4, 0, 5, 6\,]$$$

Note that this sequence of operations is also correct for $$$k$$$ greater than $$$2$$$.

It can be shown that for $$$k$$$ from $$$2$$$ to $$$6$$$ it is impossible to rearrange balls in correct order for less than $$$2$$$ coins.

In the second test case the balls are already placed in the correct order, so answers for all $$$k$$$ are equal to $$$0$$$.

Example input:
3
6
2 3 1 4 6 5
3
1 2 3
11
7 3 4 6 8 9 10 2 5 11 1

Example output:
3 2 2 2 2 2 
0 0 0 
10 5 4 4 4 4 4 4 4 4 4

Editorial:
Let's solve the problem for some fixed $$$k$$$.
Consider the set $$$S$$$ of all balls that were never moved with operation of type $$$2$$$. Let's call balls from $$$S$$$ fixed and balls not from $$$S$$$ mobile.
The relative order of fixed balls never changes, so their colors must form an increasing sequence.
Let's define $$$f(S)$$$ as the number of segments of mobile balls that the fixed balls divide sequence into. For example, if $$$n = 6$$$ and $$$S = \{ 3, 4, 6 \}$$$, then these segments are $$$[1, 2], [5, 5]$$$ and $$$f(S)$$$ is equal to $$$2$$$.
As every mobile ball has to be moved at least once, there must be at least one zero-colored ball in each such segment, whicn means that $$$f(S) \le k$$$. Also, it means that we will need at least $$$n - |S|$$$ operations of type $$$2$$$.
In fact, we can always place mobile balls at correct positions with exactly $$$n - |S|$$$ operations. The proof is left as exercise for reader.
So the answer for $$$k$$$ is equal to minimum value of $$$n - |S|$$$ over all sets $$$S$$$ of balls such that $$$f(S) \le k$$$ and the colors of balls in $$$S$$$ form an increasing sequence. This problem can be solved with dynamic programming: let $$$dp_{i, j}$$$ be maximum value of $$$|S|$$$ if only balls from $$$1$$$ to $$$i$$$ exist, ball $$$i$$$ belongs to $$$S$$$ and $$$f(S)$$$ is equal to $$$j$$$. To perform transitions from $$$dp_{i, j}$$$ you need to enumerate $$$t$$$ —the next ball from $$$S$$$ after $$$i$$$. Then, if $$$t = i + 1$$$, you transition to $$$dp_{t, j}$$$, otherwise you transition to $$$dp_{t, j + 1}$$$. After each transition $$$|S|$$$ increases by $$$1$$$, so you just update $$$dp_{t, j / j + 1}$$$ with value $$$dp_{i, j} + 1$$$.
There are $$$O(n^2)$$$ states and at most $$$n$$$ transitions from each state, so the complexity is $$$O(n^3)$$$.
Solution can be optimized to $$$O(n^2 \log{n})$$$ with segment tree, but this was not required.