Sorting Problem

Question

I have come across the following problem.

You have $N$ registers, numbered $1,2,\dots, N$, each of which can hold an integer value. You are given the initial values of the registers, which have the property that every number from $1, \dots, N$ occurs exactly once among the $N$ registers.

Each register has a "reset button": pressing the reset button on register $i$ changes its value to $i$.

In one move you can pick any subset of the registers (say, registers $3, 5, 9$) and simultaneously press all their reset buttons.

However you must ensure that every number from $1,2,\dots, N$ continues to occur exactly once amongst the $N$ registers.

The cost of a move that resets $m$ registers simultaneously is $m^2$.

You can perform a sequence of such moves one after the other, and the total cost is the sum of the costs of the individual moves.

Register $i$ is said to be stable if it contains the value $i$. Given a target $K$, where $K \le N$, the goal is to perform a sequence of moves at the end of which at least $K$ registers are stable.

Find the minimum possible cost for achieving this.

My attempt on problem:

Let $A[1, \dots, n]$ be given registers with initial values.

1. Divide $A$ into Disjoint Sets 
2. For each disjoint set maintain the number of elements in it. 
3. Find the minimum operations from these subsets(explained below with example)

Example:

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

Initial Value: 11 3  6  9  8  4  1  5  10  2  7

and $K=7$

Since Every number should be in the register we need to reset set of registers as shown below.

We can Reset $1,11,7$ in a single RESET operation.

Similarly we can reset $2,3,6,4,9,10$ and $5,8$ in a single RESET operation.

So we now have $3$ disjoint subsets of $A$

Let

$S_1=\{1,11,7\}$, note that $|S1|=3$

$S_2=\{2,3,6,4,9,10\}$, $|S2|=6$

$S_3=\{5,8\}$ and $|S3|=2$

So Minimum number of operations for $K=7$ is $(6^2+2^2)=40$.

Now we need to find minimum number of oprations form these three subset.

more formally Given $S=\{S_1, S_2, \dots, S_n\}$ we need to find Subset $\{S_{i_1},S{i_2}, \dots, S_{i_p}\}$ such that

$\sum_{j=1}^{p} S_{i_j} \ge K $ and $\sum_{j=1}^{p} S_{i_j}^2$ is as minimum as possible.

How to efficiently find the minimum number of operations from these subsets?

Any Alternative solution(s)?

Answer 1

You have it right so far.

btw, the disjoint sets you are talking about are called cycles of the permutation.

An $O(n^2)$ time dynamic programming algorithm (for the problem you state at the end) works as follows:

We compute the arrays $M_j[1 \dots n]$ such that $M_j[L]$ contains the minimum cost of using $S_1, S_2, \dots, S_j$ (your notation) to reset exactly $L$ registers in total. Note: exactly $L$, and if some exact $L$ is not possible to achieve, you set it to $\infty$.

$M_{j+1}$ can be computed, given $M_{j}$ and $S_{j+1}$, in $O(n)$ time using:

$$M_{j+1}[L] = \min\; \{M_j[L]\;,\; M_j[L-S_{j+1}] + S_{j+1}^2\}$$

In the end, given your target of at least $K$, you find the minimum among $$M_{n}[K], M_{n}[K+1], \dots, M_{n}[n]$$

By reusing the array, the space usage can be made $O(n)$.