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.

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!