10249 - The Grand Dinner

[BiK]

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]

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-

[Whinii F.]

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!

[BiK]

Thanks. I hope I'll have time to try it.

[jackie]

The greedy algorithm works for this problem.

Got accepted in less than 0.4 seconds.

[zhenh]

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]

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"

[pablo]

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]

I used preflow-push algorithm and got AC in 2.2s

[murkho]

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]

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]

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]

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

[brianfry713]

Try input:

Code: Select all

3 3
2 2 2
2 2 2
0 0

[Scarecrow]

AC

Code: Select all

AC