C: Museum Guards
This was the hardest problem in the set. No team solved it, although several came close. Here’s one bit of trickyness that bit some teams – the problem states:
These time intervals may overlap. The union of all time intervals provides the complete set of times at which the guard is available.
If a guard says they’re available from 2:05 to 3:15, and also from 3:10 to 4:20, then they are available for the 3:00 to 3:30 time interval. Some teams did not perform this union correctly.
Here’s the Judge Input, the Judge Output, the main Solving Program, another solution, and another.
[spoiler]
We’ll frame this as a Max Flow problem, but with a twist. We’ll start with a brief discussion of Max Flow problems.
Consider a directional, weighted graph that has a special node called the ‘Source’, and another called the ‘Sink’. Consider the weights to be a ‘capacity’. Think of each edge like a one-way pipe, and the ‘capacity’ is the most stuff you can push through that pipe. (The internet is a series of tubes, right?) Well, the question is… How much stuff can you push from the Source to the Sink, given the limited capacities of all the edges?
The solution technique for a Max Flow problem is called Ford-Fulkerson, and I’ll only give a brief outline of it here.
First, for every edge A⇒B, create a dual edge, B⇒A, which starts with 0 capacity. The way to think of A⇒B and its capacity is: How much capacity is available to use. The way to think of B⇒A and its capacity is: How much capacity has been used, that I could give back if I had to. That’s why B⇒A starts out as 0 – because, at the beginning of the algorithm, you haven’t done anything, so you haven’t used any capacity.
Now, find a path from the Source to the Sink, only traversing edges that have some capacity (that is, capacity>0), and don’t hit any node more than once. You can find this path any way you like, but Breadth-First Search has become the standard.
When you’ve got a path, go back over the edges on the path, and find the one with the smallest capacity. That’s the most stuff you can push through that path, right? That’s the weakest link. Then, go back over the path again, and move that amount of capacity from each edge to its dual (that is, subtract it from each edge, add it to each edge’s dual).
Keep doing this (finding paths, finding the min capacity, moving that capacity from each edge to its dual) until you can’t find a path with >0 capacity. Then, you’re done! The total amount of capacity that you moved over all the paths you found is the Max Flow!
OK, so how do we see Museum Guards as a Max Flow problem? Well, the ‘stuff’ we’ll flow through the system is guard-periods. Build two kinds of nodes, for guards, and for time periods. Link the Source to each guard, with the capacity being the number of time periods that guard is able to work. Link a guard to a time period if the guard is willing to work that time period, with capacity 1. Finally, link the time periods to the sink. What should the capacity for those edges be? Well, that’s tough. We could set them all to n, and see how many guard-periods flow through – but we have no way of forcing the guard-periods to be balanced over the time periods. Some periods could be over-represented, and some under-represented. The result wouldn’t be meaningful. Hmmm….
Consider this: If we set the capacity of each of those links to some value x, 0≤x≤n, and we get a total flow of x*48 (48=number of 30 minute periods in a day), then we know we can cover all time periods with x guards. The only way to geta total flow of x*48 is to get a full x from each of the 48 time periods. We can’t get any more from one time period (and less from another), because we’ve set the max capacity from each time period to the sink to x. That’s our hook. We just have to do repeated Ford-Fulkersons to find the largest value of x which leads to success.
[/spoiler]