11183  Teen Girl Squad
Moderator: Board moderators
11183  Teen Girl Squad
got so many WAs on this problem.
any test cases plz.
any test cases plz.

 Experienced poster
 Posts: 111
 Joined: Mon Jan 09, 2006 6:19 pm
 Location: Tehran, Iran
 Contact:
during the contest i have figured out that the problem could be solved with MST, but i have one problems, is it enough to start MST algorithm from the vertex which indegree is 0, or it has some blind spots?sclo wrote:This is the directed minimum spanning tree problem.
thanks in Advance...
In being unlucky I have the record.
For this problem, using "Prim" or "Kruskal" is not correct. they are for undirected graphs. you can find a counterexample easily if you try.
You should use Chu,Liu/Edmonds algorithm to solve this problem. for a brief description see http://www.ce.rit.edu/~sjyeec/dmst.html
But implementing it they way "what it says" will time out. (As our solution timed out during the contest)
Could anybody please give some hints on efficient implementations?
You should use Chu,Liu/Edmonds algorithm to solve this problem. for a brief description see http://www.ce.rit.edu/~sjyeec/dmst.html
But implementing it they way "what it says" will time out. (As our solution timed out during the contest)
Could anybody please give some hints on efficient implementations?
hmm, i have question to step 3. of this algo, i think that is sufficent to use this equation c(i,k)=c(i,j)(c(x(j),j), but i've WA, anyone could show me why we must substract min_{j}(c(x(j),j)) ?Hadi wrote:For this problem, using "Prim" or "Kruskal" is not correct. they are for undirected graphs. you can find a counterexample easily if you try.
You should use Chu,Liu/Edmonds algorithm to solve this problem. for a brief description see http://www.ce.rit.edu/~sjyeec/dmst.html
But implementing it they way "what it says" will time out. (As our solution timed out during the contest)
Could anybody please give some hints on efficient implementations?
min_{j}(c(x(j),j)) is a constant on each cycle, so I don't see why we even need that term either.
I'm just getting TLE.
(edit)
Never mind, i'm getting tle because a bug in my code for breaking cycles turns my program into an infinite loop.
After many many WA, I finally got AC
It is not necessary to consider use the term min_{j}(c(x(j),j)) to reassign edge weights. But it is necessary to reassign edge weights, my previous code forgot to do so and it got me many WA.
Heres some testcases:
Output:
I'm just getting TLE.
(edit)
Never mind, i'm getting tle because a bug in my code for breaking cycles turns my program into an infinite loop.
After many many WA, I finally got AC
It is not necessary to consider use the term min_{j}(c(x(j),j)) to reassign edge weights. But it is necessary to reassign edge weights, my previous code forgot to do so and it got me many WA.
Heres some testcases:
Code: Select all
8
4
4
0 1 5
0 2 6
1 3 5
2 3 1
9
16
0 1 4
0 2 4
1 2 1
1 3 2
2 1 1
3 4 1
3 5 3
4 2 2
4 3 1
5 6 1
5 7 2
6 4 3
6 5 1
7 8 1
8 7 1
8 6 2
6
11
0 1 10
0 2 10
0 5 5
1 2 8
5 1 2
2 4 6
3 2 4
3 1 7
4 3 3
4 5 3
5 3 9
6
11
0 1 1
0 2 10
0 5 5
1 2 8
1 5 2
2 4 6
3 2 4
3 1 7
4 3 3
5 4 11
5 3 9
2
1
0 1 10
2
1
1 0 10
4
4
0 1 10
0 2 10
1 3 20
2 3 30
4
4
0 1 10
1 2 20
2 0 30
2 3 100
Code: Select all
Case #1: 12
Case #2: 15
Case #3: 24
Case #4: 20
Case #5: 10
Case #6: Possums!
Case #7: 40
Case #8: 130
Can somebody explain the meaning of pseudonode?
Is pseudonode achieved by replacing the nodes in the cycle into one node?
I tried to update the weight of all incoming edges to the cycle and then pick the smallest one and replace to it. However, my attempt to eliminate a cycle leads to creating another cycle! This is one of the case:
1
7
9
1 2 1
2 3 1
3 1 1
4 5 1
5 6 1
6 4 1
4 2 2
3 6 2
0 3 1000
There are two cycles after step 1, and after 3 attempts to eliminate cycles, it will create another cycle when eliminating the cycle itself.
Do we need to check whether the replacement edge should not lead to another cycle? because this checking step is not mentioned in the algorithm. Am I missing something?
Is pseudonode achieved by replacing the nodes in the cycle into one node?
I tried to update the weight of all incoming edges to the cycle and then pick the smallest one and replace to it. However, my attempt to eliminate a cycle leads to creating another cycle! This is one of the case:
1
7
9
1 2 1
2 3 1
3 1 1
4 5 1
5 6 1
6 4 1
4 2 2
3 6 2
0 3 1000
There are two cycles after step 1, and after 3 attempts to eliminate cycles, it will create another cycle when eliminating the cycle itself.
Do we need to check whether the replacement edge should not lead to another cycle? because this checking step is not mentioned in the algorithm. Am I missing something?
Visit my script to hunt UVA problem here:
http://felixhalim.net/uva/hunting/

Felix Halim
http://felixhalim.net/uva/hunting/

Felix Halim
Yes.fh wrote:Can somebody explain the meaning of pseudonode?
Is pseudonode achieved by replacing the nodes in the cycle into one node?
Technically, you can implement it with a unionfind structure, like in Kruskal's algorithm.
Which you can then again successfully contract into a single vertex.There are two cycles after step 1, and after 3 attempts to eliminate cycles, it will create another cycle when eliminating the cycle itself.
I passed your testcase, but the testcase I mentioned above gives me headache. If you draw it, it'll go like this:sclo wrote:My testcase #2 requires the algorithm to break cycles 3 times.
Code: Select all
Graph:
0 +> 2 < 4 +
   ^ 
  v  v
 1 < 3 > 6 < 5
 ^
 
++
Edge cost from node 0 to 3 is 1000, the rest are 1.
Step 1, select minimum incoming arc for each node except root:
0 +> 2 4 +
  ^ 
 v  v
1 < 3 6 < 5
Step 2, break cycle 456:
0 +> 2 4 +
  ^ 
 v  v
1 < 3 > 6 5
Step 3, break cycle 123:
0 2 < 4 +
 ^ 
v  v
1 < 3 > 6 5
Step 4, break cycle 2463:
0 +> 2 4 +
  ^ 
 v  v
1 < 3 > 6 5
Now, does this graph rings a bell?
It's the same as step 2 above!
Now, it's an endless loop.
Visit my script to hunt UVA problem here:
http://felixhalim.net/uva/hunting/

Felix Halim
http://felixhalim.net/uva/hunting/

Felix Halim
When you detect that there's a cycle, you should merge all vertices of the cycle into one, and replace any edges entering a vertex in the cycle by edges pointing to that new big one vertex.
Thus, in your example after steps 2 and 3, you will have three vertices: 0, {4,5,6} and {1,2,3}.
In step 4, merge vertices {1,2,3} and {4,5,6} into {1,2,3,4,5,6}.
Thus, in your example after steps 2 and 3, you will have three vertices: 0, {4,5,6} and {1,2,3}.
In step 4, merge vertices {1,2,3} and {4,5,6} into {1,2,3,4,5,6}.
I tried that way, but it doesn't yield an optimal result for sclo's second test case:mf wrote:When you detect that there's a cycle, you should merge all vertices of the cycle into one, and replace any edges entering a vertex in the cycle by edges pointing to that new big one vertex.
Thus, in your example after steps 2 and 3, you will have three vertices: 0, {4,5,6} and {1,2,3}.
In step 4, merge vertices {1,2,3} and {4,5,6} into {1,2,3,4,5,6}.
Code: Select all
9
16
0 1 4
0 2 4
1 2 1
1 3 2
2 1 1
3 4 1
3 5 3
4 2 2
4 3 1
5 6 1
5 7 2
6 4 3
6 5 1
7 8 1
8 7 1
8 6 2
Here is the graph for that input:
4 2 3 2
0 > 1 > 3 > 5 > 7
 ^ ^ ^ ^
    
  1  1  1  1
    
 4 v 2 v 3 v 2 v
+> 2 < 4 < 6 < 8
Step 1, assign minimum incoming edge to each vertex:
0 1 3 5 7
^ ^ ^ ^
   
 1  1  1  1
   
v v v v
2 4 6 8
union set: {0}, {1,2}, {3,4}, {5,6}, {7,8}
Step 2, resolve cycle {1,2}, {3,4}, {5,6}, {7,8}:
// question: is it allowed to resolve many cycles in one step?
2 2
0 1 > 3 5 > 7
^  ^ 
   
 1  1  1  1
   
 2 v  2 v
2 < 4 6 < 8
union set: {0}, {1,2,3,4}, {5,6,7,8}
Step 3, resolve cycle {5,6,7,8}:
2 3 2
0 1 > 3 > 5 > 7
^  
  
 1  1  1
  
 2 v 2 v
2 < 4 6 < 8
union set: {0}, {1,2,3,4,5,6,7,8}
Step 3, resolve cycle {1,2,3,4}:
2 3 2
0 1 > 3 > 5 > 7
 ^  
   
  1  1  1
   
 4  v 2 v
+> 2 4 6 < 8
Terminates with cost = 16
Whereas the optimum result is 15:
4 2 3 2
0> 1 > 3 > 5 > 7
   
   
 1  1  1  1
   
v v v v
2 4 6 8
How do you get 15? Is the order of resolving cycle matters?
Visit my script to hunt UVA problem here:
http://felixhalim.net/uva/hunting/

Felix Halim
http://felixhalim.net/uva/hunting/

Felix Halim
No, no, no.Code: Select all
Step 3, resolve cycle {5,6,7,8}: 2 3 2 0 1 > 3 > 5 > 7 ^       1  1  1     2 v 2 v 2 < 4 6 < 8
Vertices 5,6 and 7,8 were previously already bound together in deeper cycles. Instead of "resolving cycle {5,6,7,8}", you actually should be
dealing with the cycle {{5,6}, {7,8}}. You can resolve it by adding an edge from {5,6} to {7,8} (that'll be 5>7 of cost 2), and then resolve each of cycles {5,6} and {7,8} separately.
The whole point of this cycle contraction is that you can contract cycles each into a single vertex, reweight some edges, find directed MST of the new graph (try to draw this graph, that'll help you to understand the idea), and then get back at your original graph by expanding the cycles and deleting one of their edges. (But the problem statement doesn't ask you to find the edges of MST, so you can skip the last step in your code.)
Ok I got it Accepted. Thanks sclo for the sample cases and mf for the explanation.
I miss the fact that return 1 can happen not only when step 1 fails but also when it fails in resolving cycles. I added a simple check and got Accepted.
This is the input that have no solution that I missed:
7 8
1 2 1
2 3 1
3 1 1
4 5 1
5 6 1
6 4 1
4 2 2
3 6 2
Output should be "Possums!"
I miss the fact that return 1 can happen not only when step 1 fails but also when it fails in resolving cycles. I added a simple check and got Accepted.
This is the input that have no solution that I missed:
7 8
1 2 1
2 3 1
3 1 1
4 5 1
5 6 1
6 4 1
4 2 2
3 6 2
Output should be "Possums!"
Visit my script to hunt UVA problem here:
http://felixhalim.net/uva/hunting/

Felix Halim
http://felixhalim.net/uva/hunting/

Felix Halim