Indian National Olympiad in Informatics

Related:
Online Programming Contest, 6-7 November, 2004

IARCS home > OLYMPIAD

Advanced Division

Solution to Problem 2: Treasure Hunt

At any point in his search for the treasure, Muttal has with him
a token and card. The card tells him which machine to go to and
the token is the one he is to insert into that machine. Since we
are given a table that tells us for each machine and token, what
would be his next machine and next token, knowing the current
token and current machine gives us a complete description of what
he would do in the future.

The naive solution simply simulates the actions of Muttal.

--------------------------------------------------------------
/* We assume that there are two 2-dimensional array Tok and Mac
   where Tok[i][j] is the token spat out by the ith machine when
   token j is inserted into it. Mac[i][j] is the machine number
   printed on the card spat out when token j is inserted into the
   ith machine */

        c-token=1        /* The current token is 1 
        c-machine=S      /* We begin with machine S

        for (i=2 to W)  {
               tmp-token = Tok[c-machine][c-token]
               tmp-machine=Mac[c-machine][c-token]
               c-token = tmp-token       /* get the next token*/
               c-machine = tmp-machine   /* get the next machine*/
              }
        print c-machine
-----------------------------------------------------------------

This algorithm takes time proportional to W. And as indicated in
the problem statment if W can be large (of the order of 10^9) and
then this is not good enough.

The observation that will help us cut this down considerably is
the following: Suppose the sequence of (Machine,Token) pairs that
Muttal goes through is given by

(m_1,t_1) (m_2,t_2) .... (m_k,t_k) (m_k+1,t_k+1) .... (m_n,t_n) ....

(where m_1 is S and t_1 is 1). Then

if m_k = m_n and t_k=t_n, the above sequence would actually like

(m_1,t_1) (m_2,t_2) ... (m_k,t_k)(m_k+1,t_k+1) ... 
   (m_k,t_k)(m_k+1,t_k+1) ... (m_k,t_k)...

Starting at machine m_k and with token t_k in hand if he ends up
at (m_k,t_k) again, he has no choice but to go through the same
sequence and end up (m_k,t_k) again and so on.

That is, his futile walk would look like

(m_1,t_1)(m_2,t_2)...(m_k-1,t_k-1) r r r r ...

where r = (m_k,t_k),(m_k+1,t_k+1) ... (m_n-1,t_n-1)

Let l be the length of r, that is l = n-k.  We know that the
machine reached at steps k, k+l, k+2l, ...  is m_k (and the token
on hand is t_k).  Similarly the machines reached at step k+1,
k+1+l, k+1+2l, ... is m_k+1 and so on.

Thus, for any N > k we can determine the machine reached as
follows: Let N = k+N'. The machine reached at set N is N' mod l.
Thus, it suffices to simulate Muttal's walk till we find a
repeating machine/token pair.

The question then is, how soon would a pair (m_k,t_k) repeat?
Notice that there are only |M| x |T| possible choices for (m,t).
So, no matter what the table (describing the next machine and next
token) looks like, within the first (|M| x |T| + 1) steps we are
guaranteed to find a repetition!

The algorithm incorporating the above idea is described below:

--------------------------------------------------------------
/* We assume that there are two 2-dimensional array Tok and Mac
   where Tok[i][j] is the token spat out by the ith machine when
   token j is inserted into it. Mac[i][j] is the machine number
   printed on the card spat out when token j is inserted into the
   ith machine */

        count = 1        /* To keep track of how many
                            (machine,token) pairs have been seen */
        c-token=1        /* The current token is 1 
        c-machine=S      /* We begin with machine S

        visited[count][0]=ctoken     /* store the pair */
        visited[count][1]=c-machine
        count=count+1

        for (i=2 to |M|*|T|+1)  {
               tmp-token = Tok[c-machine][c-token]
               tmp-machine=Mac[c-machine][c-token]
               c-token = tmp-token       /* get the next token*/
               c-machine = tmp-machine   /* get the next machine*/
               
               for (k=1 to count-1) { /* check if the pair has been seen
                    if ((visited[k][0]=c-token) and (visited[k][1]=c-machine)) {
                            /* if so we are done*/
                            l = count-k
                            j = (W - k) % l   /* m_j+k =  m_W, as discussed above
                            print (visited[j+k][1]) 
                            return
                     }
                 }
                /* if W is less that |M|*|T|+1 we will might find the
                   answer before the pair repeats */

                if (i = W) { 
                       print(c-machine) 
                       return
                }
        }
-----------------------------------------------------------------

The outer loop executes at most |M|*|T|+1 times and the inner
loop can run at most as many steps as the number of pairs visited
(which cannot exceed |M|*|T|+1). Thus the above algorithm will
take roughly (|M|*|T|+1)^2 steps in the worst case.