## Editorial for Wesley's Anger Contest 5 Problem 7 - Acorn Delivery System

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Author:

##### Subtask 1

For each squirrel , we can iterate through all subsets of squirrels that include squirrel and that could receive the 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:**

##### Subtask 2

We can see that we can form a tree with vertices rooted at vertex with a directed edge from vertex to vertex for each vertex where . For each squirrel, we can use dynamic programming on the vertices on the path from vertex to vertex to compute the minimum cost. Suppose is the vertex on the path from vertex to vertex , then , with . If there are vertices on the path from vertex to vertex , then the answer for squirrel is .

**Time Complexity:**

##### 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 from each squirrel. Here, , with .

**Time Complexity:**

##### Subtask 4

We can extend the dynamic programming solution 3 to work on a tree. The value for a vertex can be computed from the other vertices on the path to vertex . Here, and is on the path from to , with .

**Time Complexity:**

##### Subtask 5

With , this problem becomes similar to Frog 3. Expanding the cost function yields . We can see that solving for is equivalent to finding an index where the line is minimized where and . The difference in this problem is that the condition 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 is random. A somewhat well known fact is that a convex hull of random lines has lines. In addition, for any set of lines, if another line is added to it, the convex hull will be some subset of a convex hull of the 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:**

##### 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:**

##### Subtask 7

If we consider a point in 3D space for each index after computing its value at , then is equal to the Euclidean distance squared to the closest point in the set of points to the point . 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 expected time. In practice, it is better to store the minimum and maximum , , and values in the subtree of each node rather than dividing a large plane.

**Time Complexity:**

##### 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 expected time.

**Time Complexity:**

We are interested in hearing alternative solutions to this problem.

## Comments