TREDIFF - Editorial

editorial
, , , ,
46

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

47

Can someone help me debug my solution. Can’t figure out what’s wrong

48

Can you retry, after inserting:

 adj.clear();

before the line:

 adj.resize(n + 1);

?

2 Likes
49

thnx bro for this awesome self explanatory code.

51

got it. Reset your global variables for each testcase. I am noob

52

Galaxy Brain: Don’t use global variables, ever :slight_smile:

4 Likes
53

Can someone tell what am i doing wrong ?

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

54

The other option was to pass all the arrays as inputs to functions. Code looks much cleaner this way. Does introduce weird bugs though if not careful.

1 Like
55

Galaxy Brain 2: instead of having a bunch of separate arrays, just have a Node struct with parent, neighbours, visited, depth etc member variables :slight_smile:

5 Likes
56

Hey,
your ac code.

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

changed cnt to 101, and moved if(x==y)…

57

ok got it thanks.

58

Nice explanation. Thanks! Can you share the code for the bonus part?

59

I think test cases were weak. My O(N sqrt(N)) solution passed.

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

1 Like
60

Wow, you solved with mo algo.
Can you explain the part in your code of using frequency array and visited. What both of them does exactly while you move pointers.

61

Basically he is storing the frequency of elements as they appear in range. Then iterating it till 100 to find the minimum absolute difference.

1 Like
62

I also tried using MO’s algo but it’s giving TLE for second subtask.
Well I know that it was quite difficult passing the solution using MO’s.
Help me with optimization @choudhary463.

Code Link

63

graph was supposed to be undirected.

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