10802 - Lex Smallest Drive
Moderator: Board moderators
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...
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.")
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!
Thanks!
-
- 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.
Read the problem very carefully and try drawing several examples yourself.
If only I had as much free time as I did in college...
I need some clarification. Consider the following input:
Then, are all the followings valid drives from 0 to 3?
If so, no any finite drive is lexicographically smallest, right?
Code: Select all
1
4 4 0
0 1
1 2
2 0
0 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
...
Code: Select all
4 4 0
0 1
1 2
0 2
0 3
Case #2:
0
0 1
0 1 2
No drive.
Yes, that's also my understanding of the problem.Cho wrote:If so, no any finite drive is lexicographically smallest, right?
The problem statement says: If there is no [lexicographically smallest drive], print "No drive." Put an empty line after each test case.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???????
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."
-
- New poster
- Posts: 43
- Joined: Mon Oct 13, 2003 4:54 pm
- Location: Mexico
- Contact:
help me
my program got WA, please help me
INPUT:
OUTPUT (is correct ?)
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
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.
-
- 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...
-
- New poster
- Posts: 43
- Joined: Mon Oct 13, 2003 4:54 pm
- Location: Mexico
- Contact: