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

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Thu Mar 01, 2007 3:44 am

There is a very simple and beautiful algorithm by Fulkerson:
http://www.springerlink.com/content/t628212211v86275/
If only I had as much free time as I did in college...

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

Post by mf » Thu Mar 01, 2007 8:28 am

Abednego wrote:There is a very simple and beautiful algorithm by Fulkerson:
http://www.springerlink.com/content/t628212211v86275/
Could you outline it here?

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Thu Mar 01, 2007 8:43 am

mf wrote:Could you outline it here?
Read the paper. :) It's very simple.

The basic idea is this. Suppose you wanted to find a good lower bound on the weight of the minimum rooted tree. Here is a good candidate. For each non-zero vertex, take the smallest incoming edge. Clearly, each vertex needs to have an incoming edge, and it can't be smaller than the smallest one.

If the resulting set of n-1 edges is already a tree, then we are done.Otherwise, there is only one thing that can happen - we get jellyfish. More precisely, we get a single tree rooted at zero and any number of graphs that look like trees, rooted at a cycle (what I call jellyfish).

The next step is to take each cycle and compress it into a single vertex, so we get trees instead of jellyfish. If you spend 10 minutes thinking about what it means to compress a cycle into a vertex in this case, you'll see that we'll need to change the weights of all the edges that enter the cycle. The change is very simple - their weights will decrease by the weight of the edge we are currently using at the entrance vertex.

After we compress cycles, we simply start over, only this time, we have strictly fewer vertices.

The paper is pretty short and explains this well.
If only I had as much free time as I did in college...

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

Post by mf » Thu Mar 01, 2007 8:53 am

Actually, I think that's exactly the same algorithm everyone here is using :)
The first google hit for directed mst calls it Chu-Liu/Edmonds' algorithm, though.
Abednego wrote:Read the paper. :) It's very simple.
The link you've posted asks me to pay $32 :(

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Thu Mar 01, 2007 9:01 am

mf wrote:The link you've posted asks me to pay $32 :(
Ah. Evil Springer. I can get it from my university's computers. If you send me a private message with your email address, I'll email you the paper.

[To anyone from Springer reading this: Of course I'm joking. I would never try to distribute and publicise research done over 30 years ago that you managed to grab the rights to. That wouldn't be very professional of me, and would hurt the scientific community.]
If only I had as much free time as I did in college...

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

Post by fh » Thu Mar 01, 2007 3:04 pm

Does the paper talk about the implementations?

When the jellyfish is compressed into a single vertex, the will be many parallel edges go in/out from that vertex. We should keep the minimum one to keep the graph simple. However, the graph is now changed.

It's fortunate that in this problem (11183) only asks the minimum weight of the directed MST. How about If we are asked which edges from the original graph belong to the directed MST, it would be much harder. Isn't it? How do we keep track the original edges when compressing the jellyfish? Does the paper talk about it?
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Thu Mar 01, 2007 4:39 pm

It would not be much harder. The trick is to do the compression using Union/Find. Then you don't even need to change the graph. After you compress, whenever you see an edge (u, v), you simply treat it as an edge (Find(u), Find(v)).
If only I had as much free time as I did in college...

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

Post by fh » Thu Mar 01, 2007 6:20 pm

Abednego wrote:It would not be much harder. The trick is to do the compression using Union/Find. Then you don't even need to change the graph. After you compress, whenever you see an edge (u, v), you simply treat it as an edge (Find(u), Find(v)).
IMHO, using union/find does not keep the graph unchanged since to compress the jellyfish, the incoming edges' weight must be reduced for the resulting vertex. (or there is a trick to avoid altering the edges' weight?)

After that, if there is a change of selected incoming edge for that vertex it becomes more confusing to update. It's easy to calculate Find(u) = x, but to update the edge in the "original" graph, we need the inverse Find(x) to get back the u and other possible vertices..

Does anyone here got AC without changing the graph? and able to give one of the possible Directed MST graph (the selected d-mst edges from the input)?[/b]
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

s000015
New poster
Posts: 5
Joined: Sat Oct 08, 2005 1:56 pm
Location: Taiwan

Post by s000015 » Sat Mar 03, 2007 5:42 pm

My program yielded correct result for test cases above,
but I still got WA...

Here is some random test cases:

Code: Select all

15
4 14
3 1 4
3 1 3
3 2 3
3 2 6
1 3 9
3 1 5
2 0 9
0 1 8
0 2 8
3 1 2
2 1 3
1 3 7
1 3 5
1 0 1
4 17
3 0 6
3 0 3
1 2 8
2 3 4
0 1 4
0 1 3
3 2 7
3 1 4
1 2 2
1 0 8
0 2 3
3 1 3
3 2 6
3 2 2
3 1 0
3 0 7
3 1 0
4 18
0 2 0
3 2 3
3 2 4
3 2 8
3 2 2
0 1 8
1 2 2
0 1 3
1 3 8
3 0 2
0 2 6
0 2 0
1 3 0
2 3 9
1 0 5
0 3 8
1 2 0
0 2 4
5 19
4 3 1
1 0 4
3 4 7
4 2 6
4 0 6
3 0 2
0 2 4
2 3 9
0 1 7
4 2 2
1 0 7
2 3 2
4 2 5
2 3 7
1 2 2
3 4 6
3 4 6
1 0 6
1 2 9
5 22
1 4 6
4 1 5
3 0 9
0 4 8
1 3 1
1 3 7
1 4 9
4 0 2
3 0 9
4 0 2
1 0 8
3 2 9
1 0 1
3 2 6
0 3 9
2 4 4
1 4 3
0 1 0
1 3 2
3 2 3
3 1 0
4 2 9
5 24
3 0 3
2 1 2
1 0 7
0 3 6
3 0 9
2 4 0
0 1 9
3 0 4
1 4 2
3 2 3
2 0 3
1 4 9
2 0 9
3 4 1
1 0 0
1 0 7
4 0 1
3 0 2
0 1 0
0 1 1
4 1 4
3 4 0
1 0 4
0 2 5
5 27
2 0 6
2 0 3
1 4 6
3 4 0
3 0 2
0 1 8
0 4 1
1 0 0
3 0 9
3 2 0
2 0 2
3 2 4
3 0 5
2 4 4
4 1 8
0 3 9
4 0 8
2 3 4
4 3 7
0 1 8
4 0 4
1 2 0
0 3 0
2 1 3
0 4 2
3 1 5
4 0 0
5 30
1 3 5
1 2 4
4 0 6
4 3 3
2 3 2
1 2 1
0 2 6
3 0 9
3 1 4
4 3 9
0 3 4
1 3 3
3 1 5
1 4 5
0 2 7
4 3 8
2 0 5
2 4 3
3 4 7
1 0 6
4 2 1
0 2 4
2 3 8
1 0 1
0 1 6
4 2 0
4 2 3
3 1 6
4 3 7
4 1 6
5 32
1 2 2
3 0 3
3 4 4
0 4 6
4 0 8
1 3 1
3 0 5
4 0 3
2 4 9
0 4 4
0 4 1
3 0 9
0 3 4
4 0 5
2 3 4
1 2 2
1 3 2
0 4 2
4 3 9
2 4 0
3 4 7
0 3 2
0 2 6
2 4 9
1 4 7
4 3 7
1 4 5
3 2 3
2 3 1
0 1 4
3 4 8
4 0 3
5 32
1 4 7
0 1 8
4 0 8
1 2 7
2 3 6
3 4 0
1 2 8
1 4 6
3 0 8
3 4 7
4 1 9
4 2 1
1 2 1
1 0 4
3 2 2
4 1 9
2 0 5
0 2 8
3 1 0
0 2 2
4 1 9
4 0 5
2 0 0
2 3 7
2 1 4
0 2 1
0 2 8
1 2 6
0 3 8
3 1 3
3 0 4
2 4 5
5 36
3 2 0
0 1 9
3 0 3
4 3 8
0 1 0
0 2 4
4 0 9
3 4 9
4 2 2
2 1 5
1 2 1
1 2 9
4 0 2
2 0 0
2 4 3
2 0 2
0 2 0
3 0 3
3 4 1
1 0 2
3 2 6
3 1 4
4 2 4
1 2 2
3 1 8
3 0 1
2 3 4
4 0 1
3 2 0
4 2 2
2 0 7
0 2 5
1 2 2
2 1 6
2 4 8
2 3 7
5 40
2 4 5
1 3 4
0 3 8
4 2 5
3 4 6
4 3 4
0 2 8
0 2 0
1 0 5
4 1 6
3 2 6
1 2 4
0 1 2
4 1 9
3 4 8
4 1 4
4 0 1
4 3 5
1 0 0
4 3 6
4 2 8
0 2 4
4 2 9
1 0 3
4 2 1
3 0 8
2 4 1
4 2 6
0 4 9
4 2 3
3 2 4
4 0 2
1 4 7
1 4 4
0 4 5
3 4 5
3 4 1
4 3 2
3 4 9
0 3 7
5 40
4 3 5
3 2 2
0 1 0
1 3 3
4 0 0
2 1 4
2 3 4
4 2 3
3 4 3
0 3 4
2 3 8
0 2 7
1 3 2
2 4 8
0 1 1
0 3 3
2 4 5
3 4 3
3 2 5
4 2 8
1 3 2
1 2 5
0 4 4
3 1 1
4 2 7
2 4 3
3 0 0
2 1 6
3 1 7
1 4 1
0 1 9
3 1 4
0 1 3
0 2 6
2 4 6
2 4 2
1 4 6
2 3 8
2 0 7
0 2 2
5 44
3 0 7
0 2 8
4 0 5
1 3 9
4 3 1
1 2 6
4 0 9
0 3 1
2 4 3
0 2 1
4 2 6
2 1 0
3 4 1
1 2 7
2 0 2
2 1 9
4 0 8
0 2 6
2 3 1
3 2 9
2 3 0
2 1 1
2 3 0
2 4 7
3 2 5
1 4 8
4 3 7
4 0 0
2 1 7
3 2 4
3 2 3
2 3 3
2 3 9
0 2 0
1 0 0
3 1 0
0 3 8
1 3 7
1 3 3
2 3 4
0 4 3
2 1 9
4 1 3
2 0 0
5 44
4 0 2
0 4 4
0 3 5
2 3 6
1 2 6
2 3 5
4 1 2
0 2 8
1 2 7
4 2 5
1 3 6
0 2 2
1 3 3
0 4 2
4 2 2
1 2 0
1 4 7
4 0 5
4 2 4
3 1 5
2 1 5
4 2 7
0 1 6
2 3 2
2 0 8
4 3 0
3 0 0
1 0 1
3 0 7
0 1 2
2 3 9
1 2 4
0 4 3
0 3 6
3 1 6
3 0 7
1 4 8
0 1 2
4 0 2
1 0 2
3 4 9
0 2 5
2 3 8
0 4 9
Output:

Code: Select all

Case #1: 16
Case #2: 7
Case #3: 3
Case #4: Possums!
Case #5: 7
Case #6: 9
Case #7: 3
Case #8: 13
Case #9: 7
Case #10: 7
Case #11: 5
Case #12: 5
Case #13: 5
Case #14: 1
Case #15: 4
Is this correct?

My code:http://phpfi.com/211399

Sorry for my poor English..

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

Post by mf » Sat Mar 03, 2007 5:54 pm

My accepted program produces this output:

Code: Select all

Case #1: 16
Case #2: 7
Case #3: 3
Case #4: 17
Case #5: 7
Case #6: 9
Case #7: 3
Case #8: 12
Case #9: 7
Case #10: 7
Case #11: 5
Case #12: 5
Case #13: 5
Case #14: 1
Case #15: 4

s000015
New poster
Posts: 5
Joined: Sat Oct 08, 2005 1:56 pm
Location: Taiwan

Post by s000015 » Tue Mar 06, 2007 4:49 am

Thank you :)

I got ac.

Here is some more test cases:

Code: Select all

4
0
0
1
0
3
0
3
2
1 2 999
2 1 999

Code: Select all

Case #1: 0
Case #2: 0
Case #3: Possums!
Case #4: Possums!

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

Post by SRX » Sun Mar 11, 2007 5:15 pm

sorry , I have passed the all test cases above ,
can someone give me some test cases ?

thanks :oops:
studying @ ntu csie

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon May 14, 2007 10:19 pm

Now that I finally solved this problem, after reading everything that is publicly accessible (not a lot, both quantitative and qualitative), I would really like to read Fulkerson's article. Sure, I don't want to pay 32 bucks, and I also don't want to invite anyone to doing something illegal. But if anyone who accidentally knows my email address would accidentally attach it to an email and accidentally drop that mail into my inbox, that wouldn't be considered theft, would it?

BTW. Does the fact that Springer owns the rights to this article automatically mean that they got the intellectual rights to the algorithm described in it? So if I would make a description of the algorithm and put it on my web site, would I then be prosecutable? And if I use it to solve this problem? And if I incorporate it in a software product that I exploit commercially?

RoBa
New poster
Posts: 8
Joined: Thu Aug 11, 2005 7:57 pm

Post by RoBa » Thu Aug 16, 2007 10:26 am

I wonder the time complexity of the ACed algorithm. I got TLE with an O(V^3) implementation, and finally AC with an ugly O(VE).

And I agree with fh: If we are asked which edges from the original graph belong to the directed MST, it will be much harder. Could someone please show me an implementation about it? I can't understand why Union-Find will work...
Let it be

Post Reply

Return to “Volume 111 (11100-11199)”