But according to the editorial this type of solution should be able to get AC in subtask 1 of the problem. I am not even getting AC in that.
Here’s the first few lines from editorial-
"Let’s solve this problem naively. For each query, we shall try to move on the path from uu to vv and add all values to set and then compute the answer. We can see that each query can take O(N) time in the worst case (Linear tree). This solution would be sufficient for subtask 1,"
def printPath(stack):
for i in range(len(stack) - 1):
print(stack[i], end = " -> ")
print(stack[-1])
An utility function to do
DFS of graph recursively
from a given vertex x.
def DFS(vis, x, y, stack):
stack.append(x)
if (x == y):
# print the path and return on
# reaching the destination node
printPath(stack)
return
vis[x] = True
# A flag variable to keep track
# if backtracking is taking place
flag = 0
if (len(v[x]) > 0):
for j in v[x]:
# if the node is not visited
if (vis[j] == False):
DFS(vis, j, y, stack)
flag = 1
if (flag == 0):
# If backtracking is taking
# place then pop
del stack[-1]
A utility function to initialise
visited for the node and call
DFS function for a given vertex x.
def DFSCall(x, y, n, stack):
# visited array
vis = [0 for i in range(n + 1)]
#memset(vis, false, sizeof(vis))
# DFS function call
DFS(vis, x, y, stack)
@ankit_ap99
I found a way to get paths using precomputation.
I am still getting TLE on Subtask 2 (Submission)
Here’s the approach of the code.
Run a DFS over the tree and store parents and depths for all nodes. - O(N)
Then for each query:
a. Input two nodes u and v.
b. Get depth(u) and depth(v).
c. Go to parent for the node with greater depth until depth(u) is equal to depth(v).
d. Then iterate untill LCA is reached, i.e. u = v.
Check if path length > 100:
if yes → print 0.
Else → find min(|A_x - A_y|) in O(maxA).
Yes, finding nodes in path is costing O(N). I’m trying to change it to O(maxA). Should I keep checking if len(path) > 100 after incrementing path every time?
Well done @ameybhavsar you are 99% close. See here comes the observation part of the question. The values of A_i ranges from 1 to 100.
So maintain a frequency array for each number form 1 to 100 and check is a number repeats itself on the path from node u to LCA. In case any number repeats itself print 0, otherwise do the same thing on the path from node v to LCA. If again no values repeat itself use naive approach to find the minimum difference.
You can have a look on my solution ( here ) as you too implemented the same idea which I did. All the best.
Hey @taran_1407 i have to tell you that your editorials are really good. On top of that i am seeing that your implementations are really clean. Easy to go through them understand them. You are doing amazing work keep it up bro!!
I used the approach specified in this editorial. My complexity should be O(N + Q*100) and it should be able to pass the 2nd sub task. But I’m getting TLE. Can anyone tell me why I’m getting TLE? Code:CodeChef: Practical coding for everyone