Problem 3277 : Workshops

Do you want to discuss about these problems? Go now!
Users are shared (no need to re-register).

Moderator: Board moderators

Post Reply
mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

Problem 3277 : Workshops

Post by mido » Mon Feb 27, 2006 9:14 pm

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

Thanks....

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Thu Mar 30, 2006 11:57 pm

We solved it in contest by Graph matching.;)

teamacm
New poster
Posts: 2
Joined: Mon Feb 05, 2007 4:07 am

Post by teamacm » Mon Feb 05, 2007 4:34 am

Moha wrote: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
New poster
Posts: 1
Joined: Sun Feb 18, 2007 12:43 am

workshops

Post by ltdtl » Sun Feb 18, 2007 12:47 am

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
New poster
Posts: 2
Joined: Mon Feb 05, 2007 4:07 am

Post by teamacm » Sat Feb 24, 2007 7:33 am

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

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Wed Mar 07, 2007 10:08 am

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
New poster
Posts: 5
Joined: Thu Mar 08, 2007 4:33 am

Post by nbauernf » Thu Mar 08, 2007 4:38 am

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
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Re: Problem 3277 : Workshops

Post by rushel » Tue Apr 01, 2008 7:12 pm

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

Post Reply

Return to “ACM ICPC Archive Board”