168 - Theseus and the Minotaur

[Lawrence]

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]

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.

[Lawrence]

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]

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 ?

[Martin Juvan]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

OK, I had a few epiphanies about this problem.

1) (see my code above) Nothing dictates that the drop number be less than 10. Need to allow for any size of number for k!

2) In fact, k could be zero. The program doesn't tell us how to handle this, but I would assume that this meant that Theseus would drop a candle in the first room, and in every room thereafter. k = 1 would be similar, but Theseus would NOT drop a candle in the first room.

3) What if k is an absurdly large number and the problem ends in a loop through just a few rooms. Maybe the problem is actually to find some kind of solution without actually following the problem through step by step. Maybe we're to try to analyze the intersections to determine where candles would be dropped when, instead of actually following the path. If this is the key, I don't want to know...

It is my guess that, since I kept getting looping errors, k can very much be zero. Or a multi-digit number. I have not thoroughly tested this, but that's my next attack.

David