PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
This problem is an exercise in BFS/DFS. The main point here seems to be how to encode the state so that the search to be fast enough. The author’s approach is as follows. There are not more than 25 stones. We sill keep the mask of which stones are left of the board. And we should add the number of the stone we are standing on to the state. So we have at most 25*2^25 states which surely too much, but actually many of the states are going to be inaccessible even in the worst case (also some of the states reachable from the initial state will be unsolvable and can be removed from the search). However we should still try to make the search as fast as possible. For each state we can move to at most 8 other states. In order to make calculation possible move fast for each stack of stones we will keep the number of the first stone on the stack and also for each move the number of the stack this moves lands on or -1 in the move is illegal for the stack. Also for each stone we will keep the number of the stone under it in the stack or -1 if it’s the last stone in the stack and the number of the stack this stone belongs to. Using this information the each state can be resolved rather fast. So now BFS can be used to solve the problem. Since the number of moves to reach any state in fixed DFS can be used as well.
Several optimizations can be applied in this problem. For example we can keep the number of stack instead of the number of stone we are on. Having that the test cases are random the amount of stacks should be lesser than the amount of stones. We can determine unsolvable states and remove them from the search. Since we know the final state – meet in the middle approach can be used for some additional time win. Seems that dynamic programming can be also used in this problem.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.