Note that this weekend (Friday 7.3. to Monday 10.3. inclusive, ± time zone), this year's last round of USACO (before US Open) takes place.
You'll be able to access the contest from the USACO page. Registration is required.
Feel free to discuss the problems here after the contest ends
(which is, btw, not very clear, because there are no official start/end times posted — around Tuesday afternoon in UTC). I'll probably also post my solutions here.
Also notice how similar this is to my blog post about COCI :D. This is one of the usual Crazy Weekends — there's COCI, USACO and start of the Codechef Long Challenge. It's like the contest organizers do this on purpose...
UPD: The results are up now!
UPD: Negative votes... trolls growing strong here!
UPD^2: Trolls are gone now. Lol.
The Lazy Cow (code)
We're given N points (xi, yi) in a plane, each with a weight gi and are supposed to find a point (x, y) which maximizes the sum of gi of points located at a distance of at most K from (x, y). The distances are Manhattan ones — the distance of point (xi, yi) from our (x, y) is |xi - x| + |yi - y|. Constraints: N ≤ 105, coordinates 0 ≤ xi, yi ≤ 106, 1 ≤ K ≤ 2·106.
Let's say that we picked a point (x, y). We can transform coordinates (x, y) to (x', y') = (x + y, x - y) and similarly for all points i. In these new coordinates, the distance of our point from any given one is (evaluating all possibilities for what the abs. values can look like) , and the region for which it's ≤ K is a rectangle around (x', y').
Let's sort the given points by x'-coordinate. Now, we can use a sweepline + interval tree, which supports operations "add value v to all elements of interval I" and "get maximum of all elements". We'll try adding the points one by one, in the order of increasing x'-coordinate, and in the interval tree, we'll remember the sum of gi of points that we could get by picking y' as the other coordinate in the element y'. That's done by adding gi to all elements from yi' - K to yi' + K inclusive; removing a point is the same, just with subtracting gi from all those elements.
We need to remove the points whose xi'-coordinates are < x' - 2K (we're basically forcing the right side of our rectangle to touch some point and store in the interval tree only answers when accounting for points that have the xi'-coordinate ≥ x' - 2K; if it didn't, we can move the rectangle to the left without changing the result). Since the points are already sorted, we can use two pointers... well, just one additional "pointer", which points to the leftmost point still in the interval tree.
The time complexity of constructing an interval tree is O(maxX); each query can be processed in time and the sorting takes time, so the resulting complexity is . With y'-coordinate compression, we can get runtime.
We're given an array A of size N ≤ 105, and are asked to compute the minimum arithmetic average of all elements of this array after removing a substring (contiguous subsequence) from it. Plus some additional constraint that the elements of this array are non-negative, at most 104 and we can't remove the first or last element from A.
This type of problems (serarching for some arithmetic average) can usually be solved with bin-search. It's clear that if we can achieve an average of at most x, then we can achieve also at most y > x. So let's fix x and check if we can achieve ≤ x.
Prefix sums are useful. Let S[i] denote the sum of the first i elements (S = 0). Let's say that we erased the subarray A[i..j] (2 ≤ i ≤ j ≤ N - 1) and got an average ≤ x. It means that
Let's say that we fixed j. Now, the best choice (minimizing the left side of this inequality) is obviously picking the smallest S[i - 1] - x(i - 1). This gives us a simple way of checking if this inequality ever holds: iterate over j from 2 to N - 1, remember and update the minimum of all S[i - 1] - x(i - 1) (always just picking the minimum of smallest the one found so far and S[j - 1] - x(j - 1)) and check if the smallest value for given j is ≤ 0. If it never is for given x, there's no way to get an average ≤ x.
This check works in O(N) time; plus binsearch, it's time.
Counting friends (code)
We're given an array of N + 1 elements (N ≤ 500) and are supposed to find, and list in sorted order, all possible elements of this array such that after removing said element, the remaining ones can be degrees of a simple undirected graph.
Why not try to remove each element and check if the remaining ones are degrees of a graph? We have a simple way of checking whether they are: the Erdős–Gallai theorem, which provides a necessary and sufficient condition.
Let's sort the numbers beforehand. Now, we can get a sorted array after removing an element in O(N) time without much difficulty. For each removed element, we can just compute the sums on both sides of the inequality from Erdős–Gallai theorem for all k (possibly with some optimizations), which gives us an O(N3) time complexity.