## 11183 - Teen Girl Squad

Moderator: Board moderators

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

### 11183 - Teen Girl Squad

got so many WAs on this problem.
any test cases plz.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
This is the directed minimum spanning tree problem.

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:
sclo wrote:This is the directed minimum spanning tree problem.
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?
In being unlucky I have the record.

Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:
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?

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland
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?
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)) ?

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
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:

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

``````
Output:

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

``````

fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:
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?
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
fh wrote:Can somebody explain the meaning of pseudo-node?
Is pseudo-node achieved by replacing the nodes in the cycle into one node?
Yes.
Technically, you can implement it with a union-find structure, like in Kruskal's algorithm.
There are two cycles after step 1, and after 3 attempts to eliminate cycles, it will create another cycle when eliminating the cycle itself.
Which you can then again successfully contract into a single vertex.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
My testcase #2 requires the algorithm to break cycles 3 times.

fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:
sclo wrote:My testcase #2 requires the algorithm to break cycles 3 times.
I passed your testcase, but the testcase I mentioned above gives me headache. If you draw it, it'll go like this:

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.
``````
How to avoid this?
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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}.

fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:
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}.
I tried that way, but it doesn't yield an optimal result for sclo's second test case:

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://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

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
``````
No, no, no.
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.)

fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:
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!"
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm