10249 - The Grand Dinner

[brianfry713]

Input:

Code: Select all

1 2
1
1 1
1 1
2
2
0 0

[Scarecrow]

Many many thanks sir I could not have found that bug alone, at least not soon

[forthright48]

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.

[forthright48]

Okey never mind. I got AC. Using Priority Queue gave me TLE, but sorting it every time gave AC.

[dibery]

A test case. Hope it may help someone.

Input:
3 2
3 1 1
5 5

Output:
0