Convention Misunderstanding Problem Statement

#1

I am not following the problem statement of the USACO Silver problem Convention. We have M buses that can house a maximum of C cows, and we must find the min of a cow’s largest waiting time.

Sorting cows by time, once cow 1 gets bus i, it’s always optimal to place cow 2 in the same bus. If it’s in a different bus j, we’ll have to wait until another cow 3 comes to fulfill the size of bus i. Then the waiting time of cow 1 will be greater. The waiting time of cow 2 will also be greater since we’ll have to wait for yet another cow 4 to fulfill the size of bus j. Had we instead put cow 2 in bus i, cow 1 would have a smaller waiting time, and cow 2’s waiting time wouldn’t even matter since it’s less than cow 1’s wait anyway.

Greedily, from what I’m understanding of the problem, we need to continue placing cows in the same bus until C cows arrive, in which case we send the bus away. However, the way I am interpreting the problem is clearly incorrect. Can you please clarify?

#2

You can think about it like so-
All the buses are already there, and its the cows that arrive at different times. We can assign certain cows to certain buses, and certain buses to certain departure times. The amount of time a cow waits for is the difference between its arrival time and the bus’s departure time.

And I don’t think a greedy method would work. Have you tried binary searching?

#3

Thank you. Binary searching is very useful here. It turns out my above greedy approach works if we are given the maximum waiting time any cow can have. We can use that simulation idea to check if a maximum waiting time works, and we can get the answer through binary search.

1 Like