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

DreamLinuxer
New poster
Posts: 8
Joined: Tue Oct 01, 2002 3:22 pm

Post by DreamLinuxer » Sun Jan 30, 2005 12:09 pm

I try many times and still get WA :(

Can someone give me more testdata? thx :D

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Thu Feb 03, 2005 2:28 pm

DreamLinuxer wrote:I try many times and still get WA :(

Can someone give me more testdata? thx :D
Hello, could someone give some hints to solve the problem?
I got a little confused :o , thx

Yeomin
New poster
Posts: 5
Joined: Tue Jul 20, 2004 3:32 pm
Location: Republic of Korea

Post by Yeomin » Fri Feb 04, 2005 2:16 pm

I get WA, also.

This is my test case.
1
10 11 0
0 1
1 2
0 3
3 4
4 5
5 3
0 6
6 7
7 8
8 6
0 9
and, my output.
Case #1:
0
0 1
0 1 2
0 3
0 3 4
0 3 4 5
0 3 4 5 3 0 6
0 3 4 5 3 0 6 7
0 3 4 5 3 0 6 7 8
No drive.
is this correct?

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 Feb 04, 2005 5:51 pm

Yes, this is correct.
If only I had as much free time as I did in college...

Yeomin
New poster
Posts: 5
Joined: Tue Jul 20, 2004 3:32 pm
Location: Republic of Korea

Post by Yeomin » Mon Feb 07, 2005 12:08 pm

Thx. I got accepted.

this is my last test case. If you got WA, check this input.

Code: Select all

2
10 5 5
5 0
0 1
1 2
2 0
5 9

10 5 5
5 0
0 6
6 7
7 0
5 9

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Tue Feb 15, 2005 6:12 pm

Dammit... I spent about 6 hours (finally my code had visited setter class and 'throw' clause) when simplest DFS solution without any respect to loops, trees, etc... etc... came to my head :)

Thank you guys for test data. Finally AC.
To be the best you must become the best!

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Feb 15, 2005 8:15 pm

You're lucky you finaly found a simple solution.
I ended up with a 150+ line program that colors edges in one of seven different colors and has functions with fancy names like explore_white(), explore_blue() and explore_yellow()...
Well, it works, and it's kinda fun...

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Wed Feb 16, 2005 1:27 am

Well, my very first idea was to run DFS until the very first loop occured. I was very surprised to get WA. Thought and thought... and came to this thread. Here I understood that some loops might be traversable just once to stay minimal. Then details started to appear... one by one (like a pair of loops which will be walked 1st-2nd-1st-2nd-... etc...). Still WA and WA. No single abort() worked. Finally I came to my original solution, but with respect to edges and direction we go.

You're lucky as well to get your headacheous code working. Mine didn't, expect it gave me a LOT of headache :(
To be the best you must become the best!

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 » Wed Feb 16, 2005 3:16 am

My first solution was exactly the same - look for the first loop and then abort. Then during the contest, someone sent me a clarification with a test case that had exactly that example - one loop traversed once. I fixed my solution, but it was still wrong. Only after the contest I managed to write something that gave correct answers.

Then Yeomin posted his awesome test case and asked whether his output was correct. I ran my solution and got a different answer. So my solution is still wrong, but there are no test cases that catch that difference.

Making problems is hard... :-)
If only I had as much free time as I did in college...

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Wed Feb 16, 2005 6:22 am

My solution in details is very simple. It's like that:

step(pos, prev)
{
// add 'pos' to the end of current path
// if 'pos' has no path recorded yet, store current path for it

for(;;)
{
// get the least node 'v != prev' with edge (pos;v), if none - break
// if (pos;v) was already traversed (direction matters), stop entire algo
// mark (pos;v) as traversed
// call 'step(v, pos)'
}

// remove 'pos' from the end of current path
}

Call 'step(start, -1)' to get the answer. Unrecorded nodes will have no drive.

It works because for sub-trees (no loops inside) it just walks and leaves as normal DFS does. For sub-trees with loops it always keeps the least path prefix for further nodes. If we reach something - it has least prefix so far, and since we reached it via lexicographically smallest sequence, this is the minimum. If we loop somewhere, all further nodes will have infinite prefix. Any break-out of the loop will be lexicographically worse then making one more iteration.

P.S: I have a serious question about 10805, please check that topic. Thank you.
To be the best you must become the best!

dispanser
New poster
Posts: 18
Joined: Wed May 01, 2002 4:12 pm
Location: Jena/Germany
Contact:

Post by dispanser » Mon Mar 07, 2005 8:44 am

Yeomin wrote:
1
10 11 0
0 1
1 2
0 3
3 4
4 5
5 3
0 6
6 7
7 8
8 6
0 9
and, my output.
Case #1:
0
0 1
0 1 2
0 3
0 3 4
0 3 4 5
0 3 4 5 3 0 6
0 3 4 5 3 0 6 7
0 3 4 5 3 0 6 7 8
No drive.
is this correct?
according to the problem setter, this is a correct solution. Even after reading the complete thread i still fail to see why it is. Considering the drive for vertex 6, wouldn't "0 3 4 5 3 4 5 3 0 6" be a drive that is lexicographicly smaller? I must be missing something? And if that is a drive, why is
"0 3 4 5 3 0 6 7 8 6 0 9" not a drive for vertex 9?

Yeomin
New poster
Posts: 5
Joined: Tue Jul 20, 2004 3:32 pm
Location: Republic of Korea

Post by Yeomin » Mon Mar 07, 2005 10:07 am

Because "0 3 4 5 3 0 6 7 8 6" can loop.

0 3 4 5 3 0 6 7 8 6 0 3 4 5 3 0 9 is smaller than 0 4 3 5 3 0 6 7 8 6 9.

And 0 3 4 5 3 0 6 7 8 6 0 3 4 5 3 0 6 7 8 6 0 3 4 5 3 0 9 is smaller.

And ....... Can't define Smallest 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 » Mon Mar 07, 2005 11:23 am

The key statement is, "A drive is smallest if there is no other drive that is smaller than it." This means that some vertices that are connected by a drive may have no smallest drive. Instead, they may have an infinite sequence of lexicographically decreasing drives.
If only I had as much free time as I did in college...

dispanser
New poster
Posts: 18
Joined: Wed May 01, 2002 4:12 pm
Location: Jena/Germany
Contact:

Post by dispanser » Mon Mar 07, 2005 11:48 am

Yeomin wrote:Because "0 3 4 5 3 0 6 7 8 6" can loop.

0 3 4 5 3 0 6 7 8 6 0 3 4 5 3 0 9 is smaller than 0 4 3 5 3 0 6 7 8 6 9.

And 0 3 4 5 3 0 6 7 8 6 0 3 4 5 3 0 6 7 8 6 0 3 4 5 3 0 9 is smaller.

And ....... Can't define Smallest drive.

ah now i see it... being at vertex 3, it's lex smaller to go to vertex 0, but the first time we visit vertex 3 we can't go to 0 as that's were we're coming from. That doesn't apply when traversing 6-->0 as the lexicographicly smallest would go to vertex 3 afterwards, and thus loop.

thanks for clearing that up!

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia

I know more lexicographically small drive

Post by StatujaLeha » Sun Sep 25, 2005 8:42 pm

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.
Abednego, I know more lexicographically small drive to vertex 4: 0 3 1 2 3 0 3 1 2 3 0 4 or 0 3 1 2 3 0 3 1 2 3 0 3 1 2 3 0 4. Why is your output correct?

Post Reply

Return to “Volume 108 (10800-10899)”