## 168 - Theseus and the Minotaur

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

Moderator: Board moderators

Lawrence
New poster
Posts: 17
Joined: Sat Feb 09, 2002 2:00 am
Location: China
Contact:
This seems to be a very easy problem but I have been getting wrong answer. I have tried several cases and they all work very well. So reading the program specification again I'm now wondering what should Theseus do if the Minotaur is approaching(i.e. starts) Theseus in a one-direction passage, that is, the Minotaur can reach Theseus while the hero can't go through the passage to where the beast stays. In my program Theseus would *magically* reach the Minotaur's starting position. Anyone of any ideas?
ntrhieu
New poster
Posts: 21
Joined: Mon Oct 22, 2001 2:00 am
I got AC for this one. As far as I understand, you can assume there is no such test case. The hero just comes after the devil and always one step after it until it's trapped.
Hieu Nguyen
Lawrence
New poster
Posts: 17
Joined: Sat Feb 09, 2002 2:00 am
Location: China
Contact:
Maybe I should post my code here and someone would like to help.

#include <stdio.h>

int laby[26][26];
int candle[26];
int count[26];
int theseus;
int minotaur;
int k;

void chase()
{
int i,j;
int ct=0;
j=0;
while(1)
{
ct=count[minotaur];
for(i=0;i<ct;i++)
{
if(!candle[laby[minotaur]] && laby[minotaur]!=theseus)
{
theseus=minotaur;
minotaur=laby[minotaur];
j++;
if(j==k)
{
candle[theseus]=1;
j=0;
printf("%c ",theseus+'A');
}
break;
}
}
if(i==ct)
break;
}
printf("/%c\n",minotaur+'A');
}

void main()
{
#ifdef ONLINE_JUDGE
FILE *fp=stdin;
#else
FILE *fp=fopen("168.in","r");
#endif
char buf[300];
int i,j;
int pos;
while(1)
{
for(i=0;i<26;i++)
{
for(j=0;j<26;j++)
laby[j]=-1;
candle=0;
count=0;
}
i=0;
fgets(buf,300,fp);
if(buf[0]=='#')
break;
while(1)
{
pos=buf-'A';
i+=2;
while(buf!=';' && buf!='.')
{
laby[pos][count[pos]]=buf-'A';
count[pos]++;
i++;
}
if(buf[i]=='.')
{
sscanf(&buf[i+2],"%c %c %d",&minotaur,&theseus,&k);
minotaur-='A';
theseus-='A';
break;
}
i++;
}
chase();
}
}
ntrhieu
New poster
Posts: 21
Joined: Mon Oct 22, 2001 2:00 am
Admins, what happened ? Now they put such a test that there is no passage from the Theseus to Minotaur (unless I read input incorrectly).
So, what's the output would be for that case ?
Hieu Nguyen
Martin Juvan
New poster
Posts: 1
Joined: Mon Jun 03, 2002 9:44 pm
ntrhieu wrote:Admins, what happened ? Now they put such a test that there is no passage from the Theseus to Minotaur (unless I read input incorrectly).
So, what's the output would be for that case ?
I agree with the above conclusion. I also think that there is at least one test case where the initial positions of Theseus and Minotaur are not adjacent.

Also, I think that some of the input lines have more than 255 characters.
danielpitts
New poster
Posts: 1
Joined: Sat Jun 08, 2002 10:09 am
Contact:

### Test Cases

Well, I'm not reading the input a whole line at a time, and I'm still getting a memory overflow (about 1.8 seconds into the run).
I wonder if maybe they don't have spaces where I'm expecting them...
This does seem like a simple problem, I but only %3.2 AC? Something is either wrong with the test cases, or with the description.
Mart
New poster
Posts: 18
Joined: Wed Jun 12, 2002 1:00 pm
Hi,

as far as I can tell there is always a passage from Theseus to the Minotaur at the start. I don't know about line length (as I read in by the character) but I cope with any white space and still get WA.

I think it must be a case involving leaving candles but I've tried any strange cases I can think of:
reach candle count at final (minotaur trapped) location (tried leaving one and not leaving one - both WA)
reach candle count at penultimate location. Now Theseus could be smart and realise that the minotaur is trapped at this point so he doesn't leave a candle. But trying this still == WA.

what to do if candle count == 0? (this case doesn't happen though)
is there ever a case where Theseus leaves a candle in his initial cave?

Mart.
Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia
I agree with the conclusion about the initial position -- there's always a passage from Theseus to Minotaur. Maximum line length is between 700 and 750 chars -- I tested. So at least one statement in problem description is wrong.

I'm too curious about the case k == 0.

And one more thing: how do they notify a cavern from which you can't get out, for example all passeges are oneway starting from the other end?

Ivor
Mart
New poster
Posts: 18
Joined: Wed Jun 12, 2002 1:00 pm
You mean like:

A:C;B:C;D:C.

or:
A:C;B:C;C;D:C.

or maybe:
A:C;B:C;C:;D:C.

for ABD all going one way to C. My parser should cope with all those formats.

Hmm - I wonder if maybe there are self referring passages? or repeated passages? (that would give me an array overflow if the number from a single cave went above 26). Unlikely, but I think I might test for these cases...

Mart.
Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia
yeah, you did get my idea, but I don't know whether they have such testcases. I think I can cope with every one of them, but there must be something I am missing. but what?

Ivor
Mart
New poster
Posts: 18
Joined: Wed Jun 12, 2002 1:00 pm
I can't think of a testcase like that apart from those ones.

My thinking now is that it's a large number overflow problem. The number of moves in one of the problems gets over 2<<30 at least. I think my code would cope with it overflowing but still...

Mart.
Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia
What will it give you? In case, say k == 2^30, you won't manage to be in 30sec limit... that's personal opinion, but who knows?

I don't think this problem is that tricky, but I think there's something wrong with testcases... or there's some really tricky one...

Ivor
dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm
I have to admit, I'm doing no better. For some reason, I'm using way too much time. I'm frustrated first that this problem can't agree with itself. In the problem description, we see that Theseus lays down a candle in the first room he was in, but the output shows that he doesn't lay down his first candle until he reaches k! Anyway, if someone can see where I'm looping unnecessarily, please let me know!

@BEGIN_OF_SOURCE_CODE
// @JUDGE_ID: 2491CH 168 C++
#include
#include

using namespace std;

int main ()
{
char Input [255];
cin.getline (Input,255);

while (Input [0] != '#')
{
vector Maze [26];
short Minotaur, Theseus, Drop, i, CheckDrop = 0;
bool PermLit [26];

for (i = 0; i < 26; PermLit [i++] = false);

i = 0;

while (Input != '.')
{
short Code = Input - 'A';
for (i += 2; Input != '.' && Input != ';'; i++)
Maze

Code: Select all

``````.push_back (Input [i] - 'A');
if (Input [i] == ';')
i++;
}

Minotaur = Input [i + 2] - 'A';
Theseus = Input [i + 4] - 'A';
Drop = Input [i + 6] - '0';

short Temp = 1000;
while (i != Temp)
{
Temp = Maze [Minotaur].size ();
for (i = 0; i < Temp; i++)
{
if ((!PermLit [Maze [Minotaur] [i]]) &&
(Maze [Minotaur] [i] != Theseus))
{
Theseus = Minotaur;
Minotaur = Maze [Minotaur] [i];
CheckDrop += 1;

if (CheckDrop == Drop)
{
PermLit [Theseus] = true;
cout << char (Theseus + 'A') << ' ';
CheckDrop = 0;
}
break;
}
}
}

cout << '/' << char (Minotaur + 'A') << endl;
cin.getline (Input, 255);
}
}
@END_OF_SOURCE_CODE

Note: I've also tried a verson where Theseus is not allowed to move if there's no path between him and the minotaur.  But still got the out of time error.

A couple years ago I sent in a version that was originally accepted, then just recently rejected with PE.  Unfortunately, I don't have the code from then, and I haven't found a way to retrieve my code back from ACM.

David
[/cpp]``````
Mart
New poster
Posts: 18
Joined: Wed Jun 12, 2002 1:00 pm
Hi,

if you've got PE you're doing best than most of us... (even if you can't remember the code).

I don't agree about the problem description. It seems pretty clear from that point of view to me. It doesn't say that Theseus lays down a candle in the first cave.

In your code extra white space in the input is going to cause problems. Also, you seem to be assuming that the candle drop count is only a single digit?

The acception rate is going to get beneath 1% pretty soon...

Mart.
dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm