Single Round Match 745 Editorials

The match was held on Dec 27th and was held Fun and Unrated round for trial purposes! Thanks to misof for the brief editorials!

200: return {x,y-1}

300: Look at a maximal chain backwards. You start with a range of length n. Then, n-1 times you either remove the smallest or the largest of the numbers in the range. Thus, answer is 2^(n-1).

500: Watch out for different representations of the empty interval. [3,3), [5,7) is a valid chain. Other than that, just check that the lengths are increasing and that each interval is contained in the previous one.

600: Each element must be either smaller than or bigger than all previous elements. If you find one that isn’t, it’s invalid, otherwise its valid or maximal. It’s only maximal if each element is either min(all previous)-1 or max(all previous)+1, and ends with min=0, max=len-1. A tricky case is that when you see e.g. {3,?,?} you know that it cannot be maximal any more.

800: All chains of order n = chains that end with [0,n) + chains that don’t. The second group has the same size as the first group, minus 1, because you can append [0,n) to any chain from the second group to get a chain from the first group. Size of the second group = 2*chains of order n-1 — chains of order n-2.

1000: Greedy. Keep the number of empty intervals separately, and answer max(# of empty intervals, # of chains of nonempty intervals the greedy below builds). Keep the intervals that don’t have a successor yet in a sorted set, sorted primarily by y. Process all intervals in decreasing x order. Each time you process an interval [x0,y0) put it after the interval with the largest y among the ones available.