10802 - Lex Smallest Drive

[Dreamer#1]

sorry for posting here but i couldn't think of a 2nd option...

let us consider a graph where there is a drive such as "5 0 1 5 4" now when we are to print the lexicographically smallest drive from 5 to 4 what do we output?

if i'm not wrong "5 0 1 5 0 1 5 4" is lexographically smaller than "5 0 1 5 4" and similarly we can have even smaller drives which are valid according to problem statement because no edge is used twice consecutively here. no where in the problem statement anything is mentioned about the length of the drives so i guess here there is no constraint that lets us have a finite output for such a graph.

apart from this confusion the problem seems pretty straight forward and since many people got AC so i must be missing something silly here. can someone please enlighten me.

regards...

[Adrian Kuegel]

Your observation about an infinite length in such case is correct. But as mentioned in a clarification given for this problem, you should also print "No drive." if there is no clearly defined lexicographically smallest drive (like here). Read also the 2nd clarification for that problem. It shows this problem is more difficult than it looks first. The mistake mentioned there is in the last output line, which should be 0 1 2 3 1 0 4 (not 0 1 2 3 1 2 3 ... which would lead to "No drive.")

[totster]

I solved this problem during the contest but I get WA now. Is there anything I need to know, anything that was changed?

Thanks!

[Abednego]

Yes, something was changed. My original solution was wrong. Note that now there are 2 sample input cases. I thought that the second one was the tricky case, but now someone has showed me a case that is even more triky.

Read the problem very carefully and try drawing several examples yourself.

[Cho]

I need some clarification. Consider the following input:

Code: Select all

1
4 4 0
0 1
1 2
2 0
0 3

Then, are all the followings valid drives from 0 to 3?

Code: Select all

0 3
0 1 2 0 3
0 1 2 0 1 2 0 3
0 1 2 0 1 2 0 1 2 0 3
...

If so, no any finite drive is lexicographically smallest, right?

[technobug]

Code: Select all

4 4 0
0 1
1 2
0 2
0 3

The sample says there is a connection from 0 to 3.... why does the answer says that there is no drive while it says there is a drive from 0 to 1???????

Case #2:
0
0 1
0 1 2
No drive.

[misof]

If so, no any finite drive is lexicographically smallest, right?

Yes, that's also my understanding of the problem.

The sample says there is a connection from 0 to 3.... why does the answer says that there is no drive while it says there is a drive from 0 to 1???????

The problem statement says: If there is no [lexicographically smallest drive], print "No drive." Put an empty line after each test case.

Note that this is different from saying: If there is no drive, print "No drive."

In the example you quote there are infinitely many drives from 0 to 3, but none of them is lexicographically smallest. Thus the correct output is "No drive."

[technobug]

ahan....

[lord_burgos]

my program got WA, please help me

INPUT:

Code: Select all

3
6 15 3
1 5
1 4
0 3
1 2
4 0
4 5
2 3
0 5
3 1
4 3
5 2
2 4
1 0
0 2
5 3
13 71 2
11 9
9 8
8 5
9 12
3 10
3 6
1 10
8 10
12 8
6 4
4 1
2 6
0 5
3 5
0 3
9 5
1 5
2 0
7 8
3 7
10 9
2 3
2 4
7 2
7 12
4 10
12 11
0 1
10 2
6 12
11 10
1 7
7 10
8 2
6 1
12 5
9 3
8 3
7 11
11 2
4 9
7 6
8 1
4 3
9 2
5 6
5 2
3 1
3 12
9 0
0 11
0 12
11 6
1 11
4 7
4 11
0 6
4 0
12 4
11 3
8 0
11 8
9 1
5 7
4 8
2 12
6 8
7 0
1 12
10 12
4 5
14 64 0
13 2
6 11
0 10
11 5
7 11
2 4
5 13
13 7
3 4
10 9
13 1
8 6
12 8
1 3
13 11
3 9
0 8
6 2
13 9
2 10
0 3
1 10
10 4
5 8
10 6
9 1
3 12
5 1
10 11
12 0
3 11
6 13
6 7
4 1
6 5
12 10
8 1
8 2
11 0
5 4
12 4
13 4
7 1
3 6
4 9
8 9
13 3
12 5
7 5
9 6
11 8
0 4
3 10
2 1
3 2
5 0
0 6
0 9
3 5
9 7
10 5
8 3
9 11
13 8

OUTPUT (is correct ?)

Code: Select all

Case #1:
3 0
3 0 1
3 0 1 2
3
3 0 1 2 4
3 0 1 2 4 5

Case #2:
2 0
2 0 1
2
2 0 1 3
2 0 1 3 4
2 0 1 3 4 5
2 0 1 3 4 5 6
2 0 1 3 4 5 6 7
2 0 1 3 4 5 6 7 8
2 0 1 3 4 5 6 7 8 9
2 0 1 3 4 5 6 7 8 9 10
2 0 1 3 4 5 6 7 8 9 10 11
2 0 1 3 4 5 6 7 8 9 10 11 12

Case #3:
0
0 3 1
0 3 1 2
0 3
0 3 1 2 4
0 3 1 2 4 5
0 3 1 2 4 5 6
0 3 1 2 4 5 6 7
0 3 1 2 4 5 6 7 9 8
0 3 1 2 4 5 6 7 9
0 3 1 2 4 5 6 7 9 8 11 10
0 3 1 2 4 5 6 7 9 8 11
0 3 1 2 4 5 6 7 9 8 11 10 12
No drive.

[Abednego]

My solution outputs this:

Code: Select all

Case #1:
3 0
3 0 1
3 0 1 2
3
No drive.
No drive.

Case #2:
2 0
2 0 1
2
2 0 1 3
No drive.
No drive.
No drive.
No drive.
No drive.
No drive.
No drive.
No drive.
No drive.

Case #3:
0
0 3 1
0 3 1 2
0 3
0 3 1 2 3 0 4
No drive.
No drive.
No drive.
No drive.
No drive.
No drive.
No drive.
No drive.
No drive.

[lord_burgos]

Thanks , I got AC, in 0.041 and 64 K

[Monsoon]

Can be in the input edge connecting the same node?

[Abednego]

"each edge is a set of 2 vertices {u, v}".

[Monsoon]

But there isn't wrote that an edge is a set of two different vertices, so i understand it that can u=v, am i right?

[misof]

The usual notion is that in a set there are no duplicate elements. I assume this is what Abednego is trying to say, hence the answer to your question should be no.