How to solve N<10^6 or N<10^{15} versions of Neighbouring Fraction
For N < 10^2 I did simple brute search over all pairs (a,b). Ideas for higher constraint versions are welcome.
Use binary search
2 Likes
How?
I just used ln/dn,(ln+rn)/(rd+ld), rn/rd.
It wasnt enough.
initially ln=0/1, rn=1/1
mid=0+1/1+1 = 1/2
check whether a/b lies to the left or right and repeat
A beautiful result is that if \frac{a}{b} is the neighbour of \frac{c}{d}, Then \frac{c}{d}-\frac{1}{bd}=\frac{a}{b}. So you can binary search on b.
3 Likes
Thats what I did and it isnt enough. Consider this tc.
a/b=1/1e9
n=1e10
R will be -
1/1,1/2,1/3,1/4,… TLE.
1 Like
oops didnt think of this
is the contest rated ?
One question got removed mid contest, Contest got stopped in the middle. I don’t see any reason for it to be unrated. 
I have an idea with this: let the final fraction be \frac{x}{y}, then ya-xb=1 and we can use the euclidean algorthm to get x=ak+x_0 and y=bk+y_0 in where we just take the largest y\leq n
1 Like
this question is same as project euler 71
BTW congo fr 7 star 
1 Like
Tl;Dr; This fails on samples.
Right now, I want to submit one heuristic waiting for them to open practice submission.
Lets l=ln/ld,r=rn/rd.
For finding mid, WLOG lets assume ld<=rd.
Let r=min(rd,n-rd)/ld
mid=(rn+r*ln)/(rd+r*ld)
Keep doing it until ld+rd>n
In this maximum denominator in next iteration almost doubles.
1 Like
@admin can you please open last problem for practice?
Problem is nice I wanted to submit it in practice.
We’ll not be moving it to Practice.
2 Likes
OH! The tasks were copied thats why the contest was called off!