FRIHOST FORUMS SEARCH FAQ TOS BLOGS COMPETITIONS
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

answer:
2 swaps
1 3
1 2

I suspect you need to know how many of each 'wrong' possibility is in each position. Then you have to minimize the swaps by pairing as many single-swaps as you can.

Non-trivial, indeed! I will see if anyone can give a 'nice' solution before I consider figuring out a complete answer (which would be clumsily done if I tried it right now).

Note: the number of swaps always lies between op/2 (all cycle-2's) and 2/3 * op (all cycle-3's).
Related topics
How To : Improve Your PHP Programming
Programming Help & Support Guidelines
Imagine Cup 2006
Math Equation Editor and Computer Algebra for Students
Job that u wouldn't mind doing for the rest of your life
Programming vs Career
HTML Forms Problem
Competition maniaco!
Programming in C problem
Programming
Looking for Moderators to Large Forum with Potential Success
Some challenges for the programmers out there
Could you help me with this competition?
Crypt Kicker
Reply to topic    Frihost Forum Index -> Scripting -> Others

FRIHOST HOME | FAQ | TOS | ABOUT US | CONTACT US | SITE MAP
© 2005-2011 Frihost, forums powered by phpBB.