11613 - Acme Corporation

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

Moderator: Board moderators

Post Reply
greve
New poster
Posts: 27
Joined: Tue May 29, 2007 8:52 pm
Contact:

11613 - Acme Corporation

Post by greve » Mon May 18, 2009 7:31 pm

Can anybody explain to me how the answer for the case in the sample input is 2? I have been looking at the problem for a while now, and it seems to me that it can be solved using max-cost max-flow, but it seems a bit pointless to try if one cannot understand the sample output.
For help with problems, visit http://www.uvatoolkit.com/

greve
New poster
Posts: 27
Joined: Tue May 29, 2007 8:52 pm
Contact:

Re: 11613 - Acme Corporation

Post by greve » Tue May 19, 2009 7:20 pm

I contacted the problem author, and he told me that there was an error in the sample output. It is supposed to be 20 (not 2), but it will probably be corrected soon. Anyway, the problem can be solved using discrete ternary search and max-cost max-flow, but my solution is quite slow, so maybe there is a better solution.
For help with problems, visit http://www.uvatoolkit.com/

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Re: 11613 - Acme Corporation

Post by baodog » Wed May 20, 2009 2:10 am

Hi,

Thanks! You are solving min cost flow using ternary search + min cost max flow .. A primal dual or cycle cancelation solution might be faster.

greve
New poster
Posts: 27
Joined: Tue May 29, 2007 8:52 pm
Contact:

Re: 11613 - Acme Corporation

Post by greve » Wed May 20, 2009 8:38 am

You are right - I am solving min cost flow. I have also been told that it can be done with a single run of min-cost max-flow using the successive shortest path method, so that should speed up my solution significantly.
For help with problems, visit http://www.uvatoolkit.com/

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Re: 11613 - Acme Corporation

Post by baodog » Wed May 20, 2009 11:29 am

Actually, I got ac in 0.5 seconds, using just min cost max flow.
I use a very simple trick to conver min cost flow to min cost max flow :-)
-- just connect source to sink with infinite capacity and 0 cost.
This allows X to be "thrown away" before been produced. Then at max flow it's fine.

shiplu_1320
New poster
Posts: 32
Joined: Sat Dec 29, 2007 9:08 pm
Location: CSEDU , Dhaka
Contact:

Re: 11613 - Acme Corporation

Post by shiplu_1320 » Fri Oct 02, 2009 9:26 pm

Need some input output.
A learner......

Post Reply

Return to “Volume 116 (11600-11699)”