ARCTR - Editorial

Problem Link

Practice

Contest

Author: Igor Barenblat

Tester: Misha Chorniy

Editorialist: Bhuvnesh Jain

Difficulty

MEDIUM-HARD

Prerequisites

Dynamic Convex-Hull Trick, Heavy-Light Decomposition

Problem

You are given a tree with N nodes. M speedsters travel on the tree. The i^{th} speedster starts at time t_i from vertex u_i and travels towards v_i at a constant speed of s_i. For every vertex, we need to find the first time, any speedster visited it. In case, it was not visited by any speedster, report the answer as -1.

Explanation

For simplicity, let us assume that the tree is rooted at node 1 and the depth of all vertices from the root is calculated. The depth is basically the distance of the vertex from the root of the tree i.e. 1.

Let us first write the equation for time taken by speedster i reach a vertex x. If the vertex doesn’t lie on the path from u_i to v_i then it is not visited by speedster i, or the time taken is INFINITY (a large constant). For all the other vertices on the directed path from u_i to v_i, the time taken is given by:

\text{Time taken} = t_i + \frac{\text{Distance from vertex }u_i}{s_i}
\text{Distance between x and y} = \text{Depth[x]} + \text{Depth[y]} - 2 * \text{Depth[lca(x, y)]}

where lca(x, y) is the lowest common ancestor of vertices x and y.

We can now modify the equation for the time taken to reach any vertex on the path from u_i to v_i as follows:

Let the lowest common ancestor of u_i and v_i be lca. Calculate the final time at which we reach vertex v_i. Let us denote this by t_f. We now split the path from u_i to v_i into 2 parts: one from u_i to lca and from lca to v_i. NIte that these paths are directed. The image below shows how to calculate the time at any vertex x and y on the 2 different paths.

From the above figure, for a node x on path from u_i to lca, the time to reach it is:

\text{Time taken to reach x} = t_i + \frac{(Depth[u] - Depth[x])}{s_i} = \big(t_i + \frac{Depth[u]}{s_i}\big) - \frac{1}{s_i} * Depth[x]

Similarly, for a node y on path from lca to v_i, the time to reach it is:

\text{Time taken to reach y} = t_f - \frac{(Depth[v] - Depth[y])}{s_i} = \big(t_f - \frac{Depth[v]}{s_i}\big) - \frac{1}{s_i} * Depth[y]

If we observe carefully, both the above equations look the form Y = MX + C, where the first bracket part is C, time to be calculated is Y, \frac{1}{s_i} is the slope (M) and the depth of the node is X.

The problem asks us to find minimum time at which every node is visited by any speedster, and the above equations clearly show that time to reach it only depends on the depth of the node and pair (constant, slope) which is known beforehand for every speedster. Thus, this indicates the final solution will use the Dynamic convex-hull trick (Dynamic variant as the slopes are not guaranteed to be in increasing/decreasing order). If you don’t know about it or its use case, you can read it here

So, let us first try to solve a simple version of the problem where the tree is a bamboo(a straight path). This basically rules out the tree of the problem and reduces it to updates and queries of the following form on an array:

  1. Update: Add a line (M, C) denoting Y = MX + C to every index in range [l, r].

  2. Query: Find the minimum value at any index l for a given value of X = w.

We have range updates and point queries. So, we will use segment trees for the solution. In each node of the segment tree, we will keep the lines (represented by (M, C)) and for querying, we will just use the convex-hull trick to evaluate the minimum at node efficiently. Below is the pseudo-code for the segment-tree:


	def init(t, i, j):
		if i == j:
			seg[t].clear()		# remove all the lines
			return
		mid = (i+j)/2
		init(2*t, i, mid)
		init(2*t, mid+1, j)

	def update(t, i, j, l, r, M, C):
		if i > r or j < l:
			return
		if l <= i and j <= r:
			# within required range
			seg[t].add_line({M, C})
			return
		mid = (i+j)/2
		update(2*t, i, mid, l, r, M, C)
		update(2*t+1, mid+1, j, l, r, M, C)

	def query(t, i, j, l, r, X):
		if l <= i and j <= r:
			return seg[t].evaluate_minimum(X)
		mid = (i+j)/2
		if i <= mid:
			if j <= mid:
				return query(2*t, i, mid, l, r, X)
			else:
				a = query(2*t, i, mid, l, r, X)
				b = query(2*t+1, mid+1, j, l, r, X)
				return min(a, b)
		else:
			return query(2*t+1, mid+1, j, l, r, X)


The time complexity of the above operations on segment tree is O(\log{N} * \log{M}) for both update and query. This is because each update and query will visit at most O(\log{N}) nodes and operation on every node (addition of a line or querying for minimum) is O(\log{M}). For a good reference code to the Dynamic convex hull, you can look up this.

Back to the tree problem. We see that we can easily handle queries on an array and the queries on the tree as basically those on a path. Voila, we can simply use Heavy light Decomposition or any other data structure you are suitable with (Euler Path or Centroid Decomposition). Thus, we efficiently solve the problem.

The overall time-complexity of the above approach using heavy-light decomposition will be O({\log}^{2}{N} * \log{M}) per update and query as it divides the path between the vertices u and v into O(\log{N}) path each of which is a straight path and can be solved using the segment tree mentioned above.

You can look at the author’s implementation for more details.

Feel free to share your approach, if it was somewhat different.

Time Complexity

O((N + M) * {\log}^{2}{N} * \log{M})

Space Complexity

O(N + M)

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

2 Likes

My logic is almost the same instead I used sqrt dec. I don’t know how but it did pass xD, though i had already thought of using segment trees in case it TLED. Glad it didn’t :D.

If anyone wants a sqrt dec based solution you can look up my implementation here .

We can do this using basic union find and greedy

If anyone wants to know my solution,tell me,i’ll be happy to share it.

Edit:
My idea was to process vertices in increasing orders of smallest time of arrival of speedster.

So basically i maintain a min priority queue of form (time,Starting Vertex,Destination Vertex,velocity)

So for each speedster,put (t_i,u_i,v_i,s_i) in priority queue

Now at each step do the following:

$1)$Remove the minimum time element from priority queue.

$2)$lets say it is (t,u,v,s)

So ans[u]=t
and we can say that processed[u]=true

$3)$Now go one step further along the path from u to v,(like for u->w->v,next vertex along path from u to v is w),let this vertex be w,so insert(t+dist(u,w)/s,w,v,s) in priority queue.

$4)$Repeat

Now if u see in step 3,there’s no point in visiting vertex w if processed[w]=true,

like lets say we have a chain like this,

a->b->c->d->e

And processed[b]=processed[c]=true

Also since a has been processed currently processed[a]=true

And our current processed vertex is a,So for step 3) its not worth to go to b since its ans wont change,so it would better if we could directly jump to d,and insert d into priority queue.

How do we do that?

Lets define components,we basically group all vertices which are adjacent to each other and which have been processed into 1 group

for the above case,we could say (a,b,c) belong to component no.1,d belongs to component No.2,e belongs to component No.3

So it becomes more like

(\textbf{a->b->c})_1->(d)_2->(e)_3

(here bold indicates they are the processed vertices whose answer has been found and cannot be improved)

Now how do we find that we have to go to d?

U can use binary lifting sort of thing(Sorry if i am saying the name wrong,i just remember the method)

lets say u have a vertex u,and vertex v

Lets root the tree at 1,

we want to go to next non-processed along the path from u to v ,

first case ,u is below v(and the path is bamboo)

So do this

curr=u

while True:

$1)$iterate i from 20 to 1,

See if 2^i th parent of curr is in same component as curr,

if it is:

  curr=this parent 

  break

else

  continue

2) if curr value not changed,it means that u are at the end of the component of u,so its parent is actually what you want

eg: (a->b->c)_1->(d)_2->(e)_3

Imagine this upside down ,like a down ,e up ,wanna go from a to e

So 2^2 parent of a is e(not in same component),so continue,2^1 parent of a is c(same component break)

Now 2^1th parent of c is e(not same component so continue),2^0 th parent is d (not same component)

So parent of c is what we wanted(which is d here)

Second Case: u is above v(path is a bamboo)

This too can be handled similarly

Now if path doesnt form bamboo ,we can break it down like (u,lca(u,v)),(lca(u,v),v)

My solution: CodeChef: Practical coding for everyone

4 Likes

I used Heavy light decomposition plus convex hull for each chain, splitting the chain in case cahin exceed a particular size.

Kept getting WA on 1 file in last sub-task. here

1 Like

@taran_1407 @algmyr I too was getting the same verdict initially when I was using doubles in Convex Hull. On changing it to use longs I got AC.(Here line Y=MX+C has M=\frac{1}{s_i} and C=\frac{B}{s_i} where B is a long value. This line can also be written as \frac{1}{s_i}(X+B). Instead of calculating \frac{1}{s_i} and \frac{B}{s_i}. I had directly stored s_i and B and modified CHT to work with these long values instead). I suspect that WA on this case was due to floating point inaccuracy.(But I may be wrong as I also tried using the same code with long doubles in c++ but again got WA on this case). Can @admin provide us with this test case?Link to AC solution 18870510

1 Like

Author’s and Tester’s solutions, mentioned in the editorial give TLE on subtasks 2,3 and 4.

Links

Done. Removed the other one.

Hey i am interested. Please do write an editorial on that. It took me a lot of time to code up 500+ lines and for sometime I did try thinking an easier alternative but didn’t get any. Would be glad if you wrote and editorial :smiley:

I also kept getting WA for that particular case. Very curious as to why. Is there any way to get any insight in what actually went wrong? Is it at all possible to see that test case, @admin?

You sure you exactly copied the code? Perhaps wrong solutions got linked. I will talk to @mgch and see what I can do.

@anay1 @vijju123 updated the links.

Thank you @likecs :slight_smile: