TREDIFF - Editorial

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

125

@virtuality Although you are keeping track of repeated node values, you should also keep track of the number of nodes (call that len) in the path.
Then, keep incrementing len in the loop on line 49, whenever you add a node to the path.
After line 58, inside the loop, check whether len > 100, if yes then you can print 0 as the answer due to pigeonhole principle.

126

Keep coding :+1:

1 Like
127

No need for that because when len becomes > 100, automatically by pigeon hole principle I’ll get a repeated value which my code will detect.