Problem 1 — Guard Mark:
The "2 ≤ N ≤ 20" constraint immediately suggests a DP + Bitmask solution. Let DP[m] be the maximum safety factor we can achieve with mask m. The transition will be as follows: DP[m + 2b] = min(Str[b], DP[m] - W[b]), where Str[b] and W[b] are the strength and weight of cow b, respectively, and b is a bit that's off in the current mask m. Initially, DP[0] = INF and DP[i] = - INF for all i in the range [1, 2N - 1]. Our answer will be the maximum among all DP[m] such that the sum of heights of all the cows included in mask m is ≥ H.
Problem 2 — Marathon:
Let D[i] be the distance to go from checkpoint i - 1 to checkpoint i, and S[i] be the distance we save by skipping checkpoint i (that is, go from checkpoint i - 1 to checkpoint i + 1, skipping i). Naturally, D[1] will be zero, as well as S[1] and S[N].
Let querydist(l, r) be the sum of all D[i] in the range [l, r], and querysave(l, r) be the maximum among all S[i] in the range [l, r], then to answer a "Q L R" query, we would do querydist(l + 1, r) - querysave(l + 1, r - 1). We can manage these queries with a segment tree with two satellite data in each node.
Finally, when we receive an update query to checkpoint i, we would need to properly update data for checkpoints i - 1 through i + 1.
Problem 3 — Cow Jog:
The first thing we must think about is "When do two cows cross each other if they are on the same lane?". They will cross when one cow's starting point is behind the other cow's, but its finishing point is farther than the other cow's. That is, if we represent the cows' covered points with a segment, one cow's segment will be completely contained within the other cow's segment.
Now, how do we know exactly how many lanes we will need? Well, let L[i] be the lane that cow i runs in. Initially, we set all L[i] to 0 and then we process all cows by starting point in the following way: Suppose we're currently processing cow c and the current cow's segment is completely contained within some other cows' segments. Among all those other cows, let m be the maximum of all L[i]. Then L[c] = m + 1. If the current cow's segment is not contained in any other segment, then m will be zero.
Another thing we must deal with is how to calculate those values efficiently. We can do it with a BIT or a Segment Tree after compressing the finishing points of all cows (BIT is probably the easiest way). Since the cows will be processed by starting point, when we process cow c, we know that all segments we've encountered so far, will have a starting point lower than the current cow's segment, so all we need to worry about is their ending points and the lanes they are assigned. We can have a Range Maximum Query using a BIT that stores the maximum lane number for each segment ending point. Let query(x) be the maximum lane number for all segments which have an ending point equal or higher than x, and update(x, l) be the update routine to set ending point x to lane l in the BIT. Then to process a certain cow c, all we must do is update(r, query(r) + 1).
Finally, our answer will be query(1).