Can someone help me with the solution of gears? I used bfs and dfs in this question but got TLE. If this question use DSU then can you explain me how I can implement it
Refer to the link I gave under problem discussion thread for DSU. Use that.
HERE is my c++ code ( its neat enough to understand)
You can refer DSU is you don’t know it from HERE
This tutorial is very good and easy to understand…
You need to use DSU for checking if two elements are connected or not in O(log(n))
After that everything is just logic…
I can explain my full solution here but I think you try it once on your own and ping me back if still can’t get it…
HINT for Logic part :-
Click to view
Assign sign (i.e. 0 or 1) to alternate nodes while connecting them…
1) It helps in detecting blocking in O(1)…
How ? :-
Click to view
If you get a query having assigned same sign by you and the nodes are connected from some other path already (i.e. 0-0 or 1-1 ) then it blocks whole connected structure (make “bool isBlocked” of root of that structure TRUE…
2) Checking if two gears will move in opposite direction or not in O(1)
How? :-
Click to view
In query three u can check direction of gear (+ or -) by checking if variable sign of both nodes are same or not
MAIN ISSUE:-
query type 2 (connect them):
3-4
Now , here let’s assume u assigned “sign1” to 3 and “sign0” to 4
5-6
Here you assigned “sign1” to 5 and “sign0” to 6
3-5
and after that u get query 3-5 then you need to invert sign of all nodes in one of them to connect them properly (this prob is when u get same sign query for connecting two separate structures)
Hint for Soln of Main Issue O(logn):
Click to view
use “bool invert” of its root(before connecting) to invert a whole structure…
PS: you need to do sign^=invert(root) for each root a node have… as a node can have log(n) roots at max( as discussed in DSU tutorial)… (we can modify find root function to check real sign)
Can be merged with findroot function to avoid extra computations…
Note :- My approach wont work with path compression ( why ? think yourself :D)
sorry @vijju I again commented before seeing you answer… I was typing since a long time so…
Comment is a comment and ans is an answer xD. Gone are those days when one would be upset over such trivial things @l_returns
1 Like
I solved this question with and without path compression, but I didn’t see much difference in execution time.
Can anyone explain to me why?
-
With path compression: https://www.codechef.com/viewsolution/19401887
-
Without path compression: https://www.codechef.com/viewsolution/19401750