Problem 3277 : Workshops

[mido]

Any hints how to do this.... I tried to think of possible greedy algs, but each one seemed to have a snag...

Thanks....

[Moha]

We solved it in contest by Graph matching.

[teamacm]

We solved it in contest by Graph matching.

Do you mean weighted bipartite matching?

I've been attempting to implement this using Ford-Fulkerson and a modified Dijkstra (to avoid the problem of negative weighted edges). However, it is too slow: O(v^3) where v=1000.

Could you give details about how you solved it?

[ltdtl]

You can solve it using greedy alg.
it will take O(nlogn+rlogr+ nr).
if you make a good implementation, it will be reduced into O(xlogx), but it is not necessary (i guess).

[teamacm]

Could you please tell me what kind of greedy algorithm would solve it?

[sclo]

Sort the workshop by some order (decreasing size, then increasing time).
Sort the rooms by another order (increasing time, then increasing capacity).

Greedily assign each workshop increasing order to the first available room.

[nbauernf]

I thought I could find a counter-example to your greedy choice, but I can't seem to find it at this moment.

Practicing for the world finals I wrote a greedy solution, and I ended up proving to myself that it cannot possibly be greedy (any choice of picking has a counter example). Maybe I didn't think about this choice... I'll go change my ordering to this and see if it works on my test set.

Nate

[rushel]

edit: can two workshop share the same room at the same time if the room has sufficient capacity