168  Theseus and the Minotaur
Moderator: Board moderators
OK, I have confirmed that the problem is wrong, that 255 is NOT the maximum limit for a single line. It is less than 1000.
k can be greater than 9, but I'm using the assumption that it can fit within a long variable.
I have some ideas on where to go next. I don't want to say too much, but picture this: large value for k, and the trail loops back on itself several times. Figure out how to efficiently bypass the loop(s) and you've got a good solution.
David
k can be greater than 9, but I'm using the assumption that it can fit within a long variable.
I have some ideas on where to go next. I don't want to say too much, but picture this: large value for k, and the trail loops back on itself several times. Figure out how to efficiently bypass the loop(s) and you've got a good solution.
David
sleepless nights...
Since I read the discussion on this subject, I've been trying to solve this problem too. No success; spilled some 30 submissions, but all I get is WA.
I'm convinced that there are double definitions of a cave, something like
A:BCD;B:CD;A:E;C:DE;D:ABC;E:D.
where cave A is defined twice (or more, I don't know). I have, however, no idea how to handle them. Simple concatenation (A:BCDE;) or only considering the last one, or the first, don't work (I keep getting wrong answers).
This, and the fact that input lines can be longer then 255 characters (like others reported), makes either the input or the problemdescription incorrect.
I'm convinced that there are double definitions of a cave, something like
A:BCD;B:CD;A:E;C:DE;D:ABC;E:D.
where cave A is defined twice (or more, I don't know). I have, however, no idea how to handle them. Simple concatenation (A:BCDE;) or only considering the last one, or the first, don't work (I keep getting wrong answers).
This, and the fact that input lines can be longer then 255 characters (like others reported), makes either the input or the problemdescription incorrect.
I got around the issue above by using vectors. See my code above. (I know the Includes didn't copy correctly. The two includes are <iostream.h> and <vector>. The end result, in the case above, is that in room A, the monster would try the rooms in this order: BCDE.
I have hand computed a couple examples to try. The first one will test the speed of your algorithm  if you follow the brute force method, this could take some time. This could also cause problems if you are using short integers for k. If you're jumping over loops, your program should compelte this in no time. Basically  use the same input as was given in the problem, except set k for 1000000000. Your output should be > H /F.
I had a problem with the way my algorithm was jumping over the loops. The following input will test for this problem:
A:BC;B:A;C:D;D:A. A B 19
Output for this test is:
/B
If anyone can think up any other odd map samples to try, please contribute!
David
I have hand computed a couple examples to try. The first one will test the speed of your algorithm  if you follow the brute force method, this could take some time. This could also cause problems if you are using short integers for k. If you're jumping over loops, your program should compelte this in no time. Basically  use the same input as was given in the problem, except set k for 1000000000. Your output should be > H /F.
I had a problem with the way my algorithm was jumping over the loops. The following input will test for this problem:
A:BC;B:A;C:D;D:A. A B 19
Output for this test is:
/B
If anyone can think up any other odd map samples to try, please contribute!
David
168 Problem description wrong
For problem 168, it has become clear, both from my own testing, and through other contributors, that the description of the problem cannot be correct. As part of the problem description, it is clearly stated that no input line can be greater than 255 bytes. Evidently when new test cases were added, this restriction was not followed. Please update the program description to fit the new input data.
David
David
argh
nothing much to add to this except that I can confirm most of whats been said...... long lines, caves with multiple definitions, caves where theseus cannot get to the minotaurs cave on his first move. Speed doesnt appear to be an issue as my program runs in about 1.9seconds on the judge but is WA. The only time I have had problems was with messing around with how Theseus moves when he can't find the Minotaur straight away, and I'm pretty sure that that was due to Theseus and the Minotaur going off on separate loops.
It's about time someone looked into the data of this problem isn't it ? There do appear to be a number of inconsistencies to the problem description.
It's about time someone looked into the data of this problem isn't it ? There do appear to be a number of inconsistencies to the problem description.
Very much, someone needs to look into this problem description. I've come to the conclusion that if Theseus and the Minotaur EVER in ANY of the inputs start out in separate caverns that are not connected by a twoway hallway, the program description does not provide enough information. The starting caverns need to be connected or there is a problem even getting started.
Most notably the program description does not provide information about how the Minotaur acts prior to finding Theseus.
If the input provides only the starting location and does not imply that the Minotaur was heading toward Theseus from the Minotaur's starting location when he decided to go back toward his own starting location, then what demands that he even try to go to C, thereby triggering the chase?
If the monster were to instead head off in random directions from his starting location until he reached Theseus, it may be some time before he would ever try to go to C. If C had another twoway passage connecting it to another room, there is no guarantee that the Minotaur would ever come from A.
If the monster were to check the rooms in the described order until he triggered the chase, he would NEVER reach Theseus because he would be in a loop, cheking first B then A, then B again, etc.
Assuming again that the Minotaur would check rooms in the order described, if he never checked a room he'd just left, whether it was lit or not (because Theseus hasn't given chase yet), he would end up checking B, D, G, E, F, H, then back to E, and again stuck in a loop.
So again, if the starting locations are not joined by some kind of twoway hallway, and cannot therefore be assumed to be the starting locations of the two characters AFTER the chase has just begun (The Minotaur was coming toward Theseus when he saw the light, and Theseus just heard the Minotaur retreat)  we have no information about how to control the Minotaur, may not be able to get the two to meet each other, and the problem cannot be solved.
Either the data needs to be corrected, or the program description needs to be revised.
I keep getting Wrong Answer with everything I try. I'm waiting to hear from someone who got this one right who can provide a clue on how to proceed. How do we get the judge's attention on correcting this definition?
Most notably the program description does not provide information about how the Minotaur acts prior to finding Theseus.
If the input provides only the starting location and does not imply that the Minotaur was heading toward Theseus from the Minotaur's starting location when he decided to go back toward his own starting location, then what demands that he even try to go to C, thereby triggering the chase?
If the monster were to instead head off in random directions from his starting location until he reached Theseus, it may be some time before he would ever try to go to C. If C had another twoway passage connecting it to another room, there is no guarantee that the Minotaur would ever come from A.
If the monster were to check the rooms in the described order until he triggered the chase, he would NEVER reach Theseus because he would be in a loop, cheking first B then A, then B again, etc.
Assuming again that the Minotaur would check rooms in the order described, if he never checked a room he'd just left, whether it was lit or not (because Theseus hasn't given chase yet), he would end up checking B, D, G, E, F, H, then back to E, and again stuck in a loop.
So again, if the starting locations are not joined by some kind of twoway hallway, and cannot therefore be assumed to be the starting locations of the two characters AFTER the chase has just begun (The Minotaur was coming toward Theseus when he saw the light, and Theseus just heard the Minotaur retreat)  we have no information about how to control the Minotaur, may not be able to get the two to meet each other, and the problem cannot be solved.
Either the data needs to be corrected, or the program description needs to be revised.
I keep getting Wrong Answer with everything I try. I'm waiting to hear from someone who got this one right who can provide a clue on how to proceed. How do we get the judge's attention on correcting this definition?

 New poster
 Posts: 27
 Joined: Wed Apr 17, 2002 7:54 pm
I can also confirm that, apart from lines being longer than 255 characters, there is at least one input where there is no connection from the starting position of the Theseus to the one of the Minotaur, which clearly is inconsistent to the problem description saying "... followed by the identifiers for the caverns which the Minotaur and Theseus were in when contact was first made ...", "Theseus ... until he heard the Minotaur approaching along a tunnel. At this point he lit a candle and set off in pursuit ..." and "Theseus followed ...".
Adrian K
Adrian K
Hmm. Well my tests indicate that there is always a path from Theseus to the Minotaur, but sometimes not from the Minotaur to Theseus. Which is still inconsistent with the description of the problem, but you could carry on from that point with Theseus giving chase (which still gives WA, so it must be something more than that).
There are definitely multiple cave definitions. Concatenation of the paths would seem to be the logical action, but it is inconsistent with the problem description:
The description of a labyrinth will identify each cavern by an upper case character and will list the caverns reachable from that cavern in the order that the Minotaur will attempt them.
Mart.
There are definitely multiple cave definitions. Concatenation of the paths would seem to be the logical action, but it is inconsistent with the problem description:
The description of a labyrinth will identify each cavern by an upper case character and will list the caverns reachable from that cavern in the order that the Minotaur will attempt them.
Mart.
OK, while we're waiting to hear anything back from the problemset people about this, I keep hoping that the data is OK, but I haven't quite hit on the right idea.
The meat of my program focuses on the theory that if Theseus and the Minotaur ever find themselves in two caverns that they have already visited, in the order that they have already visited them, they will continue to visit these caverns in this same order, at the same interval, until a candle is dropped.
Basically  keep track of which "turn" Theseus visited each cavern. When the program finds a place where Theseus previously visited the current cavern on turn (x), and Theseus previously visited the Minotaur's cavern on turn (x + 1), then if Theseus is now on his turn (y), then he will continue to visit this cavern every (y  x) turns. When skipping several loops like this, (x) must be greater than zero, and every time a candle is placed, all previous turn indicators are reset to zero.
This is how I've been able to achieve near instant response time with large (k) values. Can anyone devise a cavern for which this would not work?
I started my counting at zero, so the first turn after the starting cavern, or after Theseus put down a candle was considered turn 1. With such a numbering scheme, the program needed to make sure that (x) was greater than zero or it gave the wrong input for the next example. Why? The first time it saw cavern D, it noticed that it was supposedly last visited on turn zero (actually hadn't been visited before), and that the Minotaur was now in the cavern visited on turn 1. It would therefore assume it was in a DAC loop, when turn 5 should bring it back to B.
Input:
A:BC;B:A;C:D;D:A. A B 19
#
Output:
/B
I have gone back to assuming that Theseus must be able to reach the Minotaur's starting cavern on his first turn. Reason: as I pointed out earlier in this discussion, a) the current problem description demands that this be so, and b) if this is not so, we have not been given any way to reliably start this problem  and the example input output is possibly very wrong.
I have thought about the possibility that maybe Theseus is already in the Minotaur's starting cavern. Maybe he just got lucky when he entered the maze. Related to this is the possibility that maybe one of the caverns loops back on itself. Here's some example tests for these cases:
Input:
A:B;B:AC;C:B. B B 1
A:B;B:BCA;C:D;D:C. B A 3
#
Output:
/B
/B
I've run out of new ideas for funny cases. If anyone else has ideas, build a test case, and share it with us! Here are a few more test cases I devised to test the loopjumping algorithm. All of these are based on the sample cave:
Input:
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 1000000000
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 1001
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 1002
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 1004
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 1007
#
Output:
H /F
E B /H
F A /B
E D /C
E C B /H
The meat of my program focuses on the theory that if Theseus and the Minotaur ever find themselves in two caverns that they have already visited, in the order that they have already visited them, they will continue to visit these caverns in this same order, at the same interval, until a candle is dropped.
Basically  keep track of which "turn" Theseus visited each cavern. When the program finds a place where Theseus previously visited the current cavern on turn (x), and Theseus previously visited the Minotaur's cavern on turn (x + 1), then if Theseus is now on his turn (y), then he will continue to visit this cavern every (y  x) turns. When skipping several loops like this, (x) must be greater than zero, and every time a candle is placed, all previous turn indicators are reset to zero.
This is how I've been able to achieve near instant response time with large (k) values. Can anyone devise a cavern for which this would not work?
I started my counting at zero, so the first turn after the starting cavern, or after Theseus put down a candle was considered turn 1. With such a numbering scheme, the program needed to make sure that (x) was greater than zero or it gave the wrong input for the next example. Why? The first time it saw cavern D, it noticed that it was supposedly last visited on turn zero (actually hadn't been visited before), and that the Minotaur was now in the cavern visited on turn 1. It would therefore assume it was in a DAC loop, when turn 5 should bring it back to B.
Input:
A:BC;B:A;C:D;D:A. A B 19
#
Output:
/B
I have gone back to assuming that Theseus must be able to reach the Minotaur's starting cavern on his first turn. Reason: as I pointed out earlier in this discussion, a) the current problem description demands that this be so, and b) if this is not so, we have not been given any way to reliably start this problem  and the example input output is possibly very wrong.
I have thought about the possibility that maybe Theseus is already in the Minotaur's starting cavern. Maybe he just got lucky when he entered the maze. Related to this is the possibility that maybe one of the caverns loops back on itself. Here's some example tests for these cases:
Input:
A:B;B:AC;C:B. B B 1
A:B;B:BCA;C:D;D:C. B A 3
#
Output:
/B
/B
I've run out of new ideas for funny cases. If anyone else has ideas, build a test case, and share it with us! Here are a few more test cases I devised to test the loopjumping algorithm. All of these are based on the sample cave:
Input:
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 1000000000
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 1001
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 1002
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 1004
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 1007
#
Output:
H /F
E B /H
F A /B
E D /C
E C B /H