10805 - Cockroach Escape Networks

Moderator: Board moderators

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
My solution prints the following for your input:

Code: Select all

``````Case #1:
2

Case #2:
2

Case #3:
1

Case #4:
2

Case #5:
2

Case #6:
5

``````
I think you misunderstood the problem. How could your print 1 for the first test case?
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
My solution outputs
2
2
run-time-error (duplicate edge)

Without that checking it outputs 2-2-1-2-2-5
To be the best you must become the best!

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
Abednego wrote:I think you misunderstood the problem. How could your print 1 for the first test case?

I think this problem's task is to find the longest path (Minmax).
The n-1 cockroaches move to other nests
(If their initial position are 0 and n==4, they move to 1 & 2 & 3).
They can use same trails with other cockroaches.
If they could't reach individual nests, their misson is failed.
They always choose the shortest path.
(If there are 1->3->2 (time==2) and 1->2 (time==1) paths, they choose 1->2 path (1<2).)

And, there will be no trails from a node to itself and no duplicate trails (thanks, Destination Goa).

3 3
2 1
1 0
2 0

Following is the image of above test case.

Code: Select all

``````+----------------------+
|
|   2 ------> 1
|   |         |
|   |         |
|   |         v
|   --------> 0
|
+----------------------+
``````
Initial position 0 :
they can't move, so the mission is failed.

Initial position 1 :
they can move only to '0', but they have to go '0' and '2', so the mission is failed.

Initial position 2 :
they can move to '0' and '1'. The shortest paths are 2->0 and 2->1.
Both length are 1, so the Emergency Response Time is 1.

Finally, from these results, the answer is 1.

.... but, my answer is wrong.
Could you tell me what's wrong ?

Best regards.

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
The edges are undirected. If a cockroach can go from 1 to 2 along a trail, then it can go from 2 to 1 along the same trail.]

So in the triangle example:

Code: Select all

``````3 3
2 1
1 0
2 0
``````
There is no need to keep all 3 trails. We will throw one of them away - doesn't matter which one; the problem is symmetric. We can't throw away 2 trails because that would disconnect a pair of nests, and we don't want that. So, say, we throw away "2 0". Then a cockroach that is running from 2 to 0 must go through 1, and it will take a time of 2. No cockroach will ever need a time of 3. So the answer is 2.
If only I had as much free time as I did in college...

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
I probably understand this problem's task.
I think, we can get the answer by this way (not consider efficiency) :

1. Make second map for node x with BFS.
Second map is indicated a tree with a root( = x ).

2. Find the longest paths for this tree.
Use BFS to the tree can make the longest path,
because this tree was also made by BFS.

3. Do step_1-2 while 0<=x<n

4. Find the shortest path from the result of step_2.

I changed my C code with above algorithm and submitted.... got WA
I want help again....

I prepared short input set.
Is this output correct?

Code: Select all

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

Code: Select all

``````Case #1:
4

Case #2:
4

Case #3:
4

Case #4:
3

Case #5:
3

Case #6:
2

``````
Best regards.

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

My AC solution performed edge-split (described earlier in this topic) on every edge. All weaker efforts failed, although they were more time-effective.
To be the best you must become the best!

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
Thanks, Destination Goa.

Code: Select all

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

Code: Select all

``````before action
0
/ | \
/  |   1
/   |   |
4 -- 3 - 2 - 5

after destroy the trails
0
|
|   1
|   |
4 -- 3 - 2 - 5
``````
My current algorithm couldn't find above answer '3'. I try to check my algo or change whole my code

Best regards.

gaurav2289
New poster
Posts: 10
Joined: Tue Jul 07, 2009 11:59 am
Location: Ithaca, NY

Re: 10805 - Cockroach Escape Networks

I cannot find the algorithm used to solve this problem. The link provided in the earlier posts is not working : http://www.cs.utexas.edu/users/yguan/pa ... node2.html

Can someone point me to the algorithm?

gaurav2289
New poster
Posts: 10
Joined: Tue Jul 07, 2009 11:59 am
Location: Ithaca, NY

Re: 10805 - Cockroach Escape Networks

I finally managed to get AC. For anyone else, this proved to be a great hint:

"In every tree there exists a point (possibly in the ‘middle’ of some edge) such that the distance of the furthest vertex from it is exactly half the diameter of the tree."

I just tried every possible such point ( including those in the middle of some edge ).