It would seriously hurt participation numbers. Most top contenders don't cheat because they have respect for competitive programming. The main goals of USACO are to increase interest in informatics and eventually select the IOI team, both of which the current system does pretty well on despite flaws.

If you have good way to prevent the (probably minimal) cheating without hindering those goals, it would be great, but your current suggestions hurt maximizing participation and awareness.

How can you do this?

Historically, I've aced all problems not written by Benq in-contest. But I also get like 0 cases on his, so I can never pass silver. Hopefully cutoff will be 700 for silver this time again.

P1: If Farmer John only adds haybales, we can solve the problem by maintaining a segtree/BBST of unused time intervals, using binary-search-on-segtree to find how long the new haybale lasts. Then, we can use a standard trick where we divide-and-conquer on updates/queries in order make the updates incremental-only.

Think of each haybale update as an interval of queries which it affects before it's overwritten. We can essentially form a segtree over the queries, and each update applies to $$$O(\log(U))$$$ nodes of this segtree. Then, we'll dfs through this segtree, when we reach a node, we apply all updates which cover that node, and then recurse into its children; when we're ready to leave the node, roll back all updates. This takes $$$O(U \log^2(U))$$$ time.

P3: My solution is pretty funny. Note that, as K increases, we should take a superset of the previous vertices, since adding more vertices only decreases marginal costs of adding more. Also, we can solve the problem for a single value of K using a simple tree-dp of whether we use each vertex or not.

Now, let's run the DP solve the problem for each value of K from 1 to N, using a few optimizations. First, before running anything, let's prune the tree of useless leaves (which don't have any special nodes) and then compress long paths of non-special vertices. Next, when we solve a future value of K, only do the tree-dp starting from unused edges/vertices; we can do this by maintaining a list of unused edges and shrinking it as we use them.

Now, because we compressed the tree, the number of unused compressed edges is at most twice the current number of components. Furthermore, after running for K iterations, the current number of components is at most N/K + 1, since otherwise we could just take all vertices. Thus, if we run the tree-dp only on the unused portions of the compressed tree, our total runtime is at most $$$N/1 + N/2 + ... = O(N \log(N))$$$

EDIT: Actually, the runtime of this algorithm is $$$O(N)$$$. Note that, after solving a particular value of $$$K$$$, the number of connected components is at most $$$ans[K] - ans[K-1]$$$; otherwise, we would have a better solution for $$$K-1$$$. Thus, if we add these all up, the total runtime is at most $$$ans[N] - ans[0] + O(N)$$$. We know that $$$ans[N] \le 2N$$$, so the total runtime is $$$O(N)$$$.

How to check if a number of moonies can satisfy the requirement?