243 - Theseus and the Minotaur (II)

[little joey]

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]

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).

[little joey]

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]

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.

[little joey]

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]

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).

[little joey]

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

Code: Select all

[metaphysis]

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