10249  The Grand Dinner
Moderator: Board moderators
10249  The Grand Dinner
I used the EdmondsKarp algorithm implementing the FordFulkerson method for finding the maximum flow in this problem. But I got TLE. Does this mean that I have to implement more efficient algorithm for max flow since the one I used is V*E*E? Did anybody that got Accepted use this implementation of FordFulkerson? Please who got Accepted  post what implementation of FordFulkerson you used.
Thanks
Thanks

 Experienced poster
 Posts: 187
 Joined: Wed Dec 11, 2002 2:03 pm
 Location: Mount Papandayan, Garut

 Experienced poster
 Posts: 151
 Joined: Wed Aug 21, 2002 12:07 am
 Location: Seoul, Korea
 Contact:
I cannot think of a greedy solution that works.
I used preflowpush, which is O(V*V*E). It sufficed to finish the problem in about 3 sec..
Moreover, the implementation of preflowpush is shorter and maybe easier than that of EdmondsKarp, so I suggest you should look it up. CLR covers it.
Good luck!
I used preflowpush, which is O(V*V*E). It sufficed to finish the problem in about 3 sec..
Moreover, the implementation of preflowpush is shorter and maybe easier than that of EdmondsKarp, so I suggest you should look it up. CLR covers it.
Good luck!
JongMan @ Yonsei
Greedy works
The greedy algorithm works for this problem.
Got accepted in less than 0.4 seconds.
Got accepted in less than 0.4 seconds.
How does a greedy algorithm work ??
To jackie:
How does it work?
The straitforward greedy approach is destined to fail...
( scan from first table to last table, take a seat if the table isn't full yet... )
How does it work?
The straitforward greedy approach is destined to fail...
( scan from first table to last table, take a seat if the table isn't full yet... )

 Learning poster
 Posts: 55
 Joined: Sat Jan 24, 2004 9:30 pm
 Location: Chittagong
 Contact:
here is the greedy one.
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"
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"
cuii e
preflowpush TLE
I've implemented preflowpush and got accepted in a regular flow problem (internet bandwidth, 820) and then i started working on this one because a friend of mine told me he had implemented edmondkarp and got TLE and when reading in the board found out that preflowpush was the answer. I've already got accepted with the greedy option, so i told him to do that, but now i'm trying to test my preflowpush implementation (lifttofront, supposed to be V*V*V found it in "introduction to algorithms") so i'm trying to solve it again with this perspective but i continue to get TLE. I tried sending the code that only reads the input and initializes (its V*V) and it takes more than one second so i'm thinking maybe they added more cases so to ensure that the greedy solution is the only one that works (it's clearly faster than any knid of maxflow algorithm) or that the extensive use of STL containers and streams or something else makes my constant so big that my algorithm run out og time. If someone that got ACC using preflow could submit it again and tell me that he gots TLE i'd be pleased. If he tells me he gots ACC in 3 seconds again, i'll start looking for bugs. Thank You!

 New poster
 Posts: 19
 Joined: Thu May 02, 2002 5:47 am
 Location: Zhongshan (Sun Yatsen) University
10249 Greedy strategy
Is there any proof that this problem can be solved by greedy strategy?
I got AC. But one thing I don't know why it works. What's the reason behind it?
One more extra thing:
In first attemp I sorted both the Team and Table. But I got WA. I don't know why? Because if in the input set the Tables are sorted then what would happen?
I got AC. But one thing I don't know why it works. What's the reason behind it?
One more extra thing:
In first attemp I sorted both the Team and Table. But I got WA. I don't know why? Because if in the input set the Tables are sorted then what would happen?
Re: 10249  The Grand Dinner
I've tried the greedy approach, but I can't get it and working, nor can I proof why it should work.
Haven't tried preflow push, and if there is a greedy solution, that would be way better
Haven't tried preflow push, and if there is a greedy solution, that would be way better
Re: 10249  The Grand Dinner
I am trying to solve it with the greedy approach, that it was described before,
but till now I have a lot of WA.
I used both ways for the tables, unsorted and sorted according to the capacity.
Is there any special case I have to consider?
The boundary conditions are correct?
Should the arrangement be printed in a specific order?
(the problem statement is, that just the ith line should have the arrangement of the ith team)
thanks in advance for any help
but till now I have a lot of WA.
I used both ways for the tables, unsorted and sorted according to the capacity.
Is there any special case I have to consider?
The boundary conditions are correct?
Should the arrangement be printed in a specific order?
(the problem statement is, that just the ith line should have the arrangement of the ith team)
thanks in advance for any help
Re: 10249  The Grand Dinner
Someone can help me please with my code? Here, I used a greedy algorithm. At first, I sorted the number of team members in descending order. Then spread each member of a team(from the sorted ordering of the teams) to different tables as long as it is possible. If the spreading terminates successfully, then the function returns 1, else 0. Please help someone.
Code: Select all
AC
Last edited by Scarecrow on Tue Jul 31, 2012 1:12 am, edited 1 time in total.
Do or do not. There is no try.

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 10249  The Grand Dinner
Try input:
Code: Select all
3 3
2 2 2
2 2 2
0 0
Check input and AC output for thousands of problems on uDebug!
Re: 10249  The Grand Dinner
AC
Code: Select all
AC
Last edited by Scarecrow on Tue Jul 31, 2012 1:12 am, edited 1 time in total.
Do or do not. There is no try.