11183 - Teen Girl Squad

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11183 - Teen Girl Squad

Post by sunny » Mon Feb 26, 2007 12:44 pm

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

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Feb 26, 2007 12:58 pm

This is the directed minimum spanning tree problem.

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Mon Feb 26, 2007 1:20 pm

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?
thanks in Advance...
In being unlucky I have the record.

User avatar
Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:

Post by Hadi » 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?

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

Post by Monsoon » Mon Feb 26, 2007 6:13 pm

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
Location: Vancouver, BC, Canada
Contact:

Post by sclo » 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 :D
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


User avatar
fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

Post by fh » 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?
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:

Post by mf » Tue Feb 27, 2007 7:04 pm

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
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Tue Feb 27, 2007 9:22 pm

My testcase #2 requires the algorithm to break cycles 3 times.

User avatar
fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

Post by fh » Wed Feb 28, 2007 5:20 am

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:

Post by mf » 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}.

User avatar
fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

Post by fh » Wed Feb 28, 2007 7:56 am

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:

Post by mf » Wed Feb 28, 2007 8:44 am

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

User avatar
fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

Post by fh » 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!"
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
Location: Vancouver, BC, Canada
Contact:

Post by sclo » 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.

Post Reply

Return to “Volume 111 (11100-11199)”