USACO 2018 Open: Milking Order and Topological Sort
USACO 2018 US Open Contest, Gold Problem 2. Milking Order We need to find the biggest number X such that the first X observations are satisfied. Notice that this is perfect to do a binary search on: the invariant is that if the first X observations are satisfied, all observations X-1 will be satisfied; if the first X are insatisfied, all observations X+1 will not be satisfied. So how do we check if all observations to X are satisfied? Let us assemble a graph, in which each observation O_1, O_2, O_3, ... O_i, ... O_l(o) is represented as an edge between O_i and O_i+1 for all i. These observations are satisfiable if and only if this graph has a topological sorting. Lexicographic topological sorting on a graph can be done in O(E + V log_2 V) time (log_2 V because of priority_queue to extract lowest element). So, our total time complexity will be O((E + NlogN) logM). Here, E=200K (the sum of the M_i), N=100K, and M=50K, so it's fast enough. LTS can be easily implemented with ...