Confirmed. "[...] as you start during the larger contest window starting the morning of Jan 19 and ending Jan 22 at 23:59 UTC-12 time" (see contest rules). Adding 4 hours, all contestants are done at 4:00 UTC-12. Now, it's 5:25 UTC-12.

How to solve gold 3?

Compress the edges.

I came up with an O(nlogn) solution during the contest. (I'm not really sure about it though...)

First, let's talk about the obvious O(n²) solution. We just have to run a simple DFS in the tree with every root from 1 to n. Assume that the current root is r, let dep[u] be the depth of node u and mindist[u] be the minimum distance between a leaf in the subtree of u and u. Then we go down from the root and whenever we find a node u such that dep[u] ≥ mindist[u] we stop going down and continue the DFS progress with other nodes. Here for simplicity, let's say that "u is an optimal node for r".

Now, I will demonstrate my idea to optimize the above solution. We will find the result for node 1 first. Keep all optimal nodes for the subtree of u in an array save[u]. Suppose that we are currently located in node v, and its children are u₁, u₂, ... Then the candidates of the optimal nodes for v can be all nodes in save[u1], save[u2], ... and their direct parents. Obviously, we should choose the nodes greedily with the increasing order of the distance to node v. We can use some kind of STL like set to solve this. You may think that this is slow but there is a useful observation: a node can be an optimal node for at most 2 other nodes.

By doing that, we can easily compute the answer for node 1. To compute the answers for 2, 3, ..., n, when we run dfs(u, p) (u is the current node, p is the direct parent of the current node) we should save pair<int,int>(u, p) in a map. If we revisit the state dfs(u, p) we do not go down any further, instead, use the save[] array that we just find before. Since an edge (u, v) can be visited in two directions: (u, v) and (v, u), so this DFS progress should run approximately 2n times, I guess.

This requires a very complicated and tricky implementation. Also, I am not sure whether the solution runs in O(nlogn) because my solution is very slow in practice. If there are any counterarguments, please comment.

My code: https://pastebin.com/J2FmK10Y

I solved it with O((sum of answers) * log N). I think it is O(NlogNsqrt(N)), but I couldn't prove it.

Use dp, with state dp[interval][skipped], the brute force transition will be another k factor, but it turns out that you only need to consider one transition (from the leftmost interval that intersects the current interval).

I have an easy DP (I was to lazy to do the contest but it should work).

If there is an interval that covers another one fully, remove the smaller one and decrease K (obviously there is no point in saving a small interval, if we can save a larger).

After this process sort all intervals that are left by r in increasing order. For every pair i < j these inequalities will hold: l_i < l_j and r_i < r_j.

We start iterating the intervals in increasing order of their r or l. Now consider the following DP:

dp[current interval][number of removed intervals][0/1 flag showing if we have chosen interval i] = answer if we consider all intervals until "current interval" (including it).

We can easily compute dp[i][j][0] - it's simply equal to max(dp[i - 1][j - 1][1], dp[i - 1][j - 1][0]). Now the dp[i][j][1] we will use a small observation: If we chose (not remove) interval x

From this we get that dp[i][j][1] = max(dp[p][j — (i — p)][0], dp[p][j — (i — p)][1]), where p is the leftmost interval with r_p ≥ l_i, because it's enough to consider only two case — we either will get the previous interval or won't.

The complexity will obviously be .

PS: Maybe some minor details like (+1 or -1 in the DP states) are wrong in the explanation as I haven't checked it, but I think one can get the general idea from reading this.

Is it possible to apply wqs on this task to solve K <= 100000 as well? (Something like, let the score for a set S of lifeguards fired be [amount we can cover + X * len(S)], and then binary search on X)?

I'm not sure if this would work, since the cost function here is linear rather than quadratic.

I need this one too

There are 2 realizations: 1. The area being water/fertilized will always be one big region 2. The only possible way for a rectangular region to be both water and fertilized is for one sprinkler to be on the SW corner and the other one on the NE corner.

I used 2 arrays to keep track of the running minimum and maximum of the region. I also kept track of the corner/critical points (only the max) (there are redundant points that take up time to calculate). Instead of cycling through all the points for every point which takes O(N^2), I only cycle through the critical points and skip the irrelevant maxs.

In the end, I had to subtract the region that was calculated twice. My AC code

Here is my O(N) solution. It is similar to xaz3109's solution, but I used prefix sums and some math to speed things up: link

Root the tree at Bessie's start and use DP to compute number of farmers for each subtree. Utilize the distance to nearest leaf and compare with distance from Bessie's start. Does this hint suffice?

I did a greedy solution, maybe over complicated it.

Lets make a DS, that can solve these queries -
1. Activate a node.
2. Find minimum distance to an active node from a given query node.
It can be done with Centroid Tree.

Now, in our problem, lets sort the leafs according to their distance from Bessie. Call them v₀, v₁, ..., v_k - 1. Now pseudo code is something like this —

for i = 0 to k - 1: 
    if(dist(bessie, v[k]) < ds.query(v[k])) 
        ans++; 
	ds.activate(v[k]);

Start reading here. :)

Hi there, I'm the problem-writer behind Gold 1 :)

First of all, I hadn't seen this problem before writing my problem. However, because USACO Silver and Gold use very limited subsets of the material tested in programming contests, it's natural that problems will use similar ideas over time. Indeed, after I wrote the problem (but before the USACO contest), a problem on a CF round reused an extremely similar idea: http://codeforces.net/contest/915/problem/F

The similarity between these two problems is not quite so uncanny, but anyone who had solved both would surely notice that they rely on the same idea.

Moreover, it's worth noting that anyone who has studied the Silver and Gold-level material so thoroughly as to be able to find this type of thing on short notice probably is ready for promotion anyway. Any contestant who had somehow already seen this problem almost certainly did so in the process of solving a far greater number of relevant problems, in which case they'd most likely achieve promotion regardless.

My apologies for the similarity--however, as we've seen here, it is extremely difficult to create ideas that nobody has ever come up with before when we're able to use such a small subset of the contest material. Situations like this should definitely be avoided in Platinum, but for the lower divisions, they're very likely to show up simply because almost all elementary ideas have been discovered already.

Noam527 solved it with combi (not sure if PIE), maybe you can pm him

Sort the queries by threshold and use DSU to update tree. Since number of vertices is required to be reported, store size of each set/component and union-by-size will give you AC.

I've looked and in the past years for January it seems to be 700 or below.

(Personally) I found the gold contest quite lenient on the partial credit, as I was able to get about 70% for #1 and #2 without really understanding the correct solution (probably ~700-720 total). For #3 I did an N^2 dp instead of the correct O(N) and only got the first 9/12, as I imagine many others did as well So I'm worried a relatively high amount of partial credit awarded might make the cutoff 750 or above,

Anyone else have any thoughts on the relative difficulty? This is only second gold contest for me so I'm still new

Make an array len[] which len[i] means how many units of i'th interval will remain from intersections to other intervals if delete i'th inverval. For calculating len[], sort intervals by R and update len[i] like sweep line. Rest is easy.

What are you using to open it? Notepad is what I use and it works perfectly fine on that.

Try using atom, it will open them up all in one place too.

I believe the solution is correct as is, though the number of parentheses is admittedly confusing. We are subtracting s[N] - s[N - 1] from the total number of ways.