Subtask 1

For each squirrel ~i~, we can iterate through all subsets of squirrels that include squirrel ~i~ and ~N~ that could receive the ~i^{th}~ squirrel's acorn. For each subset, we can calculate the minimum cost in linear time using the formula described in the problem statement. We can take the sum of the minimum costs for each squirrel.

Time Complexity: ~\mathcal O(2^N \cdot N)~

Subtask 2

We can see that we can form a tree with ~N~ vertices rooted at vertex ~N~ with a directed edge from vertex ~j_i~ to vertex ~i~ for each vertex ~i~ where ~1 \le i < N~. For each squirrel, we can use dynamic programming on the vertices on the path from vertex ~i~ to vertex ~N~ to compute the minimum cost. Suppose ~\text{path}_j~ is the ~j^{th}~ vertex on the path from vertex ~i~ to vertex ~N~, then ~\text{dp}[\text{path}_j] = \min\{ \text{dp}[\text{path}_k] + (x_{\text{path}_j} - x_{\text{path}_k})^2 + (y_{\text{path}_j} - y_{\text{path}_k})^2 + c_{\text{path}_j} \mid 0 \le k < j \}~, with ~\text{dp}[\text{path}_1] = 0~. If there are ~M~ vertices on the path from vertex ~i~ to vertex ~N~, then the answer for squirrel ~i~ is ~\text{dp}[\text{path}_M]~.

Time Complexity: ~\mathcal O(N^3)~

Subtask 3

In this case, the tree is a line graph. We can use a similar dynamic programming recurrence as subtask 2 to compute the cost to vertex ~N~ from each squirrel. Here, ~\text{dp}[i] = \min\{ \text{dp}[j] + (x_i - x_j)^2 + (y_i - y_j)^2 + c_j \mid i < j \le N \}~, with ~\text{dp}[N] = 0~.

Time Complexity: ~\mathcal O(N^2)~

Subtask 4

We can extend the dynamic programming solution 3 to work on a tree. The ~\text{dp}~ value for a vertex can be computed from the other vertices on the path to vertex ~N~. Here, ~\text{dp}[i] = \min\{ \text{dp}[j] + (x_i - x_j)^2 + (y_i - y_j)^2 + c_j \mid j \ne i~ and ~j~ is on the path from ~i~ to ~N~ ~\}~, with ~\text{dp}[N] = 0~.

Time Complexity: ~\mathcal O(N^2)~

Subtask 5

With ~x_i = 0~, this problem becomes similar to Frog 3. Expanding the cost function ~(y_i - y_j)^2 + c_j~ yields ~{y_i}^2 + {y_j}^2 - 2 \cdot y_i \cdot y_j + c_j~. We can see that solving for ~\text{dp}[i]~ is equivalent to finding an index ~j~ where the line ~a_j \cdot y_i + b_j~ is minimized where ~a_j = -2 \cdot y_j~ and ~b_j = \text{dp}[j] + {y_j}^2 + c_j~. The difference in this problem is that the condition ~y_i < y_{i+1}~ does not always hold. While this can be handled by using some dynamic convex hull trick data structure, or a Li Chao tree, we can instead use the fact that ~y_i~ is random. A somewhat well-known fact is that a convex hull of ~N~ random lines has ~\mathcal O(\log N)~ lines. In addition, for any set of ~N~ lines, if another line is added to it, the convex hull will be some subset of a convex hull of the ~N~ lines plus the added line. Since the graph is a line in this subtask, we can add the lines in decreasing order of indices and rebuild the convex hull each time.

Time Complexity: ~\mathcal O(N \log N)~

Subtask 6

It may seem that we use a similar solution to subtask 5, but store a convex hull for each vertex in the tree. The convex hull is rebuilt for each vertex based on its parent's convex hull and the new line. The issue with this is that it can very easily exceed the memory limit. Instead, we can store the difference between a vertex's convex hull and its parent's convex hull. Because the lines are random, it can be seen that their convex hulls will only differ by a few lines, thus allowed for a solution that uses a linear amount of memory. When performing a depth first search on the tree, we can compute the difference when entering a vertex's subtree, and revert the difference when exiting the subtree.

Time Complexity: ~\mathcal O(N \log N)~

Subtask 7

If we consider a point in 3D space for each index ~j~ after computing its ~\text{dp}~ value at ~(x_j, y_j, \sqrt{\text{dp}[j]})~, then ~dp[i]~ is equal to the Euclidean distance squared to the closest point in the set of points ~j > i~ to the point ~(x_i, y_i, 0)~. We can perform these queries using a KD Tree, which works well on random points. The KD Tree needs to support arbitrary insertions and queries for the nearest point in ~\mathcal O(\log N)~ expected time. In practice, it is better to store the minimum and maximum ~x~, ~y~, and ~z~ values in the subtree of each node rather than dividing a large plane.

Time Complexity: ~\mathcal O(N \log N)~

Subtask 8

Similar to subtask 6, we need to be able to undo the insertion of a new point when leaving the subtree of a vertex. Since the last inserted point in a KD Tree is a leaf, we can easily undo this operation in ~\mathcal O(\log N)~ expected time.

Time Complexity: ~\mathcal O(N \log N)~

We are interested in hearing alternative solutions to this problem.