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

×

TRCNTCT - Editorial

0
1

PROBLEM LINK:

Practice
Contest

Author: Daniil Melnichenka
Tester: Hasan Jaddouh
Editorialist: Daniil Melnichenka

DIFFICULTY:

Hard

PREREQUISITES:

Dfs, divide and conquer or segment tree.

PROBLEM:

Given a tree of $N$ vertices, find a number of intervals $[L, R]$, such that if we leave only vertices from this interval in the tree, the resulting graph would be connected.

QUICK EXPLANATION:

Solve the task for a fixed root and apply divide-and-conq.

EXPLANATION:

Let's count the number of intervals $[L, R]$ that contain vertex $N/2$. We can color vertices which indices are less than $N/2$ in blue, others in red.

How can we check if a pair $(X, Y)$, where $X$ is blue and $Y$ is red, is a valid pair? Let's consider all the blue vertices $V$ (such that $V \ge X$). Paths from $V$ to $N/2$ should:

  1. not contain any vertex with index strictly less than $X$;
  2. not contain any vertex with index strictly more than $Y$. Some symmetrical conditions should be hold for vertex $Y$.

Let's take a blue vertex $X$. We need to know:

$low_X$ = the minimal index among the vertices containing in all paths from vertices $V$ ($X \le V \le N/2$ ) to vertex $N/2$.
$high_X$ = the maximal index among the vertices containing in all paths from vertices $V$ ($X \le V \le N/2$ ) to vertex $N/2$.

We can firstly calculate $low_x$ = the minimal index on path from $X$ to $N/2$ (and similar values for $high_X$) and then make some technique like prefix-minimum (thus $low_X = min( low_X, low_{X+1} )$).

Similarly for every red vertex we need to calculate:

$low_Y$ = the minimal index among the vertices containing in all paths from vertices $V$ ($N/2 \le V \le Y$) to vertex $N/2$.
$high_Y$ = the maximal index among the vertices containing in all paths from vertices $V$ ($N/2 \le V \le Y$) to vertex $N/2$.

Obviously a blue vertex $X$ is a candidate if $low_X = X$, a red vertex $Y$ is a candidate if $high_Y = Y$. A pair $(X, Y)$, where both $X$ and $Y$ are candidates, is valid if $high_X \le Y$ and $low_Y \ge X$. We can note that as $X$ decreases, $high_X$ increases; and as $Y$ increases, $low_X$ decreases. Evidently we can loop vertex $X$ from $N/2$ to $1$ and use a two pointer technique to count an interval of red vertices that are valid for current $X$.

The entire algorithm described above works in $O(N)$. Now let's use a divide-and-conquer technique to get $O(NlogN)$ and solve the whole task. Let's call the vertex $\frac{L + R}{2}$ a root of the interval $[L,R]$. In every layer of divide-and-conquer we should run dfs from all the roots of this layer. But it will be $O(N^2)$ now. Consequently in dfs for some interval $[L,R]$ we should never visit vertices that don't belong interval $[L,R]$. If some vertex $V$ from the interval $[L,R]$ can't be reached from vertex $\frac{L + R}{2}$ in this way then we should assign $low_V=-infinity$ and $high_V = infinity$. Thus it is $O(N)$ for each layer and the entire complexity is $O(NlogN)$.

ALTERNATIVE SOLUTIONS:

Let's fact that the range $[L, R]$ is valid if the number of edges that connect vertices from that range is $R-L$. So, we iterate $L$ and maintain in segment tree the number of missing edges for each $R$ in segment tree. So this value would be zero, if $R$ is valid for our $L$. The number of zeroes can be calculated with segment tree that knows the number of maximums on range. The complexity is also $O(NlogN)$.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

RELATED PROBLEMS:

This question is marked "community wiki".

asked 20 Aug '17, 20:34

hloya_ygrt's gravatar image

4★hloya_ygrt
119
accept rate: 0%

edited 21 Aug '17, 00:26

admin's gravatar image

0★admin ♦♦
19.8k350498541


Could someone explain second solution in more details?Thanks!

link

answered 22 Aug '17, 14:45

math_wizard's gravatar image

3★math_wizard
11
accept rate: 0%

(22 Aug '17, 23:10) hloya_ygrt4★
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:

×1,768
×1,359
×733
×138
×31
×1

question asked: 20 Aug '17, 20:34

question was seen: 1,073 times

last updated: 22 Aug '17, 23:10