This week in competitive programming

This week had two usual suspects: a TopCoder round and a Codeforces round. TopCoder SRM 612 (problems, results, top 5 on the left) featured a somewhat unexpected 450-pointer: you were given a set of cells on the infinite grid, and were asked to find another set of cells that has the same number of cells in each row and in each column as the original set, but has the smallest possible intersection with the original set. I'm calling it unexpected because the only solution I'm aware of involves min-cost-max-flow, and that seems pretty tough for 450 points. Is some simple approach possible here?

Codeforces Round 236 (problems, results, top 5 on the left) had the following problem as the hardest: you are given two trees, blue and red, with the same set of vertices. Then, we remove one edge from the blue tree, separating all vertices into two parts. There are some red edges connecting the parts - we remove all of them on the second step, separating the red tree into several parts. Now, there are some blue edges connecting the separate red parts - we remove all of them on the third step, and so on. You need to output which edges will be removed on each step, given the two trees and the first blue edge to remove. Trees have up to 200000 vertices.

The author's solution and both accepted solutions involve interval trees and require O(NlogN) memory. So here's my challenge: can you come up with a solution that doesn't use any complicated data structures and uses O(N) memory?

Thanks for reading, and see you next week!