Problem from a programming competition

[rohanprabhu]

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.

 

[rcgldr]

The goal is to figure out the minimum number of in place swaps, but I'm assuming there's no limitation on using more memory than than to figure out the optimal swap sequence. Since there are only 3 numbers, 1, 2, 3, create a 3 entry array, and count up the number of each that there is in the list. In this example, there are two "1", three "2", and four "3", which will be the sorted order. Then create 3 arrays of indexes for all the numbers that are "out of place", the first array would be the indexes of all the "1"s out of place, the next array would be the out of place "2"s, and the third array the out of place "3"s. In your example there are two numbers "in place", a "3" in position 6, and a "3" in position "8", so they don't get added to the list.

The arrays would look like this:

out of place "1"s: 3 9
out of place "2"s: 1 2 7
out of place "3"s: 4 5

Look for swaps that move two numbers into their proper zone first, then for swaps that move one number into it's proper zone. If the same index is not used more than once, than the order doesn't matter. "1 3" "2 9" "4 7" "5 9" will work for your example.

So the algorithm is to look for "1" and "2" swaps that move both into correct zone, look for "1" and 3" swaps that move both into correct zone, look for "2" and "3" swaps that move both into correct zone, which are the optimal swaps. Then look for swaps that move "1" into correct zone, and "2" into correct zone, which will automatically leave the "3"'s in the correct zone. Note that if the same index is not used more than once, the swap sequence is optmized, and the order doesn't matter. Your example doesn't show this case so I made a new one:

2 3 1 2 3 3 2 3 1

Counts: 2 "1"s, 3 "2s", 4 "3"s

out of place "1"s: 3 9
out of place "2"s: 1 4 7
out of place "3"s: 2 5

original:: 2 3 1 2 3 3 2 3 1
swap "1 3" 1 3 2 2 3 3 2 3 1
swap "2 9" 1 1 2 2 3 3 2 3 3
swap "5 7" 1 1 2 2 2 3 3 3 3

There may be times where the same index has to be used twice to do a rotate:

original:: 1 2 1 2 3 2 3 1 3
swap "2 8" 1 1 1 2 3 2 3 2 3
swap "5 8" 1 1 1 2 2 2 3 3 3

 

[rohanprabhu]

thanks a lot mate.. we had just thought upto the part of making an array of the no. of instances each number occurs in the given list... though we then restarted on some silly logic and never got there.

thanks again..