Editorial for Facebook Hacker Cup '15 Round 3 P2 - Lunch Scheduling


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Right off the bat, it's simplest to handle a special case separately: if L > 80\,000\,000, then the answer is simply 0. Going forward, let's assume that this is not the case.

For every meeting M, there are at most two potentially optimal "next" meetings to attend – one for each person. Of all of the meetings that James can attend that start after M starts and start earlier than L milliseconds after M ends, let M_j be the one that ends the latest, if any. We can define M_w similarly for Wilson. If somebody attends meeting M, the only two meetings we need to consider attending next are M_j and M_w. We can naively precompute M_j and M_w for every meeting M in \mathcal O(N^2) time, where N is the total number of meetings (N = J+W).

Let S_j and S_w be the two meetings that are optimal to start with for James and Wilson respectively, if any. That is, the meetings for each of them that end as late as possible, but start earlier than time L. If neither S_j nor S_w are defined (no meetings start earlier than time L), then it's impossible to avoid having lunch.

Otherwise the answer we're looking for is then the minimum of these (unless both are \infty, in which case lunch also cannot be avoided):

  • \min_{0 \le i \le J} \max(f(S_j, i), i), if S_j is defined
  • \min_{0 \le i \le J} \max(f(S_w, i), i), if S_w is defined

We can define f(M, K) recursively as follows:

  • f(M, K) = \infty if M is undefined (that is, if we refer to M_j or M_w but such a meeting doesn't exist)
  • f(M, 0) = 1 if M ends after 80\,000\,000-L (no more meetings after M are needed to avoid lunch), and M is one of Wilson's meetings
  • f(M, 1) = 0 if M ends after 80\,000\,000-L, and M is one of James's meetings
  • f(M, K) = \infty if M ends after 80\,000\,000-L, and neither of the above 2 cases holds
  • f(M, 0) = f(M_w, 0) + 1 (we've run out of James's meetings, so Wilson must attend a meeting)
  • f(M, K) = \min(f(M_j, K-1), f(M_w, K) + 1) if K > 0 (either person can take the next meeting)

There are only \mathcal O(N^2) states to compute, and each one can be computed in \mathcal O(1) time. So the total time complexity of this solution is \mathcal O(N^2).


Comments

There are no comments at the moment.