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

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

Post by Abednego »

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 »

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

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

Post by Abednego »

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 »

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 :(

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

Post by Abednego »

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

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

Post by fh »

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

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

Post by Abednego »

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

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

Post by fh »

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 »

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 »

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 »

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 »

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

thanks :oops:
studying @ ntu csie

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

Post by little joey »

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 »

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