10746 - Crime Wave - The Sequel

[alex[LSD]]

Help me people! Its the dumb russian again.
I used DP for this problem.
I stored situations in structures like this:
nBank : integer; // Current bank that we re trying to save
PartolsMask : a bit vector of length M, indicating which police patrols went to the banks

At first I had one situation
nBank = 1
PatrolsMask = 00...0 // THis means that all patrols are free

From a position we can produce a new one
nBank + 1
.......1... // one zero has to be replaced by a "1"
the cost of prodution is the distance from patrol indicated by this "1" and bank number nBank.

So in my problem I start with one bit sequence, consisting of only zeros. After N steps I obtain all bit sequences with exactly N "one"s, and minimum weights counted. For every bit pattern I check every bit if it is zero. And if it is then I try to produce a new situation replacing it with a "1", and adding the weight. Every bit pattern is checked only once.

My complexity should therefore be around 20*2^20, which is close to 20 million operations. I just couldn't come up with nothing better.
Can you help me with finding a better algo? Or should I just rewrite it in C?

[..]

I think this problem should be solved as min.cost flow.
Although up to now my code from 10594 still gets WA.

[alex[LSD]]

Well I never really gave this idea a deep thought, but if we add M-N banks such that everyone gets to them in no time than we can use Hungarian Method here. And it runs under N^4... Ain't I right?

[..]

Right

[Dreamer#1]

I also tried to solve this problem with min cost flow during contest but kept getting WA. Can someone who got AC give us some test cases.

Thanks in advance.

[BiK]

Could somebody give references for the hungarian method?

For the min cost flow I assume that it is such flow that the total cost along the paths on which it flows is minimum. Ford Fulkerson can be modified to use Dijkstra when we look for an augmenting path. Is that correct? But I wonder if there is a more effective way to compute the min cost flow. For example, is it possible to modify the push-relabel algorithm to find the min cost flow?

Greets

[Adrian Kuegel]

Ford Fulkerson can be modified to use Dijkstra when we look for an augmenting path. Is that correct?

No, since Dijkstra can't handle negative edge costs. You can use Bellman Ford for augmenting path; this should work if there are no negative cycles.

[gvcormac]

Could somebody give references for the hungarian method?

For the min cost flow I assume that it is such flow that the total cost along the paths on which it flows is minimum. Ford Fulkerson can be modified to use Dijkstra when we look for an augmenting path. Is that correct? But I wonder if there is a more effective way to compute the min cost flow. For example, is it possible to modify the push-relabel algorithm to find the min cost flow?

Greets

I'm not aware of any straightforward (to computer programmers) description of the Hungarian Algorithm, so I'll give a short synopsis.

Bipartite matching is a special (simpler) case of max flow. You repeatedly find an alternating path that begins and ends with an unused edge; flipping the use/disuse of each edge on the path increases the cardinality of the match by 1. When there are no such paths, the maximum cardinality match has been reached.

The maximum cardinality match may be ambiguous. This is the case if and only if there is an alternating cycle - a cycle in which used and unused edges alternate. Clearly you can flip the edges in such a cycle without affecting the cardinality.

The trick with min-cost bipartite match is to find cycles such that flipping them can be done so as to reduce the cost of matching, and to continue until no such reducing-cost alternating cycle can be found.

To find a reducing-cost cycle, consider the used edges to have negative cost, and the unused edges to have positive cost. Then find a negative-cost cycle - one whose net cost is negative. Flip every edge in the negative-cost cycle and the negative cost will be added to the overall cost of the match.

To find negative-cost cycles you can use Bellman-Ford or Floyd's algorithm, not Dijkstra's algorithm, which chokes on negative weights.

The same basic approach extends to min-cost matching; here, you want to find a negative-cost cycle with non-zero residual capacity (i.e. capacity minus current flow). If you're a complexity theorist you might care to find the maximum capacity or most-negative cycle, but in practice any cycle will do.

[BiK]

Thanks for your explanation prof. Cormack

gvcormack wrote:

I'm not aware of any straightforward (to computer programmers) description of the Hungarian Algorithm, so I'll give a short synopsis.

We are not exactly computer programmers and we don't mind some heavy mathematical book explaining the hungarian method. Your favourite, for example

Adrian Kuegel wrote:

No, since Dijkstra can't handle negative edge costs. You can use Bellman Ford for augmenting path; this should work if there are no negative cycles.

Well, in this problem everything is positive. Instead of using BFS to find an augmenting path in Edmonds-Karp's algorithm use Dijkstra's to find the shortest cost augmenting path from the source to the sink in the residual network.

[..]

Well, in this problem everything is positive. Instead of using BFS to find an augmenting path in Edmonds-Karp's algorithm use Dijkstra's to find the shortest cost augmenting path from the source to the sink in the residual network.

Well, in this problem not everything is positive.
When you flow along the edge(u, v), you have to add the backward edge (v, u), this edge has negative cost.

[gvcormac]

Thanks for your explanation prof. Cormack

You're welcome.

gvcormack wrote:

I'm not aware of any straightforward (to computer programmers) description of the Hungarian Algorithm, so I'll give a short synopsis.

We are not exactly computer programmers and we don't mind some heavy mathematical book explaining the hungarian method. Your favourite, for example

Well, I meant that most descriptions were too "Operations Research" oriented rather than too mathematical. But your question caused me to re-think my statement and there is indeed a decent reference on this and related matching problems:

Galil, Zvi, Efficient Algorithms for Finding Maximum Matching in Graphs. ACM Computing Surveys 18:1 (March 1986).

If anybody comes of with a succinct implementation of the last problem (min-cost general matching) I would be obliged if they were to send me a copy.

Adrian Kuegel wrote:

No, since Dijkstra can't handle negative edge costs. You can use Bellman Ford for augmenting path; this should work if there are no negative cycles.

Well, in this problem everything is positive. Instead of using BFS to find an augmenting path in Edmonds-Karp's algorithm use Dijkstra's to find the shortest cost augmenting path from the source to the sink in the residual network.

The construction I gave includes negative weights. The edges that are to be removed from the match count as negative.

[Adrian Kuegel]

I also tried to solve this problem with min cost flow during contest but kept getting WA. Can someone who got AC give us some test cases.

Be careful with rounding. printf("%.2lf") gives sometimes strange results.

For example, for the test case
1 1
0.015

you should obviously print 0.02.
But printf("%.2lf\n",0.015) would print 0.01 (at least with the gcc the online judge uses).

[..]

Be careful with rounding. printf("%.2lf") gives sometimes strange results.

For example, for the test case
1 1
0.015

you should obviously print 0.02.
But printf("%.2lf\n",0.015) would print 0.01 (at least with the gcc the online judge uses).

Thanks Adrian, get AC.

[Tobbi]

...I still keep getting WA.

Could someone please post some larger test case?

Thanks!!

[Dreamer#1]

Can't believe I missed this problem for this little thing at the contest.
But its always nice to learn something new.
Thanks Adrian, got AC.