10802 - Lex Smallest Drive

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

Moderator: Board moderators

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

10802 - Lex Smallest Drive

Post by Dreamer#1 » Sun Jan 09, 2005 8:25 am

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Jan 09, 2005 8:59 am

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

Post by totster » Thu Jan 13, 2005 12:04 am

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

Thanks!

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Thu Jan 13, 2005 1:09 am

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

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Thu Jan 13, 2005 7:07 pm

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:

Post by technobug » Thu Jan 13, 2005 7:50 pm

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

Post by misof » Thu Jan 13, 2005 8:12 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:

Post by technobug » Thu Jan 13, 2005 8:20 pm

ahan....

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

help me

Post by lord_burgos » Fri Jan 14, 2005 10:23 pm

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.


User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Fri Jan 14, 2005 10:59 pm

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

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

Post by lord_burgos » Sat Jan 15, 2005 4:56 am

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

Post by Monsoon » Sun Jan 16, 2005 6:29 pm

Can be in the input edge connecting the same node?

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Sun Jan 16, 2005 6:43 pm

"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

Post by Monsoon » Sun Jan 16, 2005 7:16 pm

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

Post by misof » Sun Jan 16, 2005 9:45 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.

Post Reply

Return to “Volume 108 (10800-10899)”