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

• Aryabhata: There is latex (mathjax) support on this site. Please try to use it. (Perhaps this is of some use: meta.cs.stackexchange.com/questions/271/…)

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

• akshay: 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?
• Aryabhata: @akshay: If it is not possible, the cost is $\infty$. They need not be sorted.