243 - Theseus and the Minotaur (II)

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

243 - Theseus and the Minotaur (II)

Post by Julien Cornebise » Sun Sep 28, 2003 11:43 pm

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
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Mon Sep 29, 2003 9:27 pm

I finally got AC !! :D :D
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 :o :lol: :wink: )

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Tue Sep 30, 2003 12:19 am

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
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Tue Sep 30, 2003 7:44 am

Per wrote: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 :
Original text wrote: 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.
The text we should read wrote: 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 ! :D

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Tue Sep 30, 2003 11:03 am

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
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

WA :(

Post by zsepi » Fri Nov 07, 2003 7:13 am

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
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Fri Nov 07, 2003 8:24 am

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 ! :o
I'll check you i/o asap.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Fri Nov 07, 2003 4:14 pm

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
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Sun Dec 28, 2003 9:55 am

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
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Mon Dec 29, 2003 10:42 am

Hi (and merry christmas by the way) !
junbin wrote: 1)(...)Does this mean that Theseus will ALWAYS take the LAST path
1. Yes, it means precisely that.
junbin wrote: 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 ?
junbin wrote: 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).
junbin wrote: 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
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Mon Dec 29, 2003 4:23 pm

Julien Cornebise wrote: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
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Mon Dec 29, 2003 7:55 pm

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
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Tue Dec 30, 2003 12:31 pm

Julien Cornebise wrote: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
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Tue Dec 30, 2003 12:44 pm

junbin wrote:(...) internet was cranky. :p

Thank you for your quick response.. gonna go work on the question now.. wish me luck. :)
Lol :lol: Good luck then, both with 243 and with... your internet conection ! :wink:

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Tue Dec 30, 2003 12:47 pm

junbin wrote: __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).

Post Reply

Return to “Volume 2 (200-299)”