# Sorting Problem

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)?

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)$.

• Mj[1]= minimum cost of using S1 to reset exactly 1 register.what is the value of Mj[1] if S1=2? and also S1,S2..Sn are sorted? – akshay May 2 '13 at 19:51
• @akshay: If it is not possible, the cost is $\infty$. They need not be sorted. – Aryabhata May 2 '13 at 20:52