SRM 690: GerrymanderEasy

I actually failed system test, because my check is k < N instead of k <= N ! I should not move onto the 3rd question so quickly.

My approach uses a sliding window, which requires my to search all k <= N.

One easier way to code is just to iterate on all i and j >= i, and sum up, and we try upddating max only when (j-i +1) >= K

SRM 686: SegmentsAndPoints

I could not prove my alternative greedy approach, which failed system test, i.e., I got punished by not following proper problem solving approach.

An alternative strategy is to reduce this into a bipartite matching problem, which turns out to be a massive overkill.

Since we are just looking for the existence of an answer, we can just force an order of discovery, if there is ever one, it will be covered by forced order. This forced order insight is what I missed during contest!!!

One natural guess is go from left to right. Now it becomes obvious that to match the leftmost point, we should take the segment ends leftmost and yet covers the point.

Proof #1

claim: If there exists a solution, then our greedy solution can discover at least one of them, i.e., in a feasible solution, if point p can be matched to s, then our algorithm never returns p never matches

proof: if q is matched to s instead of p, then we know q must be to the left of p, due to our forced order of discovery,i.e., s covers both p and q.

Now consider the segment t that would have covered q, by our algorithm, t must end to the right of s, and start to the left of q => i.e., it covers p as well, i.e., our algorithm at least can reutrn p-t matching, if no other is available!

Proof #2

By contradiction, suppose our algorithm returns n matches, and we have a matching p1, p2, …..pn, pn+1, ordered by p, with minimum sum(p) and the minium sum(end of segments)

case 1: consider the first p(i) such that p(i) < our(j), this can happen because the s(i) is being used by some other matching of our algorithm already. Otherwise we hae s(i), p(i) not used by anything and our algo doesn’t return it => clearly contradiciton, if we can prove that for p1…p(i-1), our solution IS same as the optimal solution we suppose. Easily provable by induction!

case 2: p1….pn are same, we just happen to have a p(n+1), proof is similar to case 1