10802 - Lex Smallest Drive

[DreamLinuxer]

I try many times and still get WA

Can someone give me more testdata? thx

[windows2k]

I try many times and still get WA

Can someone give me more testdata? thx

Hello, could someone give some hints to solve the problem?
I got a little confused , thx

[Yeomin]

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?

[Abednego]

Yes, this is correct.

[Yeomin]

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]

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.

[little joey]

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]

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

[Abednego]

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

[Destination Goa]

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.

[dispanser]

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]

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.

[Abednego]

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.

[dispanser]

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]

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?