ilogin 6:12 am on July 22, 2016  

USACO 1.2 Milking Cows (C++) Solution

Hints

We know that this problem will need a complete search approach. Steven and Felix Halim in their book Competitive Programming give a few tips for complete search:

  • generating v.s. filtering
  • prune infeasible search space early
  • utilize symmetries
  • pre-computation/pre-calculation
  • solve the problem backwards
  • optimizing source code

N \leq 5000, so an approach with two nested loops won’t work. A lot of complete search problems are much easier if we sort them first.

Solution

When does something interesting happen? Imagine drawing all the time intervals on a sheet of paper. The only time anything interesting happens is when there’s a jump between intervals, because that’s when there’s idle time and also when there’s a break in continuity of milking cows. All we need to check is if the next interval is a “real” jump, keeping track of the “current greatest right value” and the left point of the current interval.

Code is at: https://github.com/ilogin/Competitive-Programming/blob/master/USACO/milk2.cpp