 # QUARANTEST - Neighbouring Fraction

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