Problem Link - Treasure Hunt
Problem Statement
A well-known bandit who used to haunt the forests around Siruseri was eliminated by the policemen a few months ago. There are several stories about a valuable treasure that he is alleged to have buried somewhere in the forest.
The deceased bandit had several hideouts and the police found a lot of things in these hideouts — a number of guns, ammunition, knives, … Interestingly, in every hideout there was a strange looking machine. This machine looked a bit like the weighing machine that is found in Indian railway stations where you insert a coin and get a card with your weight printed on it. The police had no idea what these machines were meant for and since they were heavy and in the middle of the forest they just left them there.
Only one man knew that the clue to the buried treasure was in these innocuous looking machines and that was Muttal. Muttal used to be part of the dacoit’s band of robbers but was thrown out for being too dumb.
Here is how the treasure was to be found. One had to insert a 1 rupee coin into one of these machines. This machine would then put out a token and a card on which was printed the name of the machine to be visited next. The token was then to be inserted into the machine whose name was printed on the card. The new machine would, in turn, produce another token and another card with a new destination printed on it, and so on. If you started with by putting a 1 rupee coin in the correct machine place and followed the sequence of machines indicated by the cards, inserting each token produced by one machine into the next one, eventually one of these machines would put out a map to the treasure. Unfortunately, though, Muttal did not know which machine one should begin with. Unknown to Muttal, the bandit had played one last joke on the world. Knowing his end was near, he had reprogrammed these machines. There was no longer any map. All that you got for inserting a token in any machine was another token and a card leading you to the next machine. So poor Muttal is going to spend the rest of his life inserting tokens into machines and walking from one machine to another.
You are given M machines that generate and respond to T different kinds of tokens. We regard the 1 rupee coin also as one of the T types of tokens. For each machine m and each token t you are told what happens when t is inserted into m: that is, which token is produced by m and what the next destination printed on the card is.
Your task is the following. Given the identity of the machine where Muttal starts his search and an integer N, identify the N-th machine that Muttal will visit. Muttal always begins his search by inserting a 1 rupee coin into the first machine.
Approach
The problem involves simulating the behavior of Muttal as he moves from one machine to another based on the output of tokens and cards. The machines and their responses are represented using a grid, where for every machine and token combination, we know the next token and destination machine. We start from a specific machine and token and keep track of each visited state. If a repeated state is detected, it indicates a loop. We calculate how many steps remain until we reach the desired count N and skip the unnecessary intermediate iterations by leveraging the loop’s length. This optimization reduces redundant computations and helps efficiently find the N-th machine. The simulation stops when either the required machine is reached or the loop optimization allows direct skipping to the result.
Time Complexity
The approach runs in O(N) in the worst case but reduces to O(\text{Loop Size}) if a loop is detected early.
Space Complexity
The space complexity is O(\text{Unique States}) for storing the visited states in the cache.