10249 - The Grand Dinner

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

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

Post by brianfry713 » Tue Jul 31, 2012 12:02 am

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

Post by Scarecrow » Tue Jul 31, 2012 1:11 am

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
Location: Bangladesh
Contact:

Re: 10249 - The Grand Dinner

Post by forthright48 » Thu Jun 13, 2013 11:57 pm

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
Location: Bangladesh
Contact:

Re: 10249 - The Grand Dinner

Post by forthright48 » Fri Jun 14, 2013 12:16 am

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

Post by dibery » Fri Jan 02, 2015 11:11 am

A test case. Hope it may help someone.

Input:
3 2
3 1 1
5 5

Output:
0
Life shouldn't be null.

Post Reply

Return to “Volume 102 (10200-10299)”