1
\$\begingroup\$

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:

enter image description here

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?

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I highly doubt on it , partly cause havent used size_t and manual memory allocation earlier and partly because of the number of inputs which is about 1000000000 and that thing is not small , thanks for answering \$\endgroup\$ – hellozee Oct 29 '16 at 17:07
  • \$\begingroup\$ As per the answer below: we should add loop detection into the algorithm. One way is to keep a set of all visited locations; once we detect that we're in a loop, we can short-circuit the whole evaluation. \$\endgroup\$ – RomanK Oct 29 '16 at 21:15
1
\$\begingroup\$

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";
}
\$\endgroup\$
  • \$\begingroup\$ I think it can be done without a custom struct \$\endgroup\$ – hellozee Oct 30 '16 at 3:04
1
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ looks alright but kinda confusing for implementation , can you shed some light? \$\endgroup\$ – hellozee Nov 6 '16 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.