TREDIFF - Editorial

editorial
, , , ,
105

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,"

106

Python3 implementation of the above approach

v = [[] for i in range(100)]

An utility function to add an edge in an

undirected graph.

def addEdge(x, y):
v[x].append(y)
v[y].append(x)

A function to print the path between

the given pair of nodes.

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)

Driver Code

n = 10
stack = []

Vertex numbers should be from 1 to 9.

addEdge(1, 2)
addEdge(2, 3)
addEdge(2, 4)
addEdge(1, 5)
addEdge(5, 6)
DFSCall(5, 6, n, stack)

This code is contributed by Mohit Kumar

107

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

any test case in which my code is failing?

108

my subtask 1 solution passing test case but showing wa please help
https://www.codechef.com/viewsolution/33544664

109

I have used same approach but getting an TLE : CodeChef: Practical coding for everyone

110

Same here bro
https://www.codechef.com/viewsolution/33544664

111

What if there are 2 paths from node u and v?? How to overcome this?

112

I was also getting TLE. Changing from long long int to int works for me. Check if it also works for you.

113

I am getting WA for this question, please see [Official] May Lunchtime 2020 - Post-contest discussion - Live stream session - #11 by ganesh_6

114

bro u kept t=1 :rofl: :rofl: :rofl:

115

@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.

  1. Run a DFS over the tree and store parents and depths for all nodes. - O(N)
  2. 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.
  3. Check if path length > 100:
    if yes → print 0.
    Else → find min(|A_x - A_y|) in O(maxA).

Kindly help.

116

Suppose -
N=100000
1 2
2 3
3 4
…
…
…
…
N-1 N

and let node u=1 and v=N, then you will move up from v to u using the parent, and that will cost O(N) iterations per query.

117

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?

118

To find the distance between two nodes you can use the formula:

dist(a,b)=depth[u]+depth[v]-2*depth[lca(a,b)]

2 Likes
119

Bro, that’s part of my template :joy:. For questions, without test cases as input, I just comment out the line of (cin >> t) :slight_smile:

2 Likes
120

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.

1 Like
121

sry bro have u got that ?

122

I solved it dude. Thank you for all your efforts. :smiley:

1 Like
123

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!!

1 Like
124

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