### Online Programming Contest, 2-3 April, 2005

Solution to Problem 2: Rank Fraud

```Let the ministers be M_1, M_2, ... M_N. The task of the prime
minister is to order them as M_i1, M_i2, ... M_iN such that for
each j, M_ij beat M_i{j+1} in the table-tennis tournament.

As mentioned earlier, the description of the problem as a set
(the set of Ministers) and a binary relationship (who beat who)
suggests the use of graphs in solving this problem. Let the
vertices of the graph be { 1, 2, 3, ..., N } representing the N
ministers with a directed edge from i to j if j beats i in the
table-tennis tournament.

For instance, if the results of the matches between 4 ministers
are as follows: Minister 1 beat ministers 2 and 4, Minister 2
beats none, Minister 3 beat ministers 1 and 2, and Minister 4
beat ministers 2 and 3.  The graph representing these results
would look like:

--------------------------
|                          |
1 <-------------  2 --     |
^                 |   |    |
|       ----------    |    |
|      |              |    |
|      |              |    |
4 <-------------  3 <------

Examining this graph we can conclude that 2 loses to 3, 3 loses
to 4 and 4 loses to 1 and thus 2, 3, 4, 1 would be a possible
order in which the prime minister could present the ministers to
the king.

Thus out aim is to find a path through the directed graph that
includes all the vertices (note that by definition any vertex can
appear at the most once in any path). Such a path is called a ``
Hamiltonian Path ''.  There are no known algorithms that can
compute or even check if a given graph contains a Hamiltonian
path efficiently. It is believed that any algorithm to solve this
problem will take at least 2^N steps where N is the number of
vertices in the graph.

However, the graph that is obtained from the results of the
table-tennis tournament has a special feature --- for each pair
of vertices i and j there is exactly one edge involving the two
of them, either from i to j or from j to i. Such a directed graph
is called a ``Tournament'' (since the results of round-robin
tournaments, such as the above, produce such graphs).  It turns
out that first of all, every tournament does have a Hamiltonian
path and secondly, such a path can be calculated quite
efficiently. Let us see how.

We construct paths of length i for each i < N. We may pick any
edge in the tournament to get a path of length 1. Pick any path
of length i-1, say v_1,v_2,v_3, ..., v_i.  We show that it can be
extended to a path of length i. Pick any vertex v that does not
appear among v_1, v_2, ... v_i.  Since i<N, such a vertex always
exists.

1) If the edge between v and v_1 (recall there must be one,
by the definition of a tournament) is from v to v_1 then our
desired path is v, v_1, ..., v_i.

2) Otherwise, if the edge between v and v_i is from v_i to v then
our desired path is v_1, v_2, ... v_i, v.

3) Otherwise the situation is as follows:

v_1 ---->  v_2 ----> v_3    ...     v_{i-1} ----> v_i
|                                                 ^
|                                                 |
-----------------------> v ----------------------

We scan right from v_1 to v_i to find the first vertex v_j
such that the edge between v and v_j is oriented from v to
v_j. Such a vertex must exist (since the edge between v and
v_i is oriented from v to v_i, there is at least one and
thus there must be a left most and this left most is not
v_1).  For this j, we have edges v_{j-1} -----> v and v
-----> v_j. Then,

v_1 ----> v_2 ----> ... v_{j-1} ----> v ----> v_j ... ----> v_i

is a path of length i.  Thus, starting with any edge, one
can successively construct paths of length 2,3, and so on
up to N-1.  Thus, we can construct a Hamiltonian path.

How efficiently can this algorithm be implemented?

In each iteration, we need to find a vertex that is not already
in the path and insert it in the appropriate position. This can
be done in time proportional to N. There are N-2 insertions and
thus, this algorithm can be implemented in time proportional to
N*N. The details are as follows:

--------------------------------------------------------------------------

/* We assume that the graph is stored as an adjacency matrix
A.  */

/* Initialise H with a path of length 1 */
If (A=1) {
H=1;
H=2;
}
else  {
H=2;
H=1;
}
Present=1;
Present=1;

for i = 2 to N-1 do {

for k = 3 to N do {
if (Present[j]=0) break;
}

/* k is vertex that has not been inserted yet. */
/* so insert it. *

if (G[k][H] = 1) then
insert k at the beginning of H

else if (G[H[i]][k] = 1)
insert k at the end of H

else { /* case 3. find the position j to insert k */

for j=1 to N
if (G[k][j] = 1) break;

insert k between the (j-1)st and jth elements
currently in H

}

Present[k] = 1

}

Print out the array H.

-------------------------------------------------------------------------

```

Copyright (c) IARCS 2003-2020;   Last Updated: 10 Nov 2005