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

×

BTMNTREE - Editorial

2
1

PROBLEM LINK:

Div1
Div2
Practice

Setter- Igor Barenblat
Tester- Misha Chorniy
Editorialist- Abhishek Pandey

DIFFICULTY:

MEDIUM-HARD

PRE-REQUISITES:

Segment Tree + Lazy Propagation, Dynamic Programming, DP on Trees, Euler Tour of Tree

PROBLEM:

Batman starts from vertex $u$. At each second, he can choose to catch a robber whose power is strictly less than his'. Also, the path of robber must lie COMPLETELY inside the path of batman from his current vertex to the chosen vertex. His power then increases by $t$. We need to find maximal achievable power of batman if he catches robbers optimally.

QUICK EXPLANATION:

Key to AC- This question was a test of DP on trees along with Segment Tree and Lazy Propagation. Practice of such questions was the key.

Let $dp[v]$ be the maximum power obtained if we are at vertex $v$. We use segment tree along with lazy propagation to update and maintain the table. We narrow down the solution to $3$ cases-

  • When $u$ is parent of $v$
  • When $v$ is parent of $u$
  • Neither of above holds

We can easily obtain the range of update using $Euler$ $Tour$ of the tree and examining cases when its possible for batman to choose an appropriate vertex $g$ to catch robber, and when not.

EXPLANATION:

This was the hardest problem of the set. It is expected that the pre-requisites are clear. The editorial will have $4$ segments (please get the pun), one for pre-calculations done, one discussing the segment tree, other handling updates and lazy propagation along with case analysis, and last one DP. @mgch (tester's) solution will be referred to implementation.

1. Pre-calculations-

We intitialize the dp table with $-\infty$ initially, and do a DFS for Euler tour of tree. Euler Tour will store the time when we enter a node and its sub-tree (in $in[u]$), and when we exit it (in $out[u]$).

We initialise the dp table by setting $dp[s]=p$ where $s$ is the starting vertex and $p$ is initial power of Batman.

2. Building Segment Tree-

What do we store in node? As said earlier, the tree is built on array $dp[]$, so in each node (say $tree[v]$) we will store answer (i.e. $max(dp[l..r]$), or more formally-

  • if $l==r:$ tree[v] = dp[l];
  • else tree[v]=max(tree[2v], tree[2v+1]);

Code for building the tree is in tab below. Compare it with what you can come up with after reading the explanation!

View Content

3. Query, Update and Lazy Propagation-

We must keep the following condition in mind-

Let's denote Batman's current vertex by s (s=si initially). To catch the robber, Batman must choose a vertex g such that each vertex on the simple path between x and y (inclusive) lies also on the simple path between s and g (inclusive). If it is impossible to choose a vertex g so that this condition is satisfied, Batman cannot catch this robber.

Lets analyze it in light of $3$ cases analyzed in Quick Explanation Section. Let me refer to $x$ and $y$ as $u$ and $v$ respectively as its more conventional :).

  • $u$ is parent of $v$- To catch this robber, Batman must NOT be at a node which allows entry inside the simple path (from $u$ to $v$) from points other than $u$ and $v$. Else he will not be able to cover ALL nodes in simple path from $u$ to $v$. (If it is possible to catch the robber, we will update value of $dp$ table at ALL nodes from where Batman can chose an appropriate vertex $g$. To formalize, we will update all nodes where batman can choose a destination, i.e. sub-tree of $v$ if a destination can be chosen there, or everything outside sub-tree of $w$ ($w$=$u's$ first son lying in path from $u$ to $v$) if an appropriate destination can be chosen..
  • If $v$ is parent of $u$. - Dealt exactly same as above.
  • Neither of above holds $\implies$ Both have a common parent. Hence we can go from sub-tree of $u$ to sub-tree of $v$ and vice-versa. Both these sub-trees must be updated.

In above, remember that the vertices of $destination$ are updated! Recall what are we storing in $dp[v]$. "Let $dp[v]$ be the maximum power obtained if we are at vertex $v$."

The "syntax" to query is given below (i.e. how to call query function + Case analysis).See if it matches with what you understood!

View Content

With that clear, how do we exactly query? Thats even easier! Recall the standard query functions. The only change here is that we a re doing lazy propagation right now. Lets analyze what will be the cases/steps in query function.

  • If out of range, return $-\infty$
  • Update the node if needed.
  • If it lies completely in range, return the node.
  • If not in range, query in ranges $[L,Mid]$ and $[Mid+1,R]$ and return the maximum obtained answer. Make sure to push updates/do lazy updates before getting answer!
View Content

For reference, tester's implementation of push function is given below-

View Content

The only thing left is now update function. I think if you've read my previous segment tree editorials, it must be getting like "Something is repeating again and again." Yes! Thats the first sign of improvement! Try to make the update function on your own w.r.t. given query functions and syntax. A commented version is given in tabs below-

View Content

4. Dynamic Programming-

Finished.

??
?????
$??????????$

What?

Dynamic Programming says "Remember previous values" and I say "Remember the previous explanation." :p. how many of you noticed that this part is already discussed in $3$ segments above? Some exclusive parts were, in finding LCA of the two nodes $u$ and $v$ (Refer to link in pre-requisites) and our segment tree :).

SOLUTION:

The setter and tester's code are given below. If the links dont work, please view code in the "View content" tab. I pasted code their only for your comfort :). Tester's code is commented and discussed in editorial.

Setter

View Content

Tester

View Content

Editorialist Solution will be put on demand :)

$Time$ $Complexity=O(MlogN)$

CHEF VIJJU'S CORNER :D

1. Give a brief note on uses of Euler Tour in Competitive coding! EXPLORE!! (25 karma for decent answer :) ). [I can myself give notes, but I want you guys to explore and contribute as well. :D )

2. Author's Solution- He worked hard to write it and hoped you love it!!

View Content

3. ????????????????????????????

View Content

4. Test case Bank-

View Content

5. Related Problems-

This question is marked "community wiki".

asked 17 Jun, 14:39

vijju123's gravatar image

5★vijju123 ♦♦
15.1k11857
accept rate: 18%

edited 18 Jun, 16:22

1

Your editorials are really awesome,so easy to understand. :)

(18 Jun, 16:31) vivek_19982996★

Thank you <3333333. Things like these keep me going on despite a few things :)

(18 Jun, 16:43) 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,032
×1,703
×1,322
×156
×34

question asked: 17 Jun, 14:39

question was seen: 472 times

last updated: 18 Jun, 16:43