10805 - Cockroach Escape Networks

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

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 » Sun May 01, 2005 12:43 am

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

Post by Destination Goa » Sun May 01, 2005 8:18 am

My solution outputs
2
2
run-time-error (duplicate edge) :lol:

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

Post by tan_Yui » Sun May 01, 2005 10:43 am

Abednego wrote:I think you misunderstood the problem. How could your print 1 for the first test case?
Thanks for your kind reply, Abednego, Destination Goa !

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.

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 » Sun May 01, 2005 10:24 pm

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

Post by tan_Yui » Mon May 02, 2005 3:33 pm

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

Post by Destination Goa » Mon May 02, 2005 8:14 pm

My answer is 4-3-4-3-3-2

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

Post by tan_Yui » Tue May 03, 2005 2:42 pm

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

Post by gaurav2289 » Sun Jan 18, 2015 12:20 am

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

Post by gaurav2289 » Sun Jan 18, 2015 4:35 am

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

Post Reply

Return to “Volume 108 (10800-10899)”