## 10249 - The Grand Dinner

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10249 - The Grand Dinner

Input:

Code: Select all

``````1 2
1
1 1
1 1
2
2
0 0``````
Check input and AC output for thousands of problems on uDebug!

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

### Re: 10249 - The Grand Dinner

Many many thanks sir I could not have found that bug alone, at least not soon
Do or do not. There is no try.

forthright48
New poster
Posts: 37
Joined: Wed Mar 14, 2012 11:57 am
Contact:

### Re: 10249 - The Grand Dinner

I searched on google for solutions for this problem. I found greedy solutions all over the place. They all used the following algorithm:
1.sort the team based on number of members in decreasing order
2.then assign team members of a team to each table considering the capacity limit of each table. and do same for the next team....
3.if a member of one team can't be assigned to any table due to table capacity try for the next.
4.repeat this process...until all team members are assigned.
now,
if all person can be placed then print the configuration,
else output "0"
So I tested them with the following test case:

Code: Select all

``````4 5
5 4 3 3
3 3 3 4 5
0 0
``````
Their greedy solutions failed. It gave 0. But an arrangement exist for this case.

Code: Select all

``````1
1 2 3 4 5
2 3 4 5
1 2 3
1 4 5
``````
Is there any reference about Greedy Solution for Complete Bipartite Graph? Since the above algorithm failed, what is the real greedy solution that can actually solve this problem? I tried a greedy method using Priority queues, but got TLE.
What ever happens, happens for good. Even when we get WA :p
http://www.forthright48.com

forthright48
New poster
Posts: 37
Joined: Wed Mar 14, 2012 11:57 am
Contact:

### Re: 10249 - The Grand Dinner

Okey never mind. I got AC. Using Priority Queue gave me TLE, but sorting it every time gave AC.
What ever happens, happens for good. Even when we get WA :p
http://www.forthright48.com

dibery
Learning poster
Posts: 76
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei
Contact:

### Re: 10249 - The Grand Dinner

A test case. Hope it may help someone.

Input:
3 2
3 1 1
5 5

Output:
0
Life shouldn't be null.