10805 - Cockroach Escape Networks

[Abednego]

It's fixed now.

[Cosmin.ro]

AC at last.

[nnahas]

AC at last.

Well I am on the list of accepted solutions, but there's something weird. I didn't get an accepted notification, I only got Wrong Answer notifications, including after the fix. The error could be on my part, (maybe I made a successful submission, didn't notice which,and then modified the code and got wrong answer) but could someone check this?

Sorry if I made a really obvious error, I am new here, it's only the second problem I solve on UVA.

[Abednego]

All submissions got rejudged because the output file had changed. You might get an email saying that.

[nnahas]

All submissions got rejudged because the output file had changed. You might get an email saying that.

Ah, OK, your're right. And now I resubmitted a correct solution , and I got an accepted message. Thank you!

[..]

c-Try to find a BFS Tree such that all these nodes are descendants of the same child of v. if such a BFS tree exists , then there is a tree of diameter 2*MaxDist, otherwise all we can say is that there is a tree of diameter 2*MaxDist +1. That value will be an upper bound on the diameter.
the least upper bound will be the diameter of the optimal Tree T..

Hi nnahas,
I think these 2 distance should be 2*MaxDist-1 and 2*MaxDist.
Is that a trap for preventing people simply implement the algorithm?

[nnahas]

c-Try to find a BFS Tree such that all these nodes are descendants of the same child of v. if such a BFS tree exists , then there is a tree of diameter 2*MaxDist, otherwise all we can say is that there is a tree of diameter 2*MaxDist +1. That value will be an upper bound on the diameter.
the least upper bound will be the diameter of the optimal Tree T..

Hi nnahas,
I think these 2 distance should be 2*MaxDist-1 and 2*MaxDist.
Is that a trap for preventing people simply implement the algorithm?

No, in one of my previous messages in the thread I indicated that I used the same convention as Guang Williams , and that is to consider the diameter as the length of the longest path in the tree, where length is defined to be the number of nodes on the path, not the number of edges.
I'm sorry if that confused you, but my proof for the odd diameter case doesn't make any sense if you take the diameter to be the number of edges on the path.

[Destination Goa]

Well, I run BFS for every starting node, then I try to split EVERY edge in EVERY such tree, start a new BFS in split-point (over the graph, not over the tree), then form a spanning tree out of this post-split-BFS tree (by bringing deleted edge back and removing split point), then calculate diameter of each such tree.

All original BFS + all post-split-BFS trees are candidates for the answer. Obviously, my algo has a lot of redundancy (but still O(N^4)), but I manage constantly getting WA. Maybe suggested algo is wrong, and the way of BFS traversal is actually important? All BFS parts walk in lexicographic order.

I will now try to split all N^2 edges from he original graph yielding O(N^5). If even this fails, I will put my code here, so you may check test data (or my code which I doubt to contain mistakes without any heuristics and so much time spent with it).

Thanks.

[Destination Goa]

Well, when I tried to split all edges of original graph, I finally got AC. Though not 0.034 sec (namely 0.221 sec), but still O(N^4) - N^2 edges are split, then BFS'ed (x N^2), then diameter for underlying trees is evaluated (+N to recent factor).

I thought this happened due to rombus cases in BFS (where its construction becomes ambiguous), but trying all edges with depth=depth[j]+1, (i;j) in E - still gave WA. So even this seems to be not enough (after all, it's O(N^5) - N^2 edges per BFS). Currently I presume that generally original BFS'es are not related with split candidates at all.

All in all, that theorem gave me only frustration. The fact that after splitting some edge we might have minimum diameter spanning tree is useful, but that's all of it. Perhaps I coded it badly, but I don't think so. Too many assertions didn't fail. Too may ways of treatment were sent. And as long as I can stay at O(N^4) without caring of all those issues, I will

Yet, I am unsure that splitting of only one edge is enough. Such rather general problem with polynomial algorithm deserves being some famous classics. It's strange to find it in such a place (meaning link, not this problem) and never hear of it before. All of that makes it twice doubtful.

[Abednego]

As far as I know, this problem (minimum diameter spanning tree) has only recently (2004) been proved to be polynomial time. The only known algorithm and proof are in this unpublished paper by Yuqiang Guan: http://www.cs.utexas.edu/users/yguan/pa ... node2.html
I was really frustrated by his algorithm description (which I still think is wrong) and by his "proof" that simply claims a few things without proving any of them.

This cute little problem seems to have been disregarded or missed by everyone. I'm glad that Cosmin showed it to me, and I agree that it should be one of the classics.

[Destination Goa]

BTW, a few things more about that description:

1) It's strange that he counts diameter as number of nodes. It's generally defined as number of edges because even more generally it's defined as the longest path (path was sum of edges for all times).

2) Judge test data contains cases when BFS(r) gave d(T), but underlying spanning tree didn't give d(T)-1 in terms of that problem (checked with abort()).

3) After all, I am unsure that BFS is minimum. It may be proven that it minimizes cost from BFS root to two most distant chlidren, but it tells nothing about internal paths not involving BFS root node. Well, that was already mentioned in this branch.

I think his idea is right, but since this paper wasn't published, there is some typo(s) in that text. Anyway, all my efforts to fix it blindly by changing code flow at doubtful places, failed. I think I've checked all 2^k ways on those slippery places

[stubbscroll]

Hi, I'm trying to solve this problem (10805). I have read the link to the Guan algorithm/proof, but I have not yet understood exactly how the edge splitting works.

I have created two solutions, one brute force (which obviously only works on small cases) and a faster one (which gets WA) and compared them to each other, and they give identical output to all the random input I've generated so far. I think the WA is due to my misunderstanding of the edge splitting. I'd be very happy if someone could tell me how the edge splitting affects this test case:

Code: Select all

1
6 7
0 1
0 3
0 4
1 2
2 3
2 5
3 4

My BFS at vertex 2 transforms this into a tree with an edge diameter of 4 (2-1, 2-3, 2-5, 1-0, 3-4). My routine goes through all vertices at the maximum depth from the root note and tries to move them to another subtree such that all maxdepth vertices are descendants in the same subtree. Is this a correct understanding of the edge splitting or am I way off? (I hope the above was understandable.) Btw, the answer to the above case is 3.

[Abednego]

I don't think that this is what was meant by edge splitting, but the idea of moving leaf vertices to a single branch works, too. You must be missing a boundary case somewhere.

The edge splitting idea says that you should do a BFS starting at the edge 2-3. The easiest way to do this is to add both 2 and 3 to the queue with depth 0 and then proceed with the BFS as usual. This is equivalent to replacing edge 2-3 with an extra vertex, x, and two new edges x-2 and x-3.

[stubbscroll]

Thanks a lot for the explanation, Abednego! It was very hard to understand the article when the two pictures were missing, but with your help I got accepted. I guess my previous idea was correct, but it was much harder to implement, so I must have had a bug somewhere.

[tan_Yui]

Hi, everyone.
I tried this problem with BFS, and my code got Wrong Answer
My code outputs correct answer for all input on this board.

I think, this problem's solution is simple, BFS or other graph algorithm like Floyd Warshall. My BFS algorithm is following :

0. i = 0
1. Search the most farthest point from starting point i .
2. Store the length in to the array.
3. i++
4. if (i >= number of the node ) goto 5 else goto 1 .
5. find the biggest value from array.

I can't find my code bugs or algorithm. I want help.
If you got AC or PE, please check following I/O or provide me with some test input set.

Thank you.

Code: Select all

6
3 3
2 1
1 0
2 0
3 3
2 1
1 0
0 2
2 2
1 0
0 1
8 13
0 1
1 2
2 3
3 4
4 5
5 6
7 0
7 1
7 2
7 3
7 4
7 5
7 6
6 9
0 1
1 2
2 3
3 4
4 5
2 1
3 1
4 1
5 1
10 13
6 4
2 8
4 6
3 1
5 9
0 7
4 1
2 9
7 5
6 8
8 3
1 0
5 6

My output :

Code: Select all

Case #1:
1

Case #2:
2

Case #3:
1

Case #4:
6

Case #5:
5

Case #6:
8