RIVER - Editorial

Problem Link

Practice

Contest

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:

f(u) = 1 + \sum_{v \in child(u)} g(v)
g(u) = min(f(u), \sum_{v \in child(u)} f(v))

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:

a + b = min(a, b)
a * b = a + b \text{(Usual addition)}

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:

\begin{bmatrix} 1 * g(l_u) & f(l_u) \\ 1 * g(l_u) & \infty \end{bmatrix} \begin{bmatrix} g(h_u) & \infty \\ f(h_u) & \infty \end{bmatrix} = \begin{bmatrix} min(1 + g(l_u) + g(h_u), f(l_u) + f(h_u)) & \infty \\ (1 + g(l_u) + g(h_u)) & \infty \end{bmatrix} = \begin{bmatrix} g(u) & \infty \\ f(u) & \infty \end{bmatrix}

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

\begin{bmatrix} 1 & 0 \\ 1 & \infty \end{bmatrix}

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.

\begin{bmatrix} 1 + g(u_1) & f(u_1) \\ 1 + g(u_1) & \infty \end{bmatrix} \begin{bmatrix} 1 + g(u_2) & f(u_2) \\ 1 + g(u_2) & \infty \end{bmatrix} \begin{bmatrix} g(u_3) & \infty \\ f(u_3) & \infty \end{bmatrix}
= \begin{bmatrix} 1 + g(u_1) & f(u_1) \\ 1 + g(u_1) & \infty \end{bmatrix} \begin{bmatrix} min(1 + g(u_2) + g(u_3), f(u_2) + f(u_3)) & \infty \\ 1 + g(u_2) + g(u_3) & \infty \end{bmatrix}
= \begin{bmatrix} min(1 + g(u_1) + min(1 + g(u_2) + g(u_3), f(u_2) + f(u_3)), f(u_1) + 1 + g(u_2) + g(u_3)) & \infty \\ 1 + g(u_1) + min(1 + g(u_2) + g(u_3), f(u_2) + f(u_3)) & \infty \end{bmatrix}

The matrix required was:

\begin{bmatrix} min(1 + g(u_1) + g(u_2) + g(u_3), f(u_1) + f(u_2) + f(u_3)) & \infty \\ 1 + g(u_1) + g(u_2) + g(u_3) & \infty \end{bmatrix}

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.

I did everything with HLD and segment trees but I didn’t really use DP, instead I maintained a maximum independent set.

To solve this problem you just need to find a minimum vertex cover on the tree which is essentially the same as finding a maximum independent set. Given a rooted tree one can easily construct a maximum independent set by following the rule: a node is in the set iff none of its children are in the set.

The proof why this will construct a maximum independent set follows from the fact that for any leaf in a graph there exists a maximum independent set containing that leaf.

So with this rule one just needs to maintain a maximum independent set on the tree, basically one boolean value for each node. When a new node is added to the tree, as the new node will be a leaf, it will be put in the independent set. Then walk up the tree, switching all of the boolean values of every node that you visit, until you find the root or a node with a sibling that is already inside of the independent set. This all just follows from the rule.

Using HLD together with a boolean segment tree this can be done in O (\log^2 N) time. As all operations used are very cheap, even my non-optimized solution in pypy2 only took 3 s for subtask 4.

4 Likes

I think this is the most logical method in this case. I used something pretty similar (with a slightly different system to work out how far up the tree a mass-flip should go).

Be slightly careful though: you should choose the heavy child to be the one with the most total nodes underneath it (down to the bottom of the tree), not just the one with the most immediate children. As it is, you can break your program with an example like this (the third line of the input file):
1 1 2 2 3 6 6 7 7 8 11 11 12 12 13 …
(Each group of five is formed by adding 5 to the previous group of five.)

That example (1 1 2 2 3 …) would result in a quadratic running time. Assuming that’s fixed, I think it should run in O(N \log N) total running time. It looks like it might be order N(\log N)^2 because each update involves O(\log N) chains of length O(\log N), but the total length of the chains in an update is limited to N, which means the maximum sum of logs of chain lengths in an update is O(\log N).

2 Likes

You’re completely correct that the code I have creating the HLD is bad. I don’t know why I did it like that. I fixed the error and surprisingly the run time only improved by a little amount (CodeChef: Practical coding for everyone), maybe the testcases were weak. As for the time complexity I don’t see how it is exactly O(n log n), but it clearly should be somewhere in the range O(n log n) to O(n log^2 n). I get one of the log(n) because of using segment trees, so it is at least O(n log n). The second log comes from having to switch heavy path possibly log n times.

For each i, a given heavy component can only be processed at most once: either you find a black sibling and halt the flipping altogether, or you go right to the top of the heavy component, in which case you can’t revisit it. The time taken for a single iteration of the while True loop is O(\log(n_h)) where n_h is the size of the heavy component h, because you are using a segment tree of size n_h. So the total time for an iteration of the i loop is O(\sum_h \log(n_h)). But \sum_h n_h\le n, so the sum of logs is maximised at n_h=3, and is O(\log n) overall.

1 Like

You’re right, my mistake. I think it will end up being of order n\log(n)^2 and I think you can get an example worst case tree by defining T(k) to be a tree from whose root you have two 2^{k-1}-long paths, each ending in a copy of T(k-1) (T(0) being a point). You can add edges in an order such that all of the degree 3 vertices are in the independent set, except when you add the edges down a 2^r-long path, which will then flip all the way to the top.

(I tried to delete the previous comment-but-one of mine which is wrong, but it refuses to let me…)