PROBLEM LINK:
Div 1
Div 2
Practice
Author: Full name
Tester: Full name
Editorialist: Oleksandr Kulkov
DIFFICULTY:
MEDIUM
PREREQUISITES:
Disjoint Set Union
PROBLEM:
You’re given N gears. Gear i has A_i teeth. You have to process M queries of the types:
- Change A_X to C;
- Connect gears X and Y;
- Find speed of gear Y if X rotates with speed V;
Note
If gears i and j are connected and i rotates with speed V then j rotates with speed -V \cdot \tfrac{A_i}{A_j}. Also it is possible that gears are blocked, in this case you should output 0.
QUICK EXPLANATION:
First, maintain bipartite checks in online with dsu. Then to answer third query use formula:
V_Y = (-1)^{c_X+c_Y}\cdot V \cdot \dfrac{A_X}{A_Y}
Here c_X and c_Y are colors of vertices X and Y (either 0 or 1). If they don’t lie in same component or their component is blocked, output 0.
EXPLANATION:
Consider gears i and j in the same component. Let i=v_1,\dots,v_k=j be arbitrary path from i to j. Then:
V_k=-V_{k-1} \cdot \dfrac{A_{v_{k-1}}}{A_{j}}=V_{k-2} \cdot \dfrac{A_{v_{k-2}}}{A_{j}}=(-1)^{k-1}\cdot V_1\cdot \dfrac{A_i}{A_{j}}
Which is direct formula to answer third query. You only have to know parity of k-1 to answer it. When can this parity depend on path we choose? If and only if there are pathes of different parity, which means that there is a cycle of odd length in the graph. Indeed, we can see that gears connected component will be blocked if and only if it’s not bipartite. Thus to solve a problem we have to maintain bipartite checks in online with queries of adding new edges. This can be done in straight-forward manner with disjoint set union through merging sets.
Let’s assign for each vertex some random color. Now when we add new edge if it connects different connected components, we will go through smallest of them if necessary (if kept colors are same for endpoints) and reverse color of each vertex in it. Otherwise we just check that the edge connects vertices of different colors and if no, we will say that this component is blocked from now on. This will give us solution with final complexity of O(n\log n) time and memory usage.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
RELATED PROBLEMS:
Nice and clear explanation. I had done same.
In case some one is not able to understand something do look at this:
For the query of type 3, speed depends only on u and v.
And the sign of answer depends on whether it is connected to other vertex by odd length or even length path. Because in the connected gear system there will be alternate +ve and -ve signs of answer from given vertex.
In short you have to color the graph in two colors.
I had maintained graph and used disjoint set data structure and array for gear teeth and when you have to change the teeth value you can just change value of array.
Maintain different color for each gear and when you connect two gears just change the color of other gear.
Note: Gears will be blocked when there is odd length cycle.
for query of type 3,
Suppose you have two components in which each components may contain several connected gears.
When query of type 2 occurs and you have to connect these two components then use disjoint set data structure and change the color of smaller component according to bigger components For e.g you had used colors 2,3 for 1st component and 4,5 for other component then change color of second component (if 2nd is smaller component).
while connecting two vertices from same component just check if one of them is blocked or by connecting these vertices will there be any odd length cycle ? i.e do they have same color ? because now you cant connect them if they have same color and after connecting they must have different colors hence all the vertices from component will be blocked.
Last while answering type 3 you can check color of both vertices if they are same color : use + sign answer else negative answer.
My solution https://www.codechef.com/viewsolution/19233845
The link to the tester’s solution is broken. Please fix it.
1 Like
it had some weak test cases as well,because I see that the brute force implementation (earlier applied by me with an order O(n^2)) passes and gives AC. One can check my solution in my submissions as well!
1 Like
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
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…
what data structure do we use for this
Disjoint Set Data Structure but Basically you would require trick of merging two sets. i.e DSU trick
@aa6565
You are using wrong formula for gcd. Use inbuilt __gcd(a,b) function.