SRM 666, D2, 222-Pointer (DevuAndGame)

James S. Plank

Sat Oct 22 10:33:09 EDT 2016

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: August, 2015
Competitors who opened the problem: 417
Competitors who submitted a solution: 396
Number of correct solutions: 347
Accuracy (percentage correct vs those who opened): 83.21%
Average Correct Time: 11 minutes, 44 seconds.

Try this one without hints. If you get stuck or frustrated, then come back here and scroll down.

Your job here is just to simulate the game. Obviously, if you hit a door with no exit, you will return "Win". What if you don't? Then you are going into an infinte loop. How can you test for that?

The hard way is to keep track of the rooms that you have been in already. You can use a vector for that. If you visit a room twice, return "Lose".

The easy way is to realize that if you win, you will do it in within a threshhold of steps. Count your steps, while you are simulating the game, and if you exceed the threshhold, then you have to be in an infinite loop: Return "Lose".

I'm not providing a solution for this one, because I assign it as an in-lab problem. You should shoot for getting this one in under 7 minutes or so.

Running Time Analysis

There isn't much to the running time analysis. Suppose that you keep track of the rooms that you have visited, and the size of nextLevel is n. Then, the running time is O(n). If you keep track of the number of steps, then the running time is also O(n). The additional space in the first solution is O(n), and in the second solution it is O(1).