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