## 10746 - Crime Wave - The Sequel

Moderator: Board moderators

alex[LSD]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:

### 10746 - Crime Wave - The Sequel

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?
Last edited by alex[LSD] on Sun Oct 17, 2004 3:03 pm, edited 1 time in total.
The more contests are held, the happier I am.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
I think this problem should be solved as min.cost flow.
Although up to now my code from 10594 still gets WA.
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

alex[LSD]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:
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?
The more contests are held, the happier I am.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
Right
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm
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.

Not all of our dreams can be made to come true. But still we live with the hope to turn them into reality someday.

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm
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

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
BiK wrote: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
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm
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

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.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
BiK wrote: 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.
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
BiK wrote: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.
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.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Dreamer#1 wrote: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).

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
Adrian Kuegel wrote: 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).
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Tobbi
New poster
Posts: 17
Joined: Sat Jan 25, 2003 3:06 pm
Location: Europe
...I still keep getting WA.

Could someone please post some larger test case?

Thanks!!

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm
Can't believe I missed this problem for this little thing at the contest.
But its always nice to learn something new.