A slightly optimised approach (maybe more useful when n is large)…
Time Complexity of reversing colour of each node will be linear in worst case ( O(n/2) i.e. O(n) )
We can use bool invert at each root of DSU instead of inverting every node individually…
This will reduce complexity of inverting to O(1)…
And for checking real sign we need to go through each of it’s parent roots (till root[i]==i) which will be O(log(n))
But we can merge this sign functionality with “findRoot()” function and thus more computations will be saved…
Note: You can’t merge it with “findroot()” if findroot uses path compression…
1 Like
what data structure do we use for this
@aa6565
You are using wrong formula for gcd. Use inbuilt __gcd(a,b) function.
What do the pair of vectors inside the groups array indicate?
I simply created a graph and ran BFS from the source to color the graph. If on coloring from source it did’nt get colored , it was disconnected . And color gave the info about the sign . Can Someone give me the tricky test cases where my code is failing ?
My solution : https://www.codechef.com/viewsolution/19229385
The link to the tester’s solution is broken. Please fix it.
1 Like
My solution and answer for “hints of the soln” link in case anyone is interested…
answer link : TLE IN Gears - #2 by l_returns - general - CodeChef Discuss
soln link : CodeChef: Practical coding for everyone
1 Like
The editorial’s solution is nlogn because of small to large merging and merging won’t result in n^2 time.
When I said its O(n^2) ???
I SAID O(n) or O(n/2) !!!
@l_returns - he meant that by small-to-large trick, SUMMING UP ALL QUERIES we can get merging done in O(QlogN) as each node is marked at most logN times. Your approach said time complexity to reverse each node can be linear which impresses that its a O(Q*N) solution.
@vijju123
IDK how to reply on codechef discuss sorry. Thank you so much for your reply on @i_returns ’ comment. I was thinking (and doing) the same thing during the contest but thought the complexity of the whole program would be O(Q*N) because I thought inversion of colours( with respect to bipartite) , would be O(N) in one inversion.
Now I can think how they can all sum up to give the logN factor and the overall complexity. Thank you :))
Should have implemented the logic anyway. :’(
Also how can I reply to a comment/reply and how can I upvote(or is it called giving karma here?)
Need 50 upvotes for comment xD. Commenters dont get upvotes- a good way to hide your contribution 
Do you realize the small to large trick?
What happens is that the smaller one is merged with larger set, and smaller set’s pairty is changed. Say smaller set’s size is a and larger set’s size is b.
Now, given a< b \implies a+a< a+b \implies a+b>2*a. This means after merging, new set is atleast 2 times size of smaller one. Hence, each node can be merged at most logN times worst case (as size must be 2 times larger)
@vijju123 That makes it so much clearer. Thank you once again!
1 Like
Thanks @vijju123 for replying…
I didn’t meant that over all will be O(n²) or O(n*q)…
By O(n) I meant that per query it would be size of smaller node…
And yes I agree O(Nlogn) is overall complexity…
Disjoint Set Data Structure but Basically you would require trick of merging two sets. i.e DSU trick