Editorial for Wesley's Anger Contest 5 Problem 7 - Acorn Delivery System
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