Lets have DSU where for each set we also remember number of cells in it and number of start sites in it. Then we just join pairs of adjacent cells in order of difference between their values. Each time we join some set that had less then T cells and resulting set no less then T cells we add current difference multiplied by number of starting sites to answer

Problem 1: code

We can see that the captured stones are exactly those in the convex hull of the opponent's stones: the stones outside the hull are obviously outside of any triangle, and we can triangulate the opponent's hull into triangles (even disjoint, if we wanted) formed by its vertices.

It's a classic problem of constructing a convex hull and couting points in a convex polygon. Just sort the points of each set by (x-coordinate, in case of equality y-coordinate), and maintain the convex hull of points below the line between the first and last point (with this sorting; inclusive), and the concave hull of points above it; the union of those 2 polylines gives the whole convex hull.

For counting points of the other set in the hull: we have them sorted identically, so we can move a sweepline by increasing x; from a property of convex polygons, we know that if a given point P lies inside the polygon, there's exactly 1 side of the bottom polyline and exactly 1 side of the top polyline which have x-coordinates of its vertices x₁, x₂ such that (except P_x equal to the maximum x-coordinate of the points of the hull, which can be checked easily). As x increases, the indices of those 2 lines don't decrease, so we can use 2 pointers for identifying them. Checking the "above" and "below" (not strictly) can be done simply using vector cross products.

Complexity: , due to sorting. My code uses closed intervals [x₁, x₂] and doesn't worry about errors by 1 :D

Problem 2: code

Let's fix B. Consider this simple bruteforce: we traverse the field and if there's a square BxB with all characters equal, let's mark all the cells of that square as "can contain anything". That's because if we ignore the condition for the resulting snow types in that square, and are able to satisfy them for the rest of the field, we can surely satisfy all of them together, by stamping the selected square BxB last. We repeat the process, where all cells with "whatever" type are considered as both "S" and "R", always stamping squares of all "S" or all "R" (with at least one cell not "whatever"), and if we can stamp the whole field this way, we win.

The generalization to any B is simple: we start with maximum B, repeat the said algorithm, and if we can't stamp anything and a cell is left unstamped, we'll just decrease B (up to B = 1, when it always works).

This is too slow, so let's try for at least O(N²M²); the first obvious improvement is in prefix sums (using which we can count "whatever"s, "R"s and "S"s in any rectangle), which make checking whether to mark the cells of a square as "whatever" simpler. We'll need to update them when marking a cell as "whatever" (so also as either "R" or "S"), but that's simple: for cell (i, j), we just need to increment the prefix sums at cells (k ≥ i, l ≥ j). If we could ensure that this happens for any cell just once, the total time for prefix sum updates is amortized O(N²M²) (O(NM) per cell).

Next, we can store the set S of top left corners of squares which weren't marked with "whatever"s yet; since B is non-increasing, we see that we can ignore the squares with top left corners not in S. That's one more optimization; the set<> operations only take additional operations.

We can now try all squares BxB witn top left corners in S; if none of them are marked "whatever", we can decrease B and repeat; that's done at most O(min(N, M)) times and only takes O(NM) time per pass. If we mark a square with "whatever"s, we can check all its cells and mark all those which haven't been marked yet. We process each top left corner at most once and the square has at most O(NM) cells; the updates of prefix sums have been counted separately, so this takes O(N²M²) time at most.

Now, this complexity is crazy, so I'll pose a mini challenge: find a test case where my code is really slow! :D

Problem 3: code

Consider a graph whose vertices are cells of the grid and there's an edge of cost |d_i - d_j| between cells i, j.

We can sort the edges and use a union-find data structure to store components. Let's add the edges by non-decreasing cost; when adding an edge between 2 different components, we merge the smaller one into the larger one; if the resulting component contains at least T vertices, and at least one of the original ones contains  < T vertices, we set the rating of all vertices in that original component (for both original components, if both satisfy the condition) equal to the cost of the added edge.

We can see that each component has vertices with all ratings set or all not yet set, and so we only set the rating of each vertex once.

In the end, we sum up the results for the vertices for which it's required. Complexity: .

Well, Egor ninja'd me :D

see above

I don't remember what were the two first problems (I think my solutions were good), but for the third, I submitted a greedy algorithm:
I sorted the differents intervals by increasing end, and, for each interval, if one or more recorders can recorder it, I choose the one who finished to record his last program lastly.
Is there a reason why this algorithm can't work?
Edit: it was a correct greedy: http://pastebin.com/VvCaYRAE

Same here :)

I don't think USACO bothers with test cases too much, seeing as there so few of them. My solution on Curling got WA 2 times, so it should've gotten WA much more often, too — yet it didn't. Your approach is a reasonable approximation, so it's no wonder that it works often — large random cases, for example, give the results 2 or 3 almost always.

I assumed that the authors didn't assume it, and accounted for it when thinking. Even so, I failed because I forgot to code the special case of points on a vertical line...

Yes, triangle usually means exactly a triangle. But USACO usually doesn't follow logic. You can write to the organizers if you want.