## 10249 - The Grand Dinner

Moderator: Board moderators

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

### 10249 - The Grand Dinner

I used the Edmonds-Karp algorithm implementing the Ford-Fulkerson 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 Ford-Fulkerson? Please who got Accepted - post what implementation of Ford-Fulkerson you used.

Thanks

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
same as mine. i use max-flow, and always get TLE. later one of my friend told me not to use max-flow, but such a kind of greedy. anyway i havent tried it.

-titid gede-
Kalo mau kaya, buat apa sekolah?

Whinii F.
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 preflow-push, which is O(V*V*E). It sufficed to finish the problem in about 3 sec..
Moreover, the implementation of preflow-push is shorter and maybe easier than that of Edmonds-Karp, so I suggest you should look it up. CLR covers it.

Good luck!
JongMan @ Yonsei

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm
Thanks. I hope I'll have time to try it.

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am

### Greedy works

The greedy algorithm works for this problem.

Got accepted in less than 0.4 seconds.

zhenh
New poster
Posts: 10
Joined: Mon Oct 18, 2004 3:52 pm

### 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... )

alu_mathics
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"
cuii e

pablo
New poster
Posts: 4
Joined: Tue Nov 09, 2004 2:37 am

### preflow-push TLE

I've implemented preflow-push 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 edmond-karp and got TLE and when reading in the board found out that preflow-push 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 preflow-push implementation (lift-to-front, 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 max-flow 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!

Gigi's Baby
New poster
Posts: 19
Joined: Thu May 02, 2002 5:47 am
Location: Zhongshan (Sun Yat-sen) University
I used preflow-push algorithm and got AC in 2.2s

murkho
New poster
Posts: 33
Joined: Mon Mar 28, 2005 6:41 pm

### 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?

decowboy
New poster
Posts: 1
Joined: Thu Jul 24, 2008 11:41 pm

### 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

Grazyna
New poster
Posts: 16
Joined: Wed Apr 20, 2005 2:44 pm
Location: Thessaloniki,Greece

### 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

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

### 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.

brianfry713
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!

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

### 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.