LVGFT - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

Author: Full name
Tester: Full name
Editorialist: Oleksandr Kulkov

DIFFICULTY:

MEDIUM

PREREQUISITES:

DSU (Disjoint Set Union)

PROBLEM:

You are given a tree on vertices 1,2,\ldots,N. Initially, each vertex contains no bank branch, though they appear in vertices over the time. You need to process two types of queries:

  1. 1 C - A bank branch is opening at vertex C. Multiple bank branches may be opened in a vertex over time.
  2. 2 C - Let V be the set of vertices v that have the following property: the unique tree path from C to v, both endpoints included, contains at least one vertex with a bank branch. Find the second maximal element in V (that is, if V is a sorted array, V[|V|-2]; remember that V contains indices of vertices, each from 1 to N). Output -1 if |V|<2.

QUICK EXPLANATION:

Process the queries offline in reverse order. Get rid of multiple bank branches opening in a vertex by only considering the first event. In reverse order, the second query is the same, while the first query means some bank branch is closing in the vertex. Maintain disjoint sets of vertices that are obtained as connected components after removal of all vertices with bank branches. The answer to the second type query for each vertex in such component is the same. For each component, maintain two indices of nodes that are maximum and second maximum in the set V. The first type queries in reverse order result in merges of the components. Maintain the size of the components to merge smaller component to larger; the indices of the two nodes may only decrease, and decrementing them naively for the larger component (checking whether the decremented index lies in another component) results in an O(N\log N) time complexity.

EXPLANATION:

Refer to the “Quick explanation” section for the outline of the solution and the first step: reversing the queries and getting rid of the redundant ones.

Maintain disjoint sets of vertices S_i that have no bank branches and that are connected if we disallow entering the vertices with bank branches: that is, sets S_i at each moment can be obtained as connected components that appear after the removal of all vertices with bank branches. Why do we need these sets? The reason is that for the vertices of the same set the answer to the second query is the same. We will call these sets ‘components’.

Store the components S_i in a DSU data structure. In addition, for each component, store the indices of the two nodes, m_1 and m_2 that are the maximum (m_1) and the second maximum (m_2) vertices in the set V for this component, so that the m_2 is the answer to the second type query for all vertices of the component. Also, for each component, maintain its size, and in the implementation of the Unite operation of DSU make smaller component children of larger component’s root.

Suppose that we know how to update the structure when the bank branches are closing. Then, the answer to the second type query can be easily obtained: if there is a bank branch the vertex, it is N-2, otherwise, it is m_2 of the corresponding component.

Suppose we now have a first type query to close the bank branch at vertex C. First, create vertex C as a separate component. Traverse all edges incident to C and if they lead to a vertex of without the bank branch, make a DSU merge operation of the corresponding components.

How do the indices m_1 and m_2 change when two components are being merged?

First, notice that m_1 and m_2 for the components other than the two being merged remain intact: for the vertex to belong to the set V of the component S it is necessary and sufficient for it either to have a bank branch or to belong to the component other than S. Thus, the merge of the components different from S_i does not affect it’s set V and thus does not affect it’s m_1 and m_2 indices.

Suppose we merge the components S_1 and S_2, |S_1|\ge|S_2|. Then the following “naive” algorithm turns out to be fast enough to recompute the indices:

  1. Use S_1.m_1 and S_1.m_2 as initial guess for the new indices of the component S_1\cup S_2; the set V_{S_1\cup S_2}\subset V_{S_1}\cap V_{S_2}, so the correct indices may only be lower.
  2. Count how many of the indices m_1 and m_2 (either 0, 1 or 2) are no longer valid: the corresponding vertices now lie in the component S_1\cup S_2. If m_1 is invalid whereas m_2 is valid, set m_1 to m_2.
  3. Check vertices m_2-1, m_2-2, \ldots in order: if the corresponding vertex does not belong to S_1\cup S_2, set either m_1 (if it is invalid) or m_2 to that vertex. Break if both indices are valid.

It is easy to see that the algorithm is correct (the indices may only decrease, and we check all candidates decrementing by one). What is it’s time complexity?

The key observation is that for the component S of size |S| the total number of operations required to decrement its indices in all merge events may not exceed O(|S|), provided that this component was the largest in all merges, that is, we used its indices m_1 and m_2 as the reference point. Indeed, when decrementing, we stop as soon as the current index does not lie in S. Thus, the number of times we continue iteration may not exceed |S|, or 2|S| when two indices are taken into account.

Now consider each component at the moment it gets merged into the larger component – we can bound the number of decrements for it as O(|S_i|). The total number of decrements thus does not exceed (C is the constant used in Big-O notation):

C\times \sum_{\text{over all merges of the components}} |\text{smallest component in the merge}|=O(N\log N)

The asymptotical equality is from the fact that each vertex may only move from the smaller component to the larger component O(\log N) times, as each move double the size of the component the vertex belongs to.

The overall time complexity is O(N\log N+Q) (we assume the DSU operation time complexity O(1)), the memory complexity is O(N+Q).

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found [here][333].

Tester’s solution can be found [here][444].

RELATED PROBLEMS:

[333]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.
[444]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server

1 Like
2

Difficulty: Cakewalk? Seriously?

1 Like
3

Its accidentally posted it seems. Bug or breach of…well, reporting to @admin.

4

I solved the problem online: I first made and Euler tour, then calculated the maximum and second maximum values with a sparse table. I also managed a segment tree with the answer for each node.

When an update comes, we have to update the subtree of the node with the maximum of the rest (it can be calculated with 2 queries), and the other sub-subtrees of the node (It’s O(children*log(N)), but overall it is O(Nlog(N)), because we only add each bank at most once). Then we do segment updates on seg tree with lazy propagation, and put (n,n-1) to the updated vertex, and the maximums of the subtree to all outer vertices. (2 updates).

Overall complexity is O(N log(N))

Here is my code.

1 Like
5

My approach for online solution using dfs order and segment tree: I did dfs order on the tree and stored position of all nodes. Now whenever a new branch will be opened at some node, reaching points for some cities will be changed, I maintained a segment tree of pairs representing {2nd max, max} reachable from any node (initially all {0,0} ). Now updates can be done using dfs order which is already done. for node X, update [1-(X-1)], [X+(size of tree rooted at X), n] with {second max, first max} of tree rooted at X. Also for all children of node X, update their reach with maximum they can go now.
Link: https://www.codechef.com/viewsolution/16263353

6

I did the exact same but even after trying 2 full days couldn’t debug.

#sed_lyf :'(
7

I also solved it with the same idea but without the sparse table part.