10805 - Cockroach Escape Networks

[Abednego]

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?

[Destination Goa]

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

Without that checking it outputs 2-2-1-2-2-5

[tan_Yui]

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.

[Abednego]

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.

[tan_Yui]

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]

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.

[tan_Yui]

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]

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]

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