TREDIFF - Editorial

editorial
, , , ,
85

Can anyone please help me in telling where am I getting wrong in my LCA code(using Sparse Matrix)
due to which I am getting TLE on subtask 1 itself!..Its the first time I am trying this approach so I think I am having some implementation issues, but I am unable to figure them out!

Here is my code link: CodeChef: Practical coding for everyone

86

Could you please help me find this bug ? I intend to solve this problem to learn the mo’s algorithm in a better way . Pigeon-hole’s principle was definitely a show winner .
https://www.codechef.com/viewsolution/33527299

87

i think its giving wrong output. Just add edges as per the TREDIFF problem and check output for 6,5. its weird

88

Thanks!!

89

Pigeonhole is a very basic thing in maths/cp, though it didn’t click me during the contest (-_-;). Nice editorial. Nice problem. But what if A_i is much greater? Can anyone tag such problem or editorial right here?

1 Like
90

The code in java does not work without the fast reader. I usually use fastreader but i forgot to use this time around…can anyone tell me from where can we detect that the i/o is causing the problem?

91

I am using the same approach but still getting TLE.
Please help me to fix it CodeChef: Practical coding for everyone

Thanks

92

Attach your code please.

1 Like
93

Can any1 tell whats wrong with my code? I use simple DFS and store path in a vector. Then I calculate the minimum among them . It should pass Subtask 1 .But its giving WA
https://www.codechef.com/viewsolution/33513447

94

@vivek_1998299 @taran_1407
Hey,
Can anyone tell why is it that declaring graph globally creates a TLE in both the subtasks.
(Code and logic used is same as editorial)
CodeChef: Practical coding for everyone (giving TLE)

CodeChef: Practical coding for everyone (accepted)

Only difference in code is that graph “g” and vector used to store values of nodes “v” is defined globally.

95

Can anyone tell whats wrong with my code. i am using lca approach using depth and parent vector and then finding min difference b/w them

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

96

In the tester’s solution he is using sparse tree implementation,but it is returning a pair.
What does that pair contains? @radoslav192

97

The first number in the pair is the depth of the vertex in the dfs order, while the second one is its id (not that each vertex appears multiple times in the order).

98

ohk,so you have modified sparse table implementation for using it in graphs.

99

Can anyone please help, my solution handles every query in 100 operations. I did this after reading the editorial. It gives TLE on subtask 2.

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

Any suggestions are also welcomed.

100

Kindly help. I am getting TLE for subtask 2.
Here’s my approach:

  1. For each query, find simple path from node A to node B using DFS.
  2. If length(path) > 100 print 0.
  3. Else use map to find min(A_x - A_y).
    Link to submission.
101

@witcher98 in worst case your solved function would run for O(N).
The worst case for your code is when the nodes of the tree from a chain and you have to go from the leaf node to the root. Thus making your time consumption O(Q.N)

102

@ameybhavsar a single dfs run takes O(N). So running DFS for each query would lead the time complexity to O(Q*N). That’s where your code failed.
Tip: In-case the nodes and paths of tree are static try building an intuition to solve problem by finding LCA, most of the time it really helps during short contests.

103

why i am getting tle on 2 subtask.My code is same as setter’s code only the dfs function is implemented a bit differently.Can anyone tell me.Thanks in advance.

104

you are not deleting the element of previous test case that’s why you are getting tle.