tag:blogger.com,1999:blog-4115025577315673827.post1548453980604887331..comments2020-05-25T13:34:36.365+05:30Comments on CSE Blog - quant, math, computer science puzzles: Threaded PinsPratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-4115025577315673827.post-73709978340488050482010-01-07T01:07:30.575+05:302010-01-07T01:07:30.575+05:30@Suarabh.. Thanx for the answer.. Interesting poin...@Suarabh.. Thanx for the answer.. Interesting point raised in your second comment.. I was confused.. @Giridhar Thanx for the proof and the awesome explanation @Pandeyji.. Nice solution..Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-79548547886217506232010-01-05T16:35:06.442+05:302010-01-05T16:35:06.442+05:30Below Proof is in the same spirit as of 'drunk...Below Proof is in the same spirit as of 'drunksaint'.<br /><br />Observtions :<br />1)All cycles are disjoint<br />2)All cycles are of same size ( by symmetry ).<br />Let, <br />N be number of Pins, numbered 0 ..(N-1) <br />G be the Gap<br />C be number of Cycles.<br />and S be size of each cycle.<br /><br />From above observations, it follows that<br />N = C * S -- (1)<br />Now let us concentrate on the cycle that begin and end with Pin 0.<br />As we move in steps of G, S shud be SMALLEST integer obeying following equation :<br />(S * G )% N = 0 <br />This implies that S * G = LCM( N, G ) --(2)<br /><br />From (1) and (2) it follows that C =(N * G)/LCM( N,G ) = GCD( N,G ).<br /><br />For the follow up thing, <br />Pins corresponds to array elemets,<br />Gap corresponds to shift K ( amount by which we need to rotate array )<br />Hence, as we know the number of cycles which arise , and elements which belong to a given cycle, array can be rotated using N + GCD(N,K) Assignment operations.<br /><br />Just for sake of completeness, let me mention that there is another relatively inefficient O(1) solution for rotation problem ::<br />let array be A#B where A is of size K and B of size ( N - K ).<br />if we rotate whole array ( using SWAP operations )we get B^R#A^R ( concatenation of B reversed with A reversed )<br />Now we rotate parts individually, this gives us (B^R)^R#(A^R)^R = BA, as desired.<br />In this solution we are doing N SWAPS , whereas first solution requires just N + GCD(N,K) ASSIGNMENTS .Giridharhttps://www.blogger.com/profile/06086734346209959881noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-4345385548930672922010-01-05T12:11:47.584+05:302010-01-05T12:11:47.584+05:30y = # of pins
x = gap
#of threads = gcd (y,x)
br...y = # of pins<br />x = gap<br /><br />#of threads = gcd (y,x)<br /><br />break the cirlce into an infinite line<br />now keep up with the procedure<br />if gcd != 1, then some positions will never be visited, positions visited would be multiples of gcd (y,x)<br />hence the result.Gold and Ironhttps://www.blogger.com/profile/06432880847456391263noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-53158442737729058002010-01-05T00:52:32.848+05:302010-01-05T00:52:32.848+05:30:-/:-/drunksainthttps://www.blogger.com/profile/05334942021615777054noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-37738124853629935872010-01-05T00:51:25.574+05:302010-01-05T00:51:25.574+05:30create ring with extra slot. shift 1 by 1 till u g...create ring with extra slot. shift 1 by 1 till u get there.drunksainthttps://www.blogger.com/profile/05334942021615777054noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-84379507300428706382010-01-05T00:46:00.437+05:302010-01-05T00:46:00.437+05:30ab/lcmab/lcmdrunksainthttps://www.blogger.com/profile/05334942021615777054noreply@blogger.com