10746 - Crime Wave - The Sequel

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

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

Post by alex[LSD] » Sun Oct 17, 2004 2:55 pm

:-?
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

Post by .. » Sun Oct 17, 2004 3:02 pm

I think this problem should be solved as min.cost flow.
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.

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

Post by alex[LSD] » Sun Oct 17, 2004 3:12 pm

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? :evil:
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

Post by .. » Sun Oct 17, 2004 3:23 pm

Right :D
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.

User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 » Sun Oct 17, 2004 3:44 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.

Thanks in advance. :)
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

Post by BiK » Sun Oct 17, 2004 6:01 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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Oct 17, 2004 6:45 pm

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:

Post by gvcormac » Sun Oct 17, 2004 6:46 pm

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

Post by BiK » Sun Oct 17, 2004 8:44 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 :)

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.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Sun Oct 17, 2004 9:07 pm

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:
  • 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.

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac » Sun Oct 17, 2004 11:29 pm

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

Post by Adrian Kuegel » Sun Oct 17, 2004 11:38 pm

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

Post by .. » Mon Oct 18, 2004 4:53 am

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).
Thanks Adrian, get AC.
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.

Tobbi
New poster
Posts: 17
Joined: Sat Jan 25, 2003 3:06 pm
Location: Europe

Post by Tobbi » Thu Oct 21, 2004 12:43 am

...I still keep getting WA. :(

Could someone please post some larger test case?

Thanks!!

User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 » Thu Oct 21, 2004 8:19 pm

Can't believe I missed this problem for this little thing at the contest. :oops:
But its always nice to learn something new.
Thanks Adrian, got AC. :)
Not all of our dreams can be made to come true. But still we live with the hope to turn them into reality someday.

Post Reply

Return to “Volume 107 (10700-10799)”