kitchent Floating point comparison is disastrous. Use algebraic comparison.
I followed the recommendation of others and looked up Stern-Brocot tree, Farey neighbours. However, even though I believe I've sufficiently implemented those approaches, it is still TLE #16-#20 in Python.
Farey neighbours seemed promising with an elegant expression like , but it somehow could not pass all test cases.
My latest implementation was even optimised with logarithms and extensively used continued fraction representation. When binary search along the Stern-Brocot tree was too slow for an input like
3 1000000000 1000000000000000because of occasionally looking forgcdto get mediants, I switched to first finding the continued fraction representation of the parent, and get the neighbour fraction from it (the parent itself or the left branch of it whichever applicable).I don't know where and how I could further improve my solution, consider it gives result for
3 1000000000 1000000000000000in about 1 second.EDIT: One of the test inputs that requires more time:
100010627 100010633 1000000000000000.EDIT 2: Got a very fast solution making use of the concept of Farey neighbours and modular inversion (implemented with Extended Euclidean Algorithm, which I just copied from somewhere else). It looks mythical to me that just with the property , we could get to the answer in a blink of an eye. Very useful when the denominator of input is large. As I know nothing about modular inversion, will definitely come back to it after some reading.
khoangcachxalam1 [deleted]khoangcachxalam1 thank for Kitchent's edit 2 : I used Extended Euclidean Algorithm (you can find it in internet) ! with input is "a" and "b" and "limit", and output "p" and "q"; the first you need find p/q < a/b : and condition is q < = limit; Because Farey "neighbours" properties satisfied a*q-b*p=1 (1) or a*q=1+p*b because p*b=0 mod b therefor-> a*q=1 mod b , you use Extended Euclidean Algorithm for this equation , you will find Q ,, ---> q= b* t + Q (2) , with "t =0,1,2,3,4,....." you to replace (2) in (1) --> a*(b*t+Q)-1=p*b --> p=a*t + (a*Q-1)/b =a*t+ P with P= (a*Q-1)/b; --> p/q=(a*t+ P)/( b* t + Q) with t=0,1,2,3,4.... because constion q < = limit --> b*t+Q < = limit -->t < = (limit-Q)/b ; because t is natural number t == [ limit - Q / b ] you will find result in O(logb) , finally printf "p" and "q" //
hemanth7787 Farey sequence can be used to generate reduced proper fractions.
chenyg 别看下面几位大爷的瞎BB。
(b*N-1)/(N*X) is a fraction less than b/a. Take the k step continued fraction of the fraction and calculate the denominator of the fraction represented by the continued fraction. Use Binary Search for k in range(1,32).
jeekobu For those who became interested in Stern-Borcot due to this problem, just a note that studying the repeated application of it's recursive formulae can lead to quick algorithms (including for this problem, no GCD or modular inverse required), and also useful approximations. For example, my computer cannot tell the difference between M_PIl (pi as an f64) and 8717442233 / 2774848045, but also 355/113 is probably "good enough" in many cases (too large by 0.0000085%).
A related tree is the Calkin-Wilf tree. I recommend the paper "Recounting the Rationals" for those intrigued by Stern-Brocot. It's a very short, accessible, and intersting paper.
ErikTillema Solved this problem in F# with the following strategy: Follow the path in the Stern-Brocot tree by using binary search and medians until you find the target fraction a/b. When you find it, use the target fraction and last left-boundary of the binary search to do more repeated medians until the denominator is greater than N.
What surprises me is that this solution is accepted, while it runs for 50 seconds on an input like 1 1000000000 1000000000000000
If anybody has a solution to this problem that is also efficient for the test case 1 1000000000 1000000000000000 then I would love to hear it! Thanks
MiniMax Yes. Using the Extended Euclidean algorithm, you can solve it in O(log b) time.
jeekobu My Stern-Brocot approach takes 0.054 seconds for that sample. Let the "SB enumeration" of a/b be a sequence of Ls and Rs depecting the left and right branches taken in the tree. Then 1/n is a sequence of n-1 Ls. I'm guessing that in your approach, you took one L (or R) at a time. But it's possible to calculate how many Ls (or Rs) to take in a row at each change in direction, thus going from 1/1 to 1/n in a single iteration, instead of n-1 iterations.
Once you find a/b in the Stern-Borcot tree, there are only two possible paths to find the answer (due to the sorted nature of the tree), which can both be found in constant time. The worst case for finding a/b is LRLRLRLR... which corresponds to the Fibonacci numbers; Fib(n) is approximately phi^n, so the algorithm to find a/b is O(log(b)).
I don't want to reveal to much here, but message me if you're still interested in the algorithm.
Diophant Happened to implement the same algorithm ErikTillema describes in C which takes just under 1 second to run 1 1000000000 1000000000000000.
But I had to do some smart optimization to avoid TLE with for last test case; afterwards all test cases ran in "0s".
Happy to discuss further details by pm with anyone who has solved the challenge 100%.
georeth2010 Accepted by using __int128_t in C++. (only for comparision)
bool is_less(int64_t x1, int64_t y1, int64_t x2, int64_t y2) { return (__int128_t)x1 * y2 < (__int128_t)x2 * y1; }
search the answer in continued fraction tree. floating point error will cause problem.
ErikTillema Just wondering: Is your solution also fast on a test case like 1 1000000000 1000000000000000 ? If yes, I would love to hear how you solved this problem.
welcometors For the last 4 cases number can temporarily go above 64-bit int. I've to rewrite the code in python. Python has Requests and BeautifulSoup on top of it's standard library, so Boost should be included for C++.
Crafter_Artisan I noticed that too, and ended up getting around it with modular exponentiation and a couple of other tricks, ultimately achieving a runtime of order O(sqrt(b) log(b)). When I saw how fast it ran, it felt a little bit like I'd used a cannon to swat a mosquito...... :-3
welcometors Hahaha. Nice :)
padeff I got it right, I still don t get how; checking possible integer solution defining a lowerbound got me only half right. parcouring the farey tree worked, but when i check the number of iteration it looks actually worse for the tree method. I got close to 10*7 iteration on 10*10 or n and 10**8 for d anyway, i m glad it s done.
ErikTillema I think I had a similar experience, see my other comments. Did you find a more efficient solution for those test cases later?
bigOTHER This problem is a unique farey tale! Thanks @shashank21j
Sort 11 Discussions, By:
Please Login in order to post a comment