Page 1 of 3
10802 - Lex Smallest Drive
Posted: Sun Jan 09, 2005 8:25 am
by 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...
Posted: Sun Jan 09, 2005 8:59 am
by 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.")
10802 - Lex Smallest Drive
Posted: Thu Jan 13, 2005 12:04 am
by 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!
Posted: Thu Jan 13, 2005 1:09 am
by 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.
Posted: Thu Jan 13, 2005 7:07 pm
by Cho
I need some clarification. Consider the following input:
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?
Posted: Thu Jan 13, 2005 7:50 pm
by technobug
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.
Posted: Thu Jan 13, 2005 8:12 pm
by misof
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."
Posted: Thu Jan 13, 2005 8:20 pm
by technobug
ahan....
help me
Posted: Fri Jan 14, 2005 10:23 pm
by 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.
Posted: Fri Jan 14, 2005 10:59 pm
by 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.
Posted: Sat Jan 15, 2005 4:56 am
by lord_burgos
Thanks , I got AC, in 0.041 and 64 K
Posted: Sun Jan 16, 2005 6:29 pm
by Monsoon
Can be in the input edge connecting the same node?
Posted: Sun Jan 16, 2005 6:43 pm
by Abednego
"each edge is a set of 2 vertices {u, v}".
Posted: Sun Jan 16, 2005 7:16 pm
by 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?
Posted: Sun Jan 16, 2005 9:45 pm
by 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.