## 168 - Theseus and the Minotaur

Moderator: Board moderators

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia
As much as I had time to test it, k was no bigger than 200000 (?). Or somewhere around that magnitude... And if I'm right, k also wasn't zero.

It has to do with some kind of interpretation problem, at least in my case I think...

Ivor
dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm
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
Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia
I don't believe that speed is any issue here... I brute-forced my solution and it ran around 1 sec... I didn't get it accepted though... So if you find out anything that's not well stated or not stated at all, please hint. I just can't think of anything...

Ivor
xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

### 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 problem-description incorrect.
dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm
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
dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm
Sorry about that one. The input for the second test was:

A:BC;B:A;C:D;D:A. A B 19[/img]
dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm

### 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
Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

### 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.
dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm
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 two-way 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 two-way 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 two-way 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?
dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm
Judge, please review the conversation about this problem on the Volume I board. There appear to be both description flaws and possible data issues with this problem. Please review this problem.
Juergen Werner
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 ...".

judge
Posts: 8
Joined: Sun Oct 07, 2001 2:00 am
Contact:
I've sent a message to the people who care of that. Thank you for the report.
Mart
New poster
Posts: 18
Joined: Wed Jun 12, 2002 1:00 pm
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.
dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm
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 loop-jumping algorithm. All of these are based on the sample cave:

Input:
#

Output:
H /F
E B /H
F A /B
E D /C
E C B /H
visser
New poster
Posts: 8
Joined: Mon Jun 10, 2002 11:13 am
Location: Netherlands
I can add that in one testcase a : (colon) is used where perhaps
a ; (semicolon) would be expected. One testcase must contain something like:

A:B:C