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

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 :slight_smile:

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.

https://www.hackerrank.com/contests/projecteuler/challenges/euler071/problem

We’ll not be moving it to Practice.

2 Likes

OH! The tasks were copied thats why the contest was called off!