TREDIFF - Editorial

https://www.codechef.com/viewsolution/33512919
can you please look into my code …i used dfs and used freq count to calculate the minimum…but my solution is giving runtime!

Wow. I like the fact that how the brilliant.org is supported/ advertised by codechef

thanks

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

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

Can you retry, after inserting:

 adj.clear();

before the line:

 adj.resize(n + 1);

?

2 Likes

thnx bro for this awesome self explanatory code.

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

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

4 Likes

Can someone tell what am i doing wrong ?

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

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

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

Hey,
your ac code.

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

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

ok got it thanks.

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

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

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

1 Like

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.

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

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

graph was supposed to be undirected.