## 10802 - Lex Smallest Drive

Moderator: Board moderators

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

### 10802 - Lex Smallest Drive

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

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
New poster
Posts: 4
Joined: Sun Dec 12, 2004 12:28 pm

### 10802 - Lex Smallest Drive

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
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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.
If only I had as much free time as I did in college...

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
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
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

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
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
Cho wrote:If so, no any finite drive is lexicographically smallest, right?
Yes, that's also my understanding of the problem.
technobug wrote: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
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:
ahan....

lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:

### 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
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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.
If only I had as much free time as I did in college...

lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:
Thanks , I got AC, in 0.041 and 64 K

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland
Can be in the input edge connecting the same node?

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
"each edge is a set of 2 vertices {u, v}".
If only I had as much free time as I did in college...

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland
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
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
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.