Indian National Olympiad in Informatics

Related:
Online Programming Contest, 2-3 April, 2005

IARCS home > OLYMPIAD

Advanced Division

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][2]=1) {
	 	H[1]=1;
		H[2]=2;
             }
         else  {
	        H[1]=2;
		H[2]=1;
	    }
	    Present[1]=1;
	    Present[2]=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]] = 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.

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