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

×

LVGFT - Editorial

1
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

asked 14 Nov, 01:22

melfice's gravatar image

2★melfice
412
accept rate: 0%

edited 14 Nov, 02:13

1

Difficulty: Cakewalk? Seriously?

(14 Nov, 01:28) vatsalsura3★

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

(14 Nov, 01:29) vijju123 ♦5★

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.

link

answered 14 Nov, 02:10

bazsi700's gravatar image

6★bazsi700
2177
accept rate: 12%

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

(14 Nov, 17:43) sdssudhu6★

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

link

answered 14 Nov, 06:01

givingmybest's gravatar image

5★givingmybest
513
accept rate: 0%

I did the exact same but even after trying 2 full days couldn't debug. #sed_lyf :'(

(14 Nov, 16:43) mathecodician5★
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

question asked: 14 Nov, 01:22

question was seen: 318 times

last updated: 14 Nov, 18:27