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

×

CHAQOT - Editorial

1
1

PROBLEM LINK:

Div1
Div2
Practice

Setter- Kirill Gulin
Tester- Ivan Safonov
Editorialist- Abhishek Pandey

DIFFICULTY:

Hard

PRE-REQUISITES:

Persistent Segment Tree, Dynamic Programming approach to find Least Common Ancestor (LCA) of two nodes, DFS

PROBLEM:

We are given a tree with $N$ nodes - each node having a value $val_i$. We have to answer $Q$ queries where each query will give us $k$ nodes $(u_1,u_2,..,u_k)$ and a value $r$. We need to tell the minimum of $|val_u-r|$ where $val_u$ is the value of a node lying in path covering all the given $k$ nodes.

QUICK EXPLANATION:

Key to Success- Practice of Persistent Segment Trees was needed. Labeling nodes of segment tree by $depth[node]$ can potentially make things quite simple.

Sort the query nodes in order of DFS traversal. Also, make a duplicate array $val$ which stores the values, and the nodes to which the values correspond, in sorted order. The answer for a query, after sorting nodes in order of DFS, is union of paths from $u_i$ to $LCA(u_i,u_{(i+1)\%N})$. Queries are hence reduced to, in a path from $u$ to $LCA(u_i,u_{(i+1)\%N})$, find the $val$ closest to $r$.

To answer these make a persistent segment tree of all nodes, the tree storing the depth of nodes for the version they were made (or, they will store some random garbage value if they are "useless" node for that version). As we will see in editorial depth is non-increasing for a version of tree, a simple check of $depth[node] \ge depth[LCA(u_i,u_{(i+1)\%N})]$ can confirm that the node lies in the path.

Now, find an index $j$ in $val$ such that is closest to $r$. We now break the queries into $2$ groups, one will try to find the greatest possible index in range $[1,j-1]$ so that node corresponding to value at that index lies in path. The other part will try to find the smallest possible value in range $[j,N]$ similarly.We pick the one giving lesser value out of the two as answer. These queries are repeated $k$ times so that all nodes in $S$ get covered

EXPLANATION:

This editorial is going to be a bit exhaustive. It is expected that you guys are aware of the concept of persistence, as well as the idea of finding LCA of two nodes in $O(LogN)$ time. If thats not the case, please head over to links in pre-requisites first. We will be primarily discussing setter's solution, and breaking/modularising this editorial with respect to each step required to get AC.

1. Pre-Processing-

The first thing to do, is to make a pair of $< val_u,u >$ where $val_u$ is the value of node $u$. Now, sort it. We will be making segment tree over this $val$ array. Before moving on, compress/map the value of indices of $val_u$ from original array to sorted array. Meaning, make a table which tells you "The value which was at index $u$ in original array is at index $v$ in sorted val array."

An illustration of making this table is in tabs-

View Content

The above table will be used in making and querying over the segment tree, as it can be used during DFS of a node to find directly at which index of $val$ array the current node corresponds to.

Also, the queries dont guarantee that nodes will be in order of DFS, they can be in any random order! Hence, we will need to sort them in order of DFS , for which we need to do a Euler tour of tree and calculate in-time and out-time of all nodes.

2. What to store in the segment tree?

We will be storing $depths$ of the nodes in the tree. Why? That cannot be answered right now. It wont make sense until we grasp concept of constructing and updating the tree. But for now, just know that it is very useful in querying.

The parent-child relation is, parent will store the the greater value of depth. In other words, if our segment tree array is $t[]$, then the relation is-

t[v] = max(t[lson[v]], t[rson[v]]);//lson=left son. rson=right son

The leaves will simple store depth of the node for which the segment tree is made - only for valid index in $val$ array. (Meaning, the range $[l,r]$ of leaf must follow $l=r=ind$ where ind is index of that node in $val$ array).

3. Constructing and Updating the tree, along with concepts involved-

First let me describe the procedure, and then we will move over to the concept.

Start a DFS from the root. Make a complete segment tree for the root or input tree, and for rest of nodes, add a new root, and consequently $logN$ new nodes to cover its path from root to leaves. (The concept of persistence). This means that, for root node, $build()$ function will be invoked, while for other $N-1$ nodes, we will update the tree by adding $logN$ new nodes on path from root of segment tree to valid/corresponding leaf.

I should highlight how these newly added nodes point to the children for those weak in the topic. You can refer to tab below.

View Content

Now, coming to the reasoning part. The first question is why store depth in segment tree. Remember that when we update to add new nodes, the new nodes can either point to a newly created child of current version, or point to a child from older version. It cannot point to a child of newer version as we are not modifying old nodes - instead we are creating new ones. Hence note that, depth of a node is maximum and root and may decrease as we go till leaves.

Hence, for now just say that I need a path from node $u$ to node $v$. What will it look like? We will go from $u$ to $LCA(u,v)$ and from there to $v$. Since depth is non-increasing, a simple check of $depth[node] \ge depth[LCA(u,v)]$ is a sufficient check that the current node of segment tree is holding information about path from $u$ to $LCA(u,v)$ etc. We query segment tree of $u$ for this, and get info about path from $u$ to $LCA(u,v)$.

The above paragraph is the million dollar one here. If you understand this, understanding setter's solution and concept is a breeze.

Now, lets discuss implementing. For build function, we have to build entire segment tree for root node of tree. If we arrive at the correct leaf node (for which $l=r=ind$ where $ind$ is index in $val$ array) then we update the leaf node by $depth$, else we leave it empty. The relation between parent and child nodes stay the same. Can you try writing the build function? For your reference, its given in tab-

View Content

Also, now that you have done build function, try the update one as well (especially if you failed in framing build function yourself). The logic is similar. We create a new root, then create $LogN$ new nodes for path from root to corresponding leaves. The new nodes can point to children of current version (if created) or older versions. The function is given in tab below-

View Content

4. Answering Queries-

Hopefully section $3$ is clear to you. If it is, not much effort is needed here.

The first thing to do is, sort the given $k$ nodes in order of DFS. This can be achieved by earlier done Euler Tour of tree. We can use inbuilt sort function, and use a custom comparator function which would compare two nodes on basis of their in-time. A short code to do this is below-

View Content

Now, also note that how set $S$ will be formed. Say we are given $k$ nodes $(u_1,u_2,...,u_k)$, and we sorted them in order to DFS. Now, the answer for any $2$ adjacent query nodes, $u_i$ and $u_{i+1}$ is simple. We already discussed answer if there are only $2$ nodes in query. The answer then was path from $u$ to $LCA(u,v)$ to $v$. Or, in other words, path from $u_1$ to $LCA(u_1,u_2)$ + Path from $u_2$ to $LCA(u2,u_{3\%2=1})$. In general terms, answer for a query is path from $u_i$ to $LCA(u_i,u_{(i+1)\%N})$. Few rough examples prove that this path is sufficient.

Now,look at what we have to answer. We need to find a node with value as close to $r$ as possible. Now, $val$ array is sorted - and we can surely use the position of value closest to $r$. We hence, perform a binary search on val to find the closest value of $r$. Now, we can transform our query to - "Query the tree the to get to leaf as close as possible corresponding to given index".

This is done by breaking query into $2$ parts. Say the index we got for the closest value was $j$. One part will deal from finding a index as large as possible in range $[1,j-1]$ such that the node lies in path, and the other will deal with finding an index as small as possible in range $[j,N]$ such that a node from that index lies on path.

I will describe the first function, and leave the other function as an exercise as both use exact same logic. We have to find the largest possible index in $[1,j-1]$ such that a node of that index lies in $S$. Take a note of the necessary information, i.e. the node $u$ whose segment tree we will be querying, and the $depth[LCA(u,u_{i+1})]$ (we discussed use of $depth[node]$ in above sections already).

Now, the logic goes like-

Check the interval $[l,r]$ to which current node corresponds. The following ideas must be accommodated- - if $r\ge j$ try going to right child.
- if $l< j$ and $r>j$ then goto left child.
- if reached at leaf, return abs(t[l]-r); provided depth permits.
- At the node, do not forget to check for depth data.
- A default preference to right child is given (as we want to achieve a index as large as possible in range $[1,j-1]$

Hmm, looks tough? Well, I wanted it to look so! xD. In a contest you might be able to come up with these guidelines and might face problem in implementing these ideas to code.

View Content

Now, you have the ideas. you know briefly how to do it for range $[1,j-1]$. Try working on the other function, which returns the smallest index possible in range $[j,N]$. The ideas are almost identical, just some changes in guidelines. Construct your guidelines, and hence realize the function. Solution for function given in tab.

View Content

And with this, we are done with the hardest problem of the set. Please feel free to ask in case of any doubts (the things to explain were exhaustive, hence it is possible that tiny details here and there might be missed out. I'd request you to help me by pointing any such instance out. :)). Setter's code was used as reference, and you can refer to it as well for any other needed details. :)

SOLUTION:

The solution codes are also posted in tabs below for your reference incase the links dont work. Enjoy, and please help me improve the editorial by asking doubts and raising clarification requests :)

Setter

View Content

Tester

View Content

$Time$ $Complexity=$ $O(Q\sum{k}(LogK +LogN))$ where $k$ is the number of nodes given in query.

CHEF VIJJU'S CORNER :D

1. Here is some after thought. What if, instead of using "$S$ is union of path from $u_i$ to $LCA(u_i,u_{(i+1)}\%N)$" we use "$S$ is union of path from $u_i$ to $LCA(u_i,u_{(i+1)}\%N)$ AND from $u_{(i+1)\%N}$ to $LCA(u_i,u_{(i+1)\%N})$? Will any extra nodes get covered this way? Is this definition also correct, but a little inefficient? Argue.

2. Setter's Notes-

View Content

3. A few practice problems-
- Persistent Segment Tree
- LCA

This question is marked "community wiki".

asked 22 Jul '18, 17:43

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

edited 23 Jul '18, 02:49


Here is my solution using heavy light decomposition and merge sort tree. I have used the fact that $S$ is the union of paths from $u_i$ to $LCA(u_1,u_2,...u_k)$.

link

answered 24 Jul '18, 21:38

ankurdua15's gravatar image

6★ankurdua15
611
accept rate: 33%

I'd thank you on behalf of future community members who will surely appreciate your efforts :)

(24 Jul '18, 21:40) vijju123 ♦♦5★

It can be easily solved using heavy light decompostion + segment tree.

link

answered 23 Jul '18, 02:40

tautsjasiunsas's gravatar image

5★tautsjasiunsas
862
accept rate: 20%

Can you give a link to your code for others to see? +15 karma if its commented for easy understanding :)

(23 Jul '18, 02:42) vijju123 ♦♦5★
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:

×2,214
×1,768
×1,359
×259
×209
×99

question asked: 22 Jul '18, 17:43

question was seen: 505 times

last updated: 24 Jul '18, 21:40