TREDIFF - Editorial

editorial
, , , ,
64

Thanks a lot :slight_smile:. That works, it never really gave a TLE problem to me in any graph problem, will take care of doing that.

1 Like
65

I am adding u to v and v to u in the adjacency list since it is undirected. Didn’t get you.

66

Ohhh! The problem is when you are converting path string to values. When the path contains nodes whose indices are more than a single digit, your conversion algorithm converts it incorrectly as it is considering one character at a time. Consider this test case:
1
11 1
1 2 4 7 11 16 22 29 37 46 56
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
10 11

Your program will find path as: PATH = 910
And so the values array will have the values: [46, 2, 1] instead of [46, 56].

1 Like
67

here is my solution in pyhton 3 my Solution
my time complexity is O(100) per query but still i am getting TLE for second type of tc.
is it because, i am using python or am i doing something inefficient??
please help.

68

Refer to this blog

We have to exclude all nodes which appears two times in the given range.

1 Like
69

Just change your compare function, it will pass

bool compare(Query x, Query y)

{

    if (x.L / blk_sz == y.L / blk_sz)

        return ((x.L/blk_sz)&1)?(x.R<y.R):(x.R>y.R);

    return x.L / blk_sz < y.L / blk_sz;;

}

https://cp-algorithms.com/data_structures/sqrt_decomposition.html#toc-tgt-7

2 Likes
71

Oh yes!! Thank you brother. What a blunder. Thanks for pointing out. Thanks a lot.

72

Hey, I did that.
Can you once take a look at my code, its getting tle. It’s moreover doing the same as yours.
My Code

73

I replaced my compare function with this one but still it didn’t pass. Code

74

I used LCA with the binary lifting technique to find number of nodes in the path, but I do not know I am getting WA. Can anyone help me ? CodeChef: Practical coding for everyone

75

Code :sweat_smile:
I just removed #define int long long int in this

1 Like
76

BLOCK_SIZE = sqrt(2 * Q);
change this to
BLOCK_SIZE = sqrt(2 * N);
But it still getting TLE idk why

1 Like
77

Oh! thanks. :sweat_smile:
Well, the time limit for MO’s was too tight.

C++14 gives TLE but passes with C++17.

1 Like
78

Can anyone tag similar problems like this from other sources like cf,spoj etc?
Thanks in advance :blush:

79

Problems on LCA:
SPOJ
SPOJ
SPOJ
SPOJ
SPOJ
SPOJ
Codechef
Codechef

6 Likes
80

My AC solution ( here ) for A_i =100.
I have used binary lifting to find distance and then naive approach for finding the minimum difference. Any tip on how to solve for A_i = 10^6.

Thanks for mentioning a new topic - Pigeonhole Principle

81

Do anyone know any source to learn implementation of path between nodes? Im just unable to find it anywhere. Just found many places saying DFS and BFS. Thanks in advance

82
1 Like
83

try Code NCode graph tutorials… they are the best.

1 Like
84

Can somebody help me, I’ve used depth and parent array (O(N) for preprocessing and then comparing depths of given nodes per query) to calculate the path between 2 nodes in tree. I didn’t use LCA using binary lifting. I also used frequency array for maxA condition as described in tutorial, but still getting TLE in both subtasks.

Here’s my Solution