10746  Crime Wave  The Sequel
Moderator: Board moderators

 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.
I think this problem should be solved as min.cost flow.
Although up to now my code from 10594 still gets WA.
Although up to now my code from 10594 still gets WA.
My signature:
 Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.  I HATE testing account.
 Don't send me source code for debug.
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 pushrelabel algorithm to find the min cost flow?
Greets
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 pushrelabel algorithm to find the min cost flow?
Greets

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
I'm not aware of any straightforward (to computer programmers) description of the Hungarian Algorithm, so I'll give a short synopsis.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 pushrelabel algorithm to find the min cost flow?
Greets
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 mincost 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 reducingcost alternating cycle can be found.
To find a reducingcost cycle, consider the used edges to have negative cost, and the unused edges to have positive cost. Then find a negativecost cycle  one whose net cost is negative. Flip every edge in the negativecost cycle and the negative cost will be added to the overall cost of the match.
To find negativecost cycles you can use BellmanFord or Floyd's algorithm, not Dijkstra's algorithm, which chokes on negative weights.
The same basic approach extends to mincost matching; here, you want to find a negativecost cycle with nonzero residual capacity (i.e. capacity minus current flow). If you're a complexity theorist you might care to find the maximum capacity or mostnegative cycle, but in practice any cycle will do.
Thanks for your explanation prof. Cormack
gvcormack wrote:
Adrian Kuegel wrote:
gvcormack wrote:
We are not exactly computer programmers and we don't mind some heavy mathematical book explaining the hungarian method. Your favourite, for exampleI'm not aware of any straightforward (to computer programmers) description of the Hungarian Algorithm, so I'll give a short synopsis.
Adrian Kuegel wrote:
Well, in this problem everything is positive. Instead of using BFS to find an augmenting path in EdmondsKarp's algorithm use Dijkstra's to find the shortest cost augmenting path from the source to the sink in the residual network.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 not everything is positive.BiK wrote: Well, in this problem everything is positive. Instead of using BFS to find an augmenting path in EdmondsKarp's algorithm use Dijkstra's to find the shortest cost augmenting path from the source to the sink in the residual network.
When you flow along the edge(u, v), you have to add the backward edge (v, u), this edge has negative cost.
My signature:
 Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.  I HATE testing account.
 Don't send me source code for debug.
You're welcome.BiK wrote:Thanks for your explanation prof. Cormack
Well, I meant that most descriptions were too "Operations Research" oriented rather than too mathematical. But your question caused me to rethink my statement and there is indeed a decent reference on this and related matching problems:gvcormack wrote:We are not exactly computer programmers and we don't mind some heavy mathematical book explaining the hungarian method. Your favourite, for exampleI'm not aware of any straightforward (to computer programmers) description of the Hungarian Algorithm, so I'll give a short synopsis.
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 (mincost general matching) I would be obliged if they were to send me a copy.
The construction I gave includes negative weights. The edges that are to be removed from the match count as negative.Adrian Kuegel wrote:Well, in this problem everything is positive. Instead of using BFS to find an augmenting path in EdmondsKarp's algorithm use Dijkstra's to find the shortest cost augmenting path from the source to the sink in the residual network.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.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
Be careful with rounding. printf("%.2lf") gives sometimes strange results.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.
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.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:
 Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.  I HATE testing account.
 Don't send me source code for debug.