You are invited to Log in or Register a free Frihost Account!

Problem from a programming competition

rohan2kool
Today there was an inter-school programming competition and I was there on my school team. There were a set of four questions, out of which we were able to do 3. The 4th question was a bit difficult and thereby we couldn't solve it in the given amount of time. Now, i'd like help frm u guys.. this is the question:

1. A list is to be sorted in an ascending order. The sorting has to take place via swaps only. Meaning, if there are two elements a and b at positions p and q in a list L, a swap at p and q would mean that a would be at position q and b would be at position a.

However, the elements in the list can have the values '1', '2' or '3' only. In that case, for a given list, there exists a optimal sequence of swaps which will result in a sorted array. Write a program which computes the minimum number of swaps required for a given list and also displays the swaps.

INPUT
The input will consist of an integer(0 < n < 10000) on a line, which specifies the number of elements in the list. All elements are integers. This will be followed by n lines, each line holding an element of the list.

OUTPUT
First line of the output should contain the minimum number of swaps (m) required to sort the given list. This should be followed by m lines, each line showing the swaps in the format: position-a <space> position-b, where position-a and position-b are the respective positions of the swapped elements in the given list.

EXAMPLE
[input]
9
2
2
1
3
3
3
2
3
1

[output]
4
1 3
4 7
2 9
9 5

We had to do this in C++.. bt any language would be fine. What i'm actually looking for is an algorithm to go about finding the minimum no. of swaps required.
SonLight
 Quote: Write a program which computes the minimum number of swaps required for a given list and also displays the swaps.

Apparently, it doesn't matter how many computational steps it takes, as long as the number of swaps are minimized. In a real-life application, it would make sense to approach the problem assuming that, then try to minimize other operations, if needed. Usually in a sort, the operations are moves and comparisons. In this case, comparisons will be limited, but we may need some other logic.

First off, recognize that there are three sections of the data: the elements that will be 1 after swapping, the elements that will be 2, and the elements that will be 3.

let nt = total count
let e[i] be the i'th number

step 1: count the total number of 1's, 2's, and 3's in the data.
for (i = 1; i<=3; i++) n[i] = number of i's in data
[I will abbreviate n[i] as ni where i is digit or literal i]

step 2: determine how many are out of place
op = 0;
for (j=i; j<=n1; j++) op += (e[j] != 1);
for (j=n1+1; j<=n1+n2; j++) op += (e[j] != 2);
for (j=n1+n2+1; j<=nt; j++) op += (e[j] != 3);

Now op is the number out of place, and if op were always even and reprented pairs that could be exchanged, then the number of swaps would be op/2. In fact, there can be a cycle of 3 that needs to be exchanged:

nt = 3
3
1
2