You are not logged in. Please login at www.codechef.com to post your questions!

×

GEARS - Editorial

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:

This question is marked "community wiki".

asked 17 Jul '18, 06:31

melfice's gravatar image

4★melfice
811737
accept rate: 0%

edited 17 Jul '18, 14:34

admin's gravatar image

0★admin ♦♦
19.7k350498541

1

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

(17 Jul '18, 14:57) akashbhalotia3★

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!

link

answered 17 Jul '18, 18:32

sharpowl_06's gravatar image

4★sharpowl_06
112
accept rate: 0%

edited 17 Jul '18, 18:34

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

link

answered 17 Jul '18, 21:01

l_returns's gravatar image

4★l_returns
1.4k19
accept rate: 25%

edited 17 Jul '18, 21:27

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

answer link : https://discuss.codechef.com/questions/131495/tle-in-gears/131504
soln link : https://www.codechef.com/viewsolution/19135163

(17 Jul '18, 21:04) l_returns4★

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) soham12346★

When I said its O(n^2) ?????

(17 Jul '18, 21:21) l_returns4★

I SAID O(n) or O(n/2) !!!

(17 Jul '18, 21:23) l_returns4★

@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 ♦♦4★

@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) iprakhar224★

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) vijju123 ♦♦4★
1

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

(18 Jul '18, 00:31) iprakhar224★

You're welcome :)

(18 Jul '18, 00:42) vijju123 ♦♦4★

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

(18 Jul '18, 11:12) l_returns4★
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

link

answered 17 Jul '18, 14:38

cis_pie's gravatar image

5★cis_pie
1055
accept rate: 9%

edited 17 Jul '18, 14:38

What is parity?

link

answered 18 Jul '18, 08:21

titin_'s gravatar image

4★titin_
133
accept rate: 0%

Parity mean odd or even.

(18 Jul '18, 08:49) tamiliit3★

what data structure do we use for this

link

answered 20 Jul '18, 16:53

araj1998's gravatar image

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★

@aa6565 You are using wrong formula for gcd. Use inbuilt __gcd(a,b) function.

link

answered 21 Jul '18, 18:52

psycic03's gravatar image

4★psycic03
01
accept rate: 0%

What do the pair of vectors inside the groups array indicate?

link

answered 25 Jul '18, 00:21

sparshkedia's gravatar image

5★sparshkedia
11
accept rate: 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

link

answered 23 Aug '18, 17:55

niteshx2's gravatar image

4★niteshx2
414
accept rate: 0%

For this specific kind of disjoint set union , read this article https://cp-algorithms.com/data_structures/disjoint_set_union.html

link

answered 24 Aug '18, 01:14

niteshx2's gravatar image

4★niteshx2
414
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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