11183 - Teen Girl Squad
Posted: Mon Feb 26, 2007 12:44 pm
got so many WAs on this problem.
any test cases plz.
any test cases plz.
Page 1 of 2
Posted: Mon Feb 26, 2007 12:58 pm
This is the directed minimum spanning tree problem.
Posted: Mon Feb 26, 2007 1:20 pm
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...
Posted: Mon Feb 26, 2007 4:27 pm
For this problem, using "Prim" or "Kruskal" is not correct. they are for undirected graphs. you can find a counter-example 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?
Posted: Mon Feb 26, 2007 6:13 pm
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 counter-example 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?
Posted: Mon Feb 26, 2007 9:11 pm
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
Posted: Tue Feb 27, 2007 2:48 pm
Can somebody explain the meaning of pseudo-node?
Is pseudo-node 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 pseudo-node 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?
Posted: Tue Feb 27, 2007 7:04 pm
Yes.fh wrote:Can somebody explain the meaning of pseudo-node?
Is pseudo-node achieved by replacing the nodes in the cycle into one node?
Technically, you can implement it with a union-find 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.
Posted: Tue Feb 27, 2007 9:22 pm
My testcase #2 requires the algorithm to break cycles 3 times.
Posted: Wed Feb 28, 2007 5:20 am
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 4-5-6:
0 +--> 2 4 ---+
| | ^ |
| v | v
1 <- 3 --> 6 5
Step 3, break cycle 1-2-3:
0 2 <-- 4 ---+
| ^ |
v | v
1 <- 3 --> 6 5
Step 4, break cycle 2-4-6-3:
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.
Posted: Wed Feb 28, 2007 6:58 am
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}.
Posted: Wed Feb 28, 2007 7:56 am
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?
Posted: Wed Feb 28, 2007 8:44 am
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.)
Posted: Wed Feb 28, 2007 9:07 pm
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!"
Posted: Wed Feb 28, 2007 9:21 pm
Alternatively, you can do a dfs at the beginning to determine whether each node is reachable from the starting node. If they are all reachable, then the algorithm guarantees it will always find the minimum spanning tree.