### Online Programming Contest, 6-7 November, 2004

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.

```

Copyright (c) IARCS 2003-2018;   Last Updated: 15 Mar 2005