×

# GEARS - Editorial

Author: Full name Tester: Full name Editorialist: Oleksandr Kulkov

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:

This question is marked "community wiki".

4★melfice
811737
accept rate: 0%

19.7k350498541

1

(17 Jul '18, 14:57)

 1 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 11●2 accept rate: 0%

# 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...

# 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.4k19
accept rate: 25%

## My solution and answer for "hints of the soln" link in case anyone is interested...

(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 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.

(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)
1

@vijju123 That makes it so much clearer. Thank you once again!

(18 Jul '18, 00:31)

You're welcome :)

(18 Jul '18, 00:42)

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...

(18 Jul '18, 11:12)
showing 5 of 10 show all
 0 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. answered 17 Jul '18, 14:38 5★cis_pie 105●5 accept rate: 9%
 0 What is parity? answered 18 Jul '18, 08:21 4★titin_ 13●3 accept rate: 0% Parity mean odd or even. (18 Jul '18, 08:49) tamiliit3★
 0 what data structure do we use for this answered 20 Jul '18, 16:53 3★araj1998 1 accept rate: 0% Disjoint Set Data Structure but Basically you would require trick of merging two sets. i.e DSU trick (20 Jul '18, 21:23) cis_pie5★
 0 @aa6565 You are using wrong formula for gcd. Use inbuilt __gcd(a,b) function. answered 21 Jul '18, 18:52 4★psycic03 0●1 accept rate: 0%
 0 What do the pair of vectors inside the groups array indicate? answered 25 Jul '18, 00:21 1●1 accept rate: 0%
 0 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 4★niteshx2 41●4 accept rate: 0%
 0 For this specific kind of disjoint set union , read this article https://cp-algorithms.com/data_structures/disjoint_set_union.html answered 24 Aug '18, 01:14 4★niteshx2 41●4 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,499
×2,559
×120

question asked: 17 Jul '18, 06:31

question was seen: 2,726 times

last updated: 03 Nov '18, 15:21