Page 1 of 1

11613 - Acme Corporation

Posted: Mon May 18, 2009 7:31 pm
by greve
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.

Re: 11613 - Acme Corporation

Posted: Tue May 19, 2009 7:20 pm
by greve
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.

Re: 11613 - Acme Corporation

Posted: Wed May 20, 2009 2:10 am
by baodog
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.

Re: 11613 - Acme Corporation

Posted: Wed May 20, 2009 8:38 am
by greve
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.

Re: 11613 - Acme Corporation

Posted: Wed May 20, 2009 11:29 am
by baodog
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.

Re: 11613 - Acme Corporation

Posted: Fri Oct 02, 2009 9:26 pm
by shiplu_1320
Need some input output.