243 - Theseus and the Minotaur (II)

[Julien Cornebise]

Hi

I'm trying to solve 243, but I keep getting Wrong Answer. Only 7 users got it AC !
Is there any special thing to know about the problem ? ANy special case ? Any error in the sample output (such as a '.' to add at the end of the lines, etc), that would not be specified in the sample output and that these 7 people had guessed ? Any common mistake ??

Please help me, I've writtent 150 C++ lines to simulate this problem, and it's driving me mad not to get it AC !
Thank you

[Julien Cornebise]

I finally got AC !!
Thank you very much Adrian for your wiseful and precious help.

For other people, here are the main trap I fall into Theseus and Minotaurus can go back (I forgot that...). One thing more : be extremely precautionous and slow when coding this one, to avoid stupid things as I did (silly bugs, etc), because efficiently simulating the curse of both of them is very minutious (though not so difficult as it seems - errr... I only done 50 submissions for this one )

[Per]

Your happy post made me take a look at my old submission yet again to see if I could find any errors, and I actually managed to get AC with just one extra submission, one little change: changing the way Theseus follows the minotaur from a room in which the minotaur has been several times (and thus exited in several different directions). IMO the problem statement is misleading on this point, if not plain wrong.

Thanks for the inspiration!

[Julien Cornebise]

IMO the problem statement is misleading on this point, if not plain wrong.

There had been some ambiguities in the pb statement some time ago about what happened if Minos saw a light in a cavern and turned back while Theseus was precisely coming from this cavern : it wasn't precised wether both of them met in the corridor or in the cavern. Thanks to Adrian who discussed this with Marceh, it has been corrected. I guess that you may send a mail to marceh (or a private message on this forum) to correct this. Indeed, a word seems to miss :

When he entered a cavern that had been previously entered by the Minotaur he would light a candle and leave it there and then turn right (as usual) but take the Minotaur's exit.

When he entered a cavern that had been previously entered by the Minotaur he would light a candle and leave it there and then DO NOT turn right (as usual) but take the Minotaur's exit.

This combined to the length of the pb statement and to the low statistics (due to the ancient ambiguity mentionned before, now solved) may explain that few people still try it.

Thanks for the inspiration!

You're welcom !

[Adrian Kuegel]

Yes, the problem statement is misleading at this point. But as I understand it, there is nothing said about minotaurs exits or a minotaur exit, so the previous exits doesn't count any more. But that theseus turns right as usual can be omitted, it is really misleading.
Perhaps the text should be like this:

When he entered a cavern that had been previously entered by the Minotaur he would light a candle and leave it there and then take the Minotaur's last exit.

[zsepi]

I get WA, though (of course) I pass the standard example.... i would really appreciate some crucial input. so far I managed to think of the case when T & M are in the same passage, of course T should die, T & M both can go through each edge twice (one time each way), if the format of the standard input is correct, then i do that right - it's kinda said that two day before the regionals i get stuck on this :( I do hope saturday will be better
thanks in advance
PS: what should be the output for this case:

Code: Select all

A:FB
B:AC
C:BD
D:CE
E:DF
F:EA
@FAEF

my output is

Code: Select all

Theseus is killed between B and C

[Julien Cornebise]

Hi zsepi

I'm having a quick glance at your post before going in class (7AM here in Paris), so I can't lock toroughly to your input/output, but a first run on my AC source let me think that there is no such case : I shamely sigsegv on this one !
I'll check you i/o asap.

[Adrian Kuegel]

My output is:
The Minotaur is slain in C
Moves of theseus and minotaur:
Theseus moves from F to A, minotaur from E to F
Theseus moves from A to B, minotaur from F to A
Theseus moves from B to C, minotaur from A to B
Theseus moves from C to D, minotaur from B to C
Theseus moves from D to E, minotaur from C to D
Theseus moves from E to F, minotaur from D to E
Theseus moves from F to A, minotaur from E to F // note that minotaur returns to E in same round
Theseus moves from A to B, minotaur from E to D
Theseus moves from B to C, minotaur from D to C

[junbin]

I have been trying to solve this question for quite some time and I can't seem to get it right. I think I may have misunderstood some concepts... Can someone please tell me whether my understanding is correct?


1) "When he entered a cavern that had been previously entered by the Minotaur he would light a candle and leave it there and then turn right (as usual) but take the last exit used by the Minotaur. "

Does this mean that Theseus will ALWAYS take the LAST path taken by the Minotaur if the Minotaur has passed through that room already (even if that path is marked)? Eg: Minotaur goes from A to B to C to D to E. Theseus goes from B to C to A to B to C?

Also, is it correct to say that if the Minotaur was previously in the cave Theseus is in, he will always light a candle, but WILL NOT mark the exit he takes (the one the Minotaur last took)?


2) "If he sensed that the cavern he was about to enter had a candle burning in it, he would turn and flee back up the passage he had just used, arriving back at the previous cavern to complete his `turn.' If this happens and Theseus is coming from that cavern they will meet in the passage. "

In the last sentence "Theseus is coming from that cavern they will meet in the passage. ", which passage does "the passage" refer to? And which cavern does "that cavern" refer to?

Does "the cavern" refer to the cavern with the candle, or the cavern that the minotaur was in before entering the passage which leads to the cavern with the candle, or does "the cavern" refer to the cavern that the Minotaur will take next? Eg: Minotaur is at A, goes into passage leading to B (B has a candle). Minotaur returns to A (without entering B) and then chooses C.

Does "the cavern" refer to A, B or C?


Also, does "the passage" refer to A-B, B-A, B-C, C-B, A-C or C-A ?



3) "he would turn and flee back up the passage he had just used, arriving back at the previous cavern to complete his `turn.'"

Does this mean that the Minotaur will not enter the cavern with the candle (and thus will not leave a "last exit" trail for Theseus)?

[Julien Cornebise]

Hi (and merry christmas by the way) !

1)(...)Does this mean that Theseus will ALWAYS take the LAST path

1. Yes, it means precisely that.

Also, is it correct to say that if the Minotaur was previously in the cave Theseus is in, he will always light a candle, but WILL NOT mark the exit he takes (the one the Minotaur last took)?

It's not important wether he marks it or not : see why ?

2) (...) Eg: Minotaur is at A, goes into passage leading to B (B has a candle). Minotaur returns to A (without entering B) and then chooses C.

2. In your exemple, in ONE round, minotaur can't go from A to B (candle !), then flee back to A, and choose C. He only does goes from A to B (candle !), and back to A, so at the end of the turn he still is in A, and the passage refers to A<->B (in the case where Theseus arrived from B).

3) (...) Does this mean that the Minotaur will not enter the cavern with the candle (and thus will not leave a "last exit" trail for Theseus)?

3. Yes, he would not enter the cavern, and thus not leave a trail.

Hope it cleared things up. Good luck

[junbin]

Hi (and merry christmas by the way) !
2. In your exemple, in ONE round, minotaur can't go from A to B (candle !), then flee back to A, and choose C. He only does goes from A to B (candle !), and back to A, so at the end of the turn he still is in A, and the passage refers to A<->B (in the case where Theseus arrived from B).

Let me clarify some cases..

Assume B has a candle in all cases.
M: Minotaur, T: Theseus
X-Y means passage from X to Y


Case 1:
Round 1: M: A, T: B
Round 2: M: A-B, T: B-A

Theseus dies in passage between B and A. (NOT between A and B)

Case 2:
Round 1: M: A, T: C
Round 2: M: A-B, T: C-A
Round 3: M:A, T:A

Minotaur dies in cave A

Case 3:
Round 1: M:A, T:B
Round 2: M:A-B, T:B-C
Round 3: M:B, T:C
Round 4: M:B-C, T:C-B

Theseus dies in passage between C and B. (NOT between B and C)

Case 4:
Round 1: M: A, T: B
Round 2: M: A-B, T:B-D
Round 3: M:A, T:D
Round 4: M:A-C, T:D-C
Round 5: M: C, T:C

Minotaur dies in cave C.

[Julien Cornebise]

Hi (And by the way, that would'nt hurt that you say "hi" too, or "thanks", or things like that. A little bit less efficient, maybe, but really more agreable to read and to answer to.)

Case 1: Yes, T dies, but the graph is undirected, so passage A to B is exactly the same that B to A

Case 2: Yes

Case 3: Didn't you say that there was a candle in B ? M can't be in B at round 3. Anyway, if there is no candle in B, then ok, T dies between B and C (and between C and B, see case 1)

Case 4: Yes

[junbin]

Hi (And by the way, that would'nt hurt that you say "hi" too, or "thanks", or things like that. A little bit less efficient, maybe, but really more agreable to read and to answer to.)

Sorry.. :p

Was a bit angry that night because that was the fourth time I typed the same forum post... (the first three times had merry christmas :p ).. internet was cranky. :p

Thank you for your quick response.. gonna go work on the question now.. wish me luck.


__EDIT__

Just added in the case about them meeting up after M sees a candle and I got accepted. Thanks for your help.

[Julien Cornebise]

(...) internet was cranky. :p

Thank you for your quick response.. gonna go work on the question now.. wish me luck.

Lol Good luck then, both with 243 and with... your internet conection !

[Julien Cornebise]

__EDIT__

Just added in the case about them meeting up after M sees a candle and I got accepted. Thanks for your help.

You're welcome ! Great ! Congratulations This seing-a-candle case is indeed the most trickiest in this problem (imho).