Problem Link
Author: Bogdan Ciobanu
Tester: Mark Mikhno
Editorialist: Bhuvnesh Jain
Difficulty
HARD
Prerequisites
Minimum vertex cover, Dynamic Programming, Matrices, Link-cut tree, Tropical Geometry
Problem
Chef and N animals need to cross the river from left side to the right side. There are some restrictions, meaning 2 animals cannot say together without the chef at the same time. This is represented by an edge (u, v) in a graph. This graph will be a tree. You need to find the minimum size of the boat for the chef and animals to safely cross the river without any violations.
We need to find this answer after every addition of a new edge to the tree.
Explanation
Let us rephrase the problem statement. Let the set of vertices in the tree be denoted by V. Let the group of animals we take along with Chef for the first time in the boat we denoted by X. We need to minimise the size of set X and ensure that no vertices, u \in (V - X), are directly connected by an edge in the tree. (Note: vertices in X may be connected by an edge).
It is clear that we will need Chef in the boat, so we won’t even count his seat.
Let G(V, E) be the graph in the problem, for a specific query. Let M(G) be the minimum vertex cover of G and m(G) = |M(G)|. Also, denote b(G) as the minimum size of the boat for G.
Claim 1: m(G) <= b(G)
Proof: It is clear that the first time we leave the left riverbank we cannot leave any restriction active and the minimum number of animals to do so is m(G).
Claim 2: b(G) <= m(G) + 1
Proof: We have a trivial solution using (m(G) + 1) seats for animals in the boat. We’ll keep M(G) on the boat at all times and transport (V - M(G)) using the remaining seat. In the end, we’ll leave M(G) on the right bank as well.
Claim 3: For 4 <= N and G not the star tree we have a solution with m(G) = b(G).
Proof: Because G is not the star tree, then m(G) >= 2 so we can choose two different nodes S and U from M(G). We’ll start as usual, with M(G) in the boat and then we’ll leave S on the right riverbank. Using its seat, we’ll transport all nodes which are not in M(G) and which are adjacent to S. Then, we’ll take S back on the boat. Now we want to move its neighbours to the right riverbank. It is clear that S and U have at most one neighbour in common. We’ll move U to the left riverbank and move S’s neighbours, prioritizing, if it’s the case, their common neighbour. When we’re done, we bring U back and then move M(G) to the right riverbank.
Claim 4: For the star tree we can use the trivial solution with 2 seats.
Proof: The central node being connected to all the nodes will always be required. So, we always to take the centre node and any other animal. This is the optimal answer.
With the about thoughts in mind, let us start with a dynamic programming approach. Let G_{node} be the sub-tree rooted in the node.
Let f(u) = min(m(G_u)) with the obligation that we’ll select u in the solution and g(u) = min(m(G_u)), then:
The answer will be in g(1).
The reasons for the above relations are as follows:
-
For f(u), since u is selected we add 1 and we have both options for the children of u, either to select or not select it. This is captured by g(u).
-
For g(u), we have two options, either the node was selected which is captured by f(u) or the node was not selected resulting in the selection of all the children of u.
The time complexity of the above approach will be O(N^2) and is enough to pass the first subtask. You can notice that the f and g values for only the nodes which are the ancestor of the newly added node get changed. Thus, the algorithm can be easily modified to work in O(N * diameter). On the addition of a node, we only move up the ancestor and update the f and g values. Since the diameter of the tree is limited to 40 in the second subtask, we can easily make the solution pass for 41 points.
For the complete solution, we require the idea of Tropical Semiring. You can read more about it here.
For two numbers, a and b, the operations are defined as follows:
Consider that we’ve build the heavy-light decomposition of the tree (and for the sake of simplicity consider the tree to be binary) before-hand and let l_u be the light son of u and h_u be the heavy son of u, then we can find f(u) and g(u) using matrix multiplication:
To go from binary tree to any tree we must take care to consider all the light sons as a unity. The nice to handle matrix multiplications doesn’t really work with them and changes must be made by hand. The unity matrix will be
This is because g(l_u) = g(h_u) = f(l_u) = f(h_u) = 0 as the node currently doesn’t have any children.
Let us consider how the matrix multiplication looks like when we have 3 children, where u_3 is heavy and u_1 and u_2 is light.
The matrix required was:
So, the changes required to be made by hand are simply first tracing back the terms inside the min function, removing the contribution of 1 and then adding it back. For details refer to the comments in the solution of the author. As usual, we’ll use a segment tree over all chosen chains to compute matrix multiplications on the range once the HLD is done.
The time complexity of the above solution is O(N * {\log}^{2}{N}) which is enough to pass subtask 3, when number of nodes, V <= 2 * {10}^{5}.
For the complete solution, we need to eliminate the additional \log{N} factor from the solution. For this, we will use link-cut tree instead of HLD. For details, refer to the full solution below.
If your solution was somewhat different, feel free to explain in the comments section below.
Time Complexity
O(N \log{N})
Space Complexity
O(N)
SOLUTIONS:
Author’s solution using (HLD + Segment tree) can be found here. (Will pass subtask 1 & 3 only)
Author’s solution using Link-Cut-tree can be found here.
Editorialist’s solution for first 2 subtasks can be found here.