CLOVER - Editorial

clover
dfs
editorial
medium-hard
segment-tree

#1

PROBLEM LINKS:

Practice

Setter : Vatsal Gupta##

Tester : Shubham Grover##

DIFFICULTY:

Medium-Hard

PREREQUISITES:

Depth First Search,Segment Trees

EXPLANATION:

Firstly, here we use the thing that if we dfs a tree and we keep a stack such that

we push a element to the stack when we arrive at it and pop the element from the

stack when we depart from it, therefore when we depart from node x the

elements on the stack are the elements which lie on the path from root to x

(reader’s can easily prove this).

Here we use the same thing, we maintain an array (arr) of the maximum value in

the nodes and each index of this array works like the stack discussed above (i.e.

Suppose a node of value v is arrived we push the arrival time of this node to

arr[v] and next, suppose a node of value v is departed we pop the arrival time of

this node from arr[v]).

Now, all we need is the closest vertex with value greater than some value (x). For

that we have an array (arr2) of the maximum value in the nodes such that arr2*

stores the top of the stack at position i in “arr” array described above.

Now,we simply need the maximum value in the range (x,maximum

value in the nodes) which is actually the arrival time of the vertex closest to the

given vertex and has a value greater than the given value,

For this we apply segment tree to find the maximum value in a range and also we

apply point updates in the segment tree every time we arrive or depart a vertex

in the dfs run.

Since we can store the answer for each vertex beforehand in the dfs run we can

simply answer the queries in O(1) by maintaining an array such that the array*

stores the answer for the vertex i and update this array during the dfs run.

Total Complexity : O(Nlog(Max value)+Q)

SETTER’S SOLUTION:

Can be found here


#2

My code is being showed as a wrong answer even though it is getting executed successfully with the sample input . Please tell me where am I making the mistake . Thank you .

https://www.codechef.com/viewsolution/11780190