PROBLEM LINK: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:
NoteIf 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_{k1} \cdot \dfrac{A_{v_{k1}}}{A_{j}}=V_{k2} \cdot \dfrac{A_{v_{k2}}}{A_{j}}=(1)^{k1}\cdot V_1\cdot \dfrac{A_i}{A_{j}}$$ Which is direct formula to answer third query. You only have to know parity of $k1$ 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 straightforward 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:
This question is marked "community wiki".
asked 17 Jul '18, 06:31

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! answered 17 Jul '18, 18:32

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... answered 17 Jul '18, 21:01
My solution and answer for "hints of the soln" link in case anyone is interested...answer link : https://discuss.codechef.com/questions/131495/tleingears/131504
(17 Jul '18, 21:04)
The editorial's solution is nlogn because of small to large merging and merging won't result in n^2 time.
(17 Jul '18, 21:15)
When I said its O(n^2) ?????
(17 Jul '18, 21:21)
I SAID O(n) or O(n/2) !!!
(17 Jul '18, 21:23)
@l_returns  he meant that by smalltolarge 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.
(17 Jul '18, 23:44)
@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?)
(18 Jul '18, 00:19)
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)
(18 Jul '18, 00:24)
You're welcome :)
(18 Jul '18, 00:42)
Thanks @vijju123 for replying....
(18 Jul '18, 11:12)
showing 5 of 10
show all

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 answered 17 Jul '18, 14:38

What is parity? answered 18 Jul '18, 08:21

What do the pair of vectors inside the groups array indicate? answered 25 Jul '18, 00:21

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 answered 23 Aug '18, 17:55

For this specific kind of disjoint set union , read this article https://cpalgorithms.com/data_structures/disjoint_set_union.html answered 24 Aug '18, 01:14

The link to the tester's solution is broken. Please fix it.