Problem
Recently I came across this problem in the IARCS server,here is an little excerpt from it,
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 Nth machine
that Muttal will visit. Muttal always begins his search by inserting a
1 rupee coin into the first machine.For example suppose there are three machines and two kinds of tokens
and the description of the machines is as follows:
We take T1 to represent the one rupee coin. If Muttal starts at
machine M1 then the sequence of machines he visits is M1, M2, M3, M1,
M2, M3, … Thus, the fourth machine he visits is M1, the fifth
machine he visits is M2 and so on.
So I have worked a little on the code , but I get Time limit exceeded for some last output , I was thinking of an modulo thing , but not sure of it, here is what I am working on,
#include <iostream>
#include <vector>
int main(){
int machines , tokens , start , end;
std::cin >> machines >> tokens >> start >> end;
start--;end--;
std::vector<std::vector<int> >tokenTable(machines,std::vector<int>(tokens));
std::vector<std::vector<int> >machTable(machines,std::vector<int>(tokens));
//std::vector<std::vector<int> >visited(machines,std::vector<int>(tokens));
std::vector<int>visitedMach;
for(int i=0;i<machines;i++){
for(int j=0;j<tokens;j++){
int tok , mach;
std::cin >> tok >> mach;
tok--;mach--;
tokenTable[i][j] = tok;
machTable[i][j] = mach;
}
}
int moves =0 ,token = 0;
while(moves < end){
/*if(visited[start][token]){
int remaining = moves - visited[start][token]+1;
int modFac = (end-visited[start][token])%remaining;
if(modFac == 0){
modFac = remaining;
}
modFac = modFac + visited[start][token];
//std::cout << visited[start][token] << ' ' << moves <<' ' <<modFac<<std::endl;
std::cout <<visitedMach[modFac]+1<< std::endl;
return 0;
}
visited[start][token] = moves;
visitedMach.push_back(start);*/
int newTok = tokenTable[start][token];
int newStart = machTable[start][token];
token = newTok;
start = newStart;
moves++;
}
std::cout << start+1 << std::endl;
return 0;
}
The code in the comments is what I was thinking of doing but not sure of it, do you guys have some better approach for this problem?
Solution
What we have here is a two-dimensional map, where each pair maps to a new pair.
We could pre-allocate a single contiguous vector like this:
std::vector<size_t> treasureMap;
treasureMap.resize(machines * tokens);
Then, taking the example from the question, item 0, i.e. machine M1, token T1 would point to index 3 (machine M2, token T2).
The whole vector from the example would look like this:
[3, 2, 4, 5, 0, 1]
Or, in code, when we read tokens and machines
treasureMap[i * tokens + j] = mach * tokens + tok
So, we have an optimized allocation, and optimized walkthrough when we iterate from the starting point.
size_t currentPos = start;
for (size_t i = 0; i < moves; ++i)
currentPos = treasureMap[currentPos];
I’m not sure if it will give you enough speed to pass the challenge though. If not, at least the code looks nicer.
So the first think to define is the state of Muttal on the route, which is a pair of the current token and machine, which incidentally are two unsigned numbers
using machineMap = std::vector<std::pair<int, int>>;
Now for every machine we would create a mapping, that gives us the next token and the next machine.
std::vector<machineMap> mapping(numMachines, machineMap(numTokens));
for (subMapping : mapping) {
for (map : subMapping) {
std::cin >> map.first >> map.second;
}
}
Also you should utilize a for loop whenever you know the number of steps instead of a while loop.
auto currentPos = std::make_pair(0, firstMachine);
for (size_t step = 0; step < numSteps; ++step) {
currentPos = mapping[currentPos.second][currentPos.first];
}
In total that would give us
#include <iostream>
#include <utility>
#include <vector>
int main() {
using machineMap = std::vector<std::pair<int, int>>;
size_t numMachines , numTokens , firstMachine , numSteps;
std::cin >> numMachines >> numTokens >> firstMachine >> numSteps;
firstMachine--;
numSteps--;
std::vector<machineMap> mapping(numMachines, machineMap(numTokens));
for (subMapping : mapping) {
for (pair : subMapping) {
std::cin >> pair.first >> pair.second;
}
}
auto currentPos = std::make_pair(0, firstMachine);
for (size_t step = 0; step < numSteps; ++step) {
currentPos = mapping[currentPos.second][currentPos.first];
}
std::cout << currentPos.second+1 << std::endl;
}
So this would be the plain algorithm you utilized. However, as you said this will most likely give you TLE. So what i believe would be the main idea behind the challenge is to realize that there might be immutable orbits inside the map, aka whenever you end up with the same combination of token and machine, you can shortcircuit by taking the remaining number of steps modulo the number of steps it takes you to reach the node the again.
So the question is, how can you find out, whether you can shortcuircuit and how long it took to get to the same token again. For me the solution would be not use a std::pair, but rather a custom struct
struct mapEntry {
size_t nextToken = 0;
size_t nextMachine = 0;
bool visited = false;
size_t lastVisited = 0;
}
Now the code would look like this:
#include <iostream>
#include <vector>
struct mapEntry {
size_t nextToken = 0;
size_t nextMachine = 0;
bool visited = false;
size_t lastVisited = 0;
}
int main() {
using machineMap = std::vector<mapEntry>;
size_t numMachines , numTokens , firstMachine , numSteps;
std::cin >> numMachines >> numTokens >> firstMachine >> numSteps;
firstMachine--;
std::vector<machineMap> mapping(numMachines, machineMap(numTokens));
for (subMapping : mapping) {
for (entry : subMapping) {
std::cin >> entry.nextToken >> entry.nextMachine;
}
}
mapEntry currentPos = mapping[0][firstMachine];
currentPos.visited = true;
currentPos.lastVisited = 0;
for (size_t step = 1; step < numSteps; ++step) {
currentPos = mapping[currentPos.nextMachine][currentPos.nextToken];
if (currentPos.visited) {
size_t cycleLength = step - lastVisited;
size_t remainingSteps = (numSteps - step)%cycleLength;
/* Only loop to remainingStep-1 so that you get the final machine via currentPos.nextMachine */
for (size_t newStep = 0; newStep < remainingSteps -1; ++newStep) {
currentPos = mapping[currentPos.nextMachine][currentPos.nextToken];
}
break;
} else {
currentPos.visited = true;
currentPos.lastVisited = step;
}
}
std::cout << currentPos.nextMachine << "n";
}
Cycle detection
With M machines and T tokens, there are M∗T states that you can be in. So your path can be at most M∗T moves long before it starts to cycle.
To solve the problem for large values of N, you should first manually make M∗T moves. Then, remembering your location (meaning the machine AND token), count how many moves it takes until you end up at the same location again. This is the length of the cycle you are in. After that, you need to make some more final moves to end up at the destination. If n is the original number of moves you needed to make, and cycleLen is the cycle length, then you need to make (n - m*t) % cycleLen more final moves.
This algorithm makes at most 3∗M∗T moves.
Sample Implementation
Here is an implementation of the above:
#include <iostream>
#include <vector>
int main(){
int machines , tokens , start , end;
int total;
std::cin >> machines >> tokens >> start >> end;
total = machines * tokens;
start--;end--;
std::vector<std::vector<int> >tokenTable(machines,std::vector<int>(tokens));
std::vector<std::vector<int> >machTable(machines,std::vector<int>(tokens));
std::vector<int>visitedMach;
for(int i=0;i<machines;i++){
for(int j=0;j<tokens;j++){
int tok , mach;
std::cin >> tok >> mach;
tok--;mach--;
tokenTable[i][j] = tok;
machTable[i][j] = mach;
}
}
int token = 0;
// If there are a lot of moves, then find a cycle first and then reduce
// the number of moves to something less than the cycle length.
if (end > total * 3) {
// First, make M*T moves.
for (int moves = 0; moves < total; moves++) {
int newTok = tokenTable[start][token];
int newStart = machTable[start][token];
token = newTok;
start = newStart;
}
// Next, count the number of moves until we reach this spot again.
int cycleStart = start;
int cycleToken = token;
int cycleLength = 0;
do {
int newTok = tokenTable[start][token];
int newStart = machTable[start][token];
token = newTok;
start = newStart;
cycleLength++;
} while (start != cycleStart || token != cycleToken);
// Now, we can reduce the number of total moves.
end = (end - total) % cycleLength;
}
// Now make moves until we reach the end.
for (int moves = 0; moves < end; moves++) {
int newTok = tokenTable[start][token];
int newStart = machTable[start][token];
token = newTok;
start = newStart;
}
std::cout << start+1 << std::endl;
return 0;
}