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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon May 17, 2004 4:38 pm

I'm getting TLE, which is caused by the fact that Minotaur is stuck in a cave and all the exits are marked by him (I verified this fact using assert()).

This can be caused by two things:

1) This situation cannot occur given the problem constraints and my code is awfully bad.

2) The way to treat this situation is so obvious, that it would be a shame to mention it in the problem description.

In both cases I am to blame, which I realise.

Can anyone with AC tell _IF_ he deals with this situation, and if yes, _HOW_ ?

I tried to construct a maze in which this deadlock would occur, but without success. This gives me the feeling that alternative 1) applies...

Any help is appreciated,
-little joey

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

Post by Adrian Kuegel » Mon May 17, 2004 5:20 pm

My program would go into an endless loop in such a case.
Perhaps you can describe your logic, how you mark which entries into passages were used (note that not the passages are marked, only the entries, so it is possible to use the same passage twice, once in each direction).

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon May 17, 2004 6:21 pm

Thanks for your reply.

Mine goes into an endless loop too, but this actually happens while executing the judges' input... (Making the Minotaur stay in the cavern until Theseus hunts him down and beets him, gives WA).

I actually mark the passage, but I keep two records per passage, from A to B and from B to A, that are marked when going from A to B or the reverse, respectively. I also keep an attribute minotaur_last_exit for every cavern. If set, Theseus will always take this exit from the cavern.

I have a main loop as follows:

Code: Select all

   Minotaur_passage_to_cavern()
      if he finds a lit candle he flees back to original cavern
   Theseus_passage_to_cavern()
      if he finds the Minotaur here, he kills him
      if the attribute minotaur_last_exit is set, he lights a candle
   Theseus_cavern_to_passage()
      if minotaur_last_exit is set, he marks the exit and takes it
      else he searches the first exit not marked by him, marks it and takes it
   Minotaur_cavern_to_passage()
      search for the first exit not marked by him, mark it and select it
      if Theseus is in the passage he just selected, kill him
      set minotaur_last_exit to the selected one and take it
This loop is repeated endlessly, until one of the kills occurs. I think this reflects the order in which the events should occur (although other implementations are of course possible).

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

Post by Adrian Kuegel » Mon May 17, 2004 6:35 pm

Hi,
I just checked with assert that there is a case where minotaur and theseus start in the same passage.
From your logic it seems that you miss that theseus is killed there.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon May 17, 2004 6:57 pm

Thanks Man! I added that as a special case and got accepted!
You're rightfully number one. Do you think I should remove my previous message?

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

Post by Adrian Kuegel » Mon May 17, 2004 7:06 pm

I think you can leave your post as it is, it might help others to find mistake in their code (and it is no spoiler in my opinion).

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon May 17, 2004 8:25 pm

Yes, I'll leave it. The actual order of events is:

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

Re: 243 - Theseus and the Minotaur (II)

Post by metaphysis » Tue May 31, 2016 5:00 am

Some test cases and AC output.

Code: Select all

A:BCD
D:BACG
F:HE
G:HED
B:AD
E:FGH
H:FEG
C:AD
@ACFH
A:BCD
D:BACG
F:HE
G:HED
B:AD
E:FGH
H:FEG
C:AD
@ABAC
A:BCD
D:BACG
F:HE
G:HED
B:AD
E:FGH
H:FEG
C:AD
@ACDG
D:G
G:ED
E:GH
H:E
@DGGE
A:BC
B:CA
C:AB
@ABBC
#

Code: Select all

Theseus is killed between D and G
The Minotaur is slain in D
The Minotaur is slain in H
Theseus is killed between E and H
The Minotaur is slain in B

Post Reply

Return to “Volume 2 (200-299)”