You are not logged in. Please login at www.codechef.com to post your questions!

×

LVGFT - Editorial

0
2

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:

asked 14 Nov, 01:25

melfice's gravatar image

2★melfice
412
accept rate: 0%

edited 14 Nov, 19:12

admin's gravatar image

0★admin ♦♦
16.9k347485513

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.

(2 days ago) gagan86nagpal5★

My Solution is different : C++ Code

  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(c) to R(c).
  5. Find the answer in ranges 1 to L(c)-1 and R(c) 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(r) 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 - Code
link

answered 14 Nov, 21:01

triveni's gravatar image

5★triveni
506126
accept rate: 16%

edited 14 Nov, 21:03

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

(2 days ago) gagan86nagpal5★

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 all cities. 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.

link

answered 5 hours ago

nilesh3105's gravatar image

4★nilesh3105
2566
accept rate: 18%

edited 5 hours ago

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×11,987
×1,879
×253
×46

question asked: 14 Nov, 01:25

question was seen: 426 times

last updated: 5 hours ago