10805  Cockroach Escape Networks
Moderator: Board moderators
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?Cosmin.ro wrote:AC at last.
Sorry if I made a really obvious error, I am new here, it's only the second problem I solve on UVA.
Hi nnahas,nnahas wrote: cTry 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..
I think these 2 distance should be 2*MaxDist1 and 2*MaxDist.
Is that a trap for preventing people simply implement the algorithm?
My signature:
 Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.  I HATE testing account.
 Don't send me source code for debug.
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... wrote:Hi nnahas,nnahas wrote: cTry 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..
I think these 2 distance should be 2*MaxDist1 and 2*MaxDist.
Is that a trap for preventing people simply implement the algorithm?
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.

 Experienced poster
 Posts: 123
 Joined: Thu Feb 10, 2005 4:46 am
Well, I run BFS for every starting node, then I try to split EVERY edge in EVERY such tree, start a new BFS in splitpoint (over the graph, not over the tree), then form a spanning tree out of this postsplitBFS tree (by bringing deleted edge back and removing split point), then calculate diameter of each such tree.
All original BFS + all postsplitBFS 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.
All original BFS + all postsplitBFS 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.
To be the best you must become the best!

 Experienced poster
 Posts: 123
 Joined: Thu Feb 10, 2005 4:46 am
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.
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.
To be the best you must become the best!

 A great helper
 Posts: 281
 Joined: Tue Sep 10, 2002 5:14 am
 Location: Mountain View, CA, USA
 Contact:
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.
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.
If only I had as much free time as I did in college...

 Experienced poster
 Posts: 123
 Joined: Thu Feb 10, 2005 4:46 am
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
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
To be the best you must become the best!

 Experienced poster
 Posts: 151
 Joined: Tue Nov 16, 2004 7:23 pm
 Location: Norway
 Contact:
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:
My BFS at vertex 2 transforms this into a tree with an edge diameter of 4 (21, 23, 25, 10, 34). 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.
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

 A great helper
 Posts: 281
 Joined: Tue Sep 10, 2002 5:14 am
 Location: Mountain View, CA, USA
 Contact:
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 23. 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 23 with an extra vertex, x, and two new edges x2 and x3.
The edge splitting idea says that you should do a BFS starting at the edge 23. 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 23 with an extra vertex, x, and two new edges x2 and x3.
If only I had as much free time as I did in college...

 Experienced poster
 Posts: 151
 Joined: Tue Nov 16, 2004 7:23 pm
 Location: Norway
 Contact:
I got Wrong Answer
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.
My output :
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
Code: Select all
Case #1:
1
Case #2:
2
Case #3:
1
Case #4:
6
Case #5:
5
Case #6:
8