LVGFT - Editorial

[melfice]

PROBLEM LINK:

Practice
Contest

Author: Zain Ali
Tester: Istvan Nagy
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.

Tester’s solution can be found here.

RELATED PROBLEMS:

[triveni]

My Solution is different : [C++ Code][1]

1. Root the tree at some node - say node 1.
2. Do inorder dfs traversal in the tree such that any subtree appears consecutive in the inorder array. For any node u, let’s denote L(u) be the starting index in the inorder array and R(u) be the last index in the inorder array for the subtree rooted at u.
3. Now suppose we need to find the answer (largest two reachable) for some node c. If c has a bank, then answer is (N, N-1). Otherwise, we do the following -
4. Find the answer in the subtree rooted at c. That is max element reachable in the range L© to R©.
5. Find the answer in ranges 1 to L©-1 and R© to N. Overall answer is best of these three.
6. Whenever there is an update operation at node u, we do the following-
7. In the range L(u) to L® find the answer, lets call it ans_u. In the ranges 1 to L(u)-1 and R(u) to N, update that ans_u is a candidate. Similarly let’s call the best two in the range 1…L(u) and R(u)…N be ans_u_p. Then update in the range L(u)…R(u), ans_u_p.
8. I am using O(1) RMQ to answer in any range l…r.
9. Complexity is O((N+Q)log N).
10. See code -

[1]

 


  [1]: https://www.codechef.com/viewsolution/16186482

[gagan86nagpal]

In the 7th point , shouldn’t it be " In the range L(u) to R(u) " ?

[gagan86nagpal]

I think there is a typo in 4th Paragraph of Explanation section.
“it is N-1, otherwise” seems to be correct.
I guess editorialist is assuming 0-based indexing.

[nilesh3105]

In case someone else has problem understanding this editorial like I did:

1. This editorial didn't mention how to initialize the DSU with correct $m1, m2$ values. But it's quite simple when you think about it. Assume in the starting branch is open in **every city**. Now close branches in those cities in which a branch was never opened.
2. In editorial it says to

   First, create vertex $C$ as a separate component.

   This is as trivial as it seems. $m1, m2$ values for this component would simply be 2 largest values not equal to $C$.

Also from what I understand in complexity analysis, it assumes that to merge S_1 and S_2 it takes O(|S_2|) time. Which would require us to store V_{S_i}. But I did not store V_{S_i} and the solution still passed so ¯\_(ツ)_/¯.

My solution. It should be way easier to follow than the Author’s and Tester’s solution.

[kush2327]

@nilesh3105 could you please explain the cal function in your code?

[roll_no_1]

@nilesh3105 Amazingly well written solution, but there’s a corner case, where your solution will fail. This one:
1

1 2

1 1

2 1

But anyways, thanks a lot, your solution helped me understand the problem very well :).