Join Us
Loading Similar Posts
Entering edit mode
Average CTC: 18lpa
Company: Product based
Roles: Software Engineers
Link: PhonePe Software Engineering position
Question 1
Click here to Practice
Submit Problem to OJ
Nuclear Nadal is the chief f Nuclear scientist of Wadiya. Aladeen has an annoying habit of imposing his will on scientific calculations done by Nadal. One day Nadal was using trees to solve some problem. Aladeen walked in and asked him to introduce an extra edge in the tree which would help solve the problem. This time Nadal decided to give him a tree problem with an extra edge.
The problem is given a tree with n vertices and n-1 edges. Aladeen has to answer q queries of the following type
x y a b k
In this query, an edge is added between node x and node y. Aladeen needs to find out whether there exists a path from node a to b with exactly k edges between them. A path can contain the same vertices and edges multiple times.
All the queries are independent of each other ie the edge added in a query is invalidated in the queries following it.
Input Format
The first line has an integer n - the number of vertices in the tree.
Then follow n-1 lines having two integers a and b ( 1 <= a, b <= n ), implying an edge a and b.
The next line has an integer q - the number of queries Nadal wants to ask.
Next q lines contain x, y, a, b, k.
Constraints
1<=n<=100000
1<=q<=100000
1<=x,y,a,b<=n
1<=k<=10^9
Output Format
For each query print 'Aladeen' if it is possible to have a path with k length between a and b after adding the edge between x and y. If not print 'Aladin'.
Sample Input 0
3
1 2
2 3
1
1 3 1 2 6
Sample Output 0
Aladeen
Question 2
Click here to Practice
Submit Problem to OJ
We have a tree with N vertices that is rooted. The vertices are numbered from 1 to N. 1 is the root node of the tree.
Vertices Ai and Bi are connected by the i-th edge.
An integer Xi is inscribed on vertex i.
We ask you Q queries. Answer each of the i-th query using the pair of integers (Vi,Ki).
Find the Ki-th biggest value of the numbers printed on the vertices in the subtree rooted at Vertex Vi.
Input Format
N Q
X1.......Xn
A1 B1 . . . . A[n-1] B[n-1]
V1 K1 . . . . Vq Kq
Constraints
2<=N<=100000
0<=Xi<=10^9
1<=Ai,Bi<=N
1<=Q<=10^5
1<=Vi<=N
1<=Ki<=20
The given graph is a tree.
The subtree rooted at vertex Vi has Ki or more vertices.
All values in input are integers.
Output Format
Print Q lines. The i-th lines should contain the response to the i-th query.
Sample Input 0
5 2
1 2 3 4 5
1 4
2 1
2 5
3 2
1 2
2 1
Output Format
4
5
Explanation 0
For the 1st query the vertices in the subtree rooted at Vertex 1 are Vertices 1, 2, 3, 4 and 5, so print the second largest value of the numbers written on these vertices, 4.
For 2nd query the vertices in the subtree rooted at Vertex 2 are Vertices 2, 3 and 5, so print the 1st largest value of the numbers written on these vertices 5.
Bonus Question 3: Interview Round
There are seats numbered from 1 to N placed in a row. You are given a list of integers empty spaces and a list of occupied spaces both between 1 to N. You are given M queries. In each query, you need to allocate a seat to a new person such that the distance between him and closest person to him is maximized.
Constraints
1<=N<=10^7
1<=M<=10^7
M
Entering edit mode
Solution to Problem 2
Analysis
We can note that the constraints on K are small, Hence we can first preprocess all of the K largest elements in the subtree of each node and then answer the queries. Lets start the preprocessing from the leaves. For a vertex i, suppose that the K largest elements have already been found for all children j1,j2,…,jm of i. Then, we can simply create an array containing the elements from the children and sort the resultant array at once, then the required elements for the current node i is an array consisting of the K largest values of the sorted array. Hence, we can precompute the K largest elements for all vertices in a total of ∑ O(miKlog(miK)) = O(NKlog(NK)) time and O(N*K) space.
PseudoCode
pre = [MAXN][]
dfs(node,parent): //dfs to precompute the k largest elements in subtree of every node
pre[node].append(value[node])
for child in adj[node]:
if(child!=par): //append the values precomputed for the children
dfs(child,node)
for val in pre[child]:
ans[node].append(val)
pre[node].sort(reverse=true) //sort the values
pre[node] = pre[node][0:MAXK] //remove everything except the K largest elements
solve(adj, queries):
dfs(1,-1) //first preprocess the K largest elements for each node
ans = []
for query in queries: //we can then answer each query in O(1)
ans.append(pre[query.node][query.k])
return ans
Entering edit mode
Q1)Analysis
As given in question that we could travel any edge or vertices multiple times so,
1>Let's suppose if we travel from A to B in distance d then we could also travel from A to B in distance {d+2 , d+4...}
Reason : if we travel from A --------- > P ----- Q ------> B (where P and Q has a direct edge and distance from A to B = d) then we could travel from A -----> B with distance of d+2 also by travelling P-----Q two times . Similarly we could travel other distances too.
Conclusion : IF we want to travel from A to B with distance K then we need to check whether minimum distance between A and B of same parity as that of K is atmost K or not because if distance is not of same parity we could not achieve K distance and if the minimum distance between A and B of same parity as that of K is greater than K than it's obvious that we could not achieve lesser distance(as it is already the minimum).
2>Hence our main task is to check for the minimum distance between A and B that is of same parity as K is atmost K or not.
Solution
If we got a query of adding an edge between X and Y. and we need to check whether distance from A to B exactly equal to K exists or not.
Let's check for minimum distance of same parity as that of K. Let's represent D(A,B) as the shortest distance between A and B not considering newly added edge.
Now here we have 2 options
1>Either take the newly constructed edge X----Y into the consideration
2>Not considering the edge X-----Y.
For second option the distance between A and B when not considering the edge X----Y is simply D(A,B) and represent it as D1
For first option
1>either we could go from A to X then X to Y then Y to B with total distance of D(A,X)+1+D(Y,B) represent it as D2
2>or we could go from A to Y then Y to X then X to B with total distance of D(A,Y)+1+D(X,B) represent it as D3 .
Therefore for a given K we need to check that out of {D1,D2,D3} having same parity as that of K is atmost K or not.(like if D1 is having same parity as that of K then we need to check D1 is < = K or not)
Here D(A,B) can be calculated by rooting the tree at any node and then finding the distance from A-->LCA(A,B) + LCA(A,B)-->B
where A-->LCA(A,B) is simply distance from root-->A - distance from root-->LCA(A,B) similarly for LCA(A,B)-->B
Hence D(A,B) is (distance from root-->A) + (distance from root-->B) - 2*(distance from root-->LCA(A,B)) and (distance from root-->Q) is simply the level of the node Q with respect to root.
LCA(A,B) can be calculated by precomputing the ancestors using Binary Lifting and then find the lowest common ancestors either by doing binary search or by lifting the nodes upto same level until and unless they become same.
Entering edit mode
1
/ \
2 3
/ \ / \
4 5---6 7
Let the above be the tree where edge has been added between (5,6)
for the query : [5,6,4,7,k]
{UPDATE} : I initially ignored the part where we can travel an edge multiple times.
-> Observation : If we can travel from node A to node B with a distance K , then we can also travel in {K+2 , K+4 . . . }
-> The above observation can be achieved by oscillating between two nodes which add up a cost 2*oscillations
Lets say that we have a function dist(a,b) which returns the distance
between node a and b before adding the edge.
The following possibilities for D are :
1. Take path ignoring the newly added edge
-> D = dist(4,7)
2. Take path utilizing the newly added edge
-> D = dist(4,5)+1+dist(6,7)
-> D = dist(4,6)+1+dist(5,7)
if D <= k and (D-k)%2 == 0 , then return TRUE
Hence , the above can be generalized as :-
-> D = dist(x,y)
-> D = dist(x,a)+1+(b,y)
-> D = dist(x,b)+1+dist(a,y)
Now , if D <= k and (D-K)%2 == 0 then return TRUE ( D should have same parity as K )
Function dist(a,b) can be made using LCA [binary lifting / sparse table]
-> We pre-process the 2^kth ancestor for each node.
-> We use this to find LCA(a,b) in logn
-> Run a DFS and pre-process the depth for each node.
-> Let LCA(a,b) = c , then dist(a,b) = depth[a] + depth[b] - 2*depth[c]
Time complexity:
O(Nlogn) for pre-processing 2^kth ancestors for each node.
O(logn) for each query. ( calling LCA function)
