Chef Monocarp
Contest: Educational Codeforces Round 97 (Rated for Div. 2)
Difficulty rating: 1800
Tags: dp, flows, graph matchings, greedy, math, sortings

Chef Monocarp has just put $$$n$$$ dishes into an oven. He knows that the $$$i$$$-th dish has its optimal cooking time equal to $$$t_i$$$ minutes.

At any positive integer minute $$$T$$$ Monocarp can put no more than one dish out of the oven. If the $$$i$$$-th dish is put out at some minute $$$T$$$, then its unpleasant value is $$$|T - t_i|$$$ — the absolute difference between $$$T$$$ and $$$t_i$$$. Once the dish is out of the oven, it can't go back in.

Monocarp should put all the dishes out of the oven. What is the minimum total unpleasant value Monocarp can obtain?

Input format:
The first line contains a single integer $$$q$$$ ($$$1 \le q \le 200$$$) — the number of testcases.

Then $$$q$$$ testcases follow.

The first line of the testcase contains a single integer $$$n$$$ ($$$1 \le n \le 200$$$) — the number of dishes in the oven.

The second line of the testcase contains $$$n$$$ integers $$$t_1, t_2, \dots, t_n$$$ ($$$1 \le t_i \le n$$$) — the optimal cooking time for each dish.

The sum of $$$n$$$ over all $$$q$$$ testcases doesn't exceed $$$200$$$.

Output format:
Print a single integer for each testcase — the minimum total unpleasant value Monocarp can obtain when he puts out all the dishes out of the oven. Remember that Monocarp can only put the dishes out at positive integer minutes and no more than one dish at any minute.

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

Note:
In the first example Monocarp can put out the dishes at minutes $$$3, 1, 5, 4, 6, 2$$$. That way the total unpleasant value will be $$$|4 - 3| + |2 - 1| + |4 - 5| + |4 - 4| + |6 - 5| + |2 - 2| = 4$$$.

In the second example Monocarp can put out the dishes at minutes $$$4, 5, 6, 7, 8, 9, 10$$$.

In the third example Monocarp can put out the dish at minute $$$1$$$.

In the fourth example Monocarp can put out the dishes at minutes $$$5, 1, 2, 4, 3$$$.

In the fifth example Monocarp can put out the dishes at minutes $$$1, 3, 4, 5$$$.

Example input:
6
6
4 2 4 4 5 2
7
7 7 7 7 7 7 7
1
1
5
5 1 2 4 3
4
1 4 4 4
21
21 8 1 4 1 5 21 1 8 21 11 21 11 3 12 8 19 15 9 11 13

Example output:
4
12
0
0
2
21

Editorial:
There are a lot of solutions for the problem. Let's start with the easiest one.
Sort the dishes in the non-decreasing order of their optimal time. I claim that there is an optimal answer such that the times $$$T$$$ for each dish go in the increasing order. That's not too hard to prove (something along the lines of if there are two dishes $$$i$$$ and $$$j$$$ such that $$$t_i < t_j$$$ and $$$T_i > T_j$$$, then $$$|t_i - T_i| + |t_j - T_j|$$$ is always greater than $$$|t_i - T_j| + |t_j - T_i|$$$).
So we can use dynamic programming to solve the task. Let $$$dp[i][T]$$$ be the minimum total unpleasant value if $$$i$$$ dishes are processed and the current minute is $$$T$$$. For the transitions you can either put out the current dish $$$i$$$ at the current minute $$$T$$$ or wait one more minute. Notice that you'll never need more time than $$$2n$$$ minutes (the actual constraint is even smaller, just consider the case with all dishes times equal to $$$n$$$).
So that dp works in $$$O(n^2)$$$.
The other possible solution is matching. Let's build the following graph. The left partition is $$$n$$$ vertices corresponding to dishes. The right partition is $$$2n$$$ vertices corresponding to minutes (as we saw in previous solution $$$2n$$$ is always enough). Now add the edges between all dishes and all minutes with the cost of their absolute different. Finally, find the minimum cost maximum matching. That can be done with MCMF or Hungarian algorithm.
Both should pass pretty easily.
There's also a solution in $$$O(n \log n)$$$ involving the slope trick.