Hi everyone!
It's been quite some time since I wrote two previous articles in the cycle:
Part 1: Introduction
Part 2: Properties and interpretation
Part 3: In competitive programming
This time I finally decided to publish something on how one can actually use continued fractions in competitive programming problems.
Few months ago, I joined CP-Algorithms as a collaborator. The website also underwent a major design update recently, so I decided it would be great to use this opportunity and publish my new article there, so here it is:
It took me quite a while to write and I made sure to not only describe common competitive programming challenges related to continued fractions, but also to describe the whole concept from scratch. That being said, article is supposed to be self-contained.
Main covered topics:
- Notion of continued fractions, convergents, semiconvergents, complete quotients.
- Recurrence to compute convergents, notion of continuant.
- Connection of continued fractions with the Stern-Brocot tree and the Calkin-Wilf tree.
- Convergence rate with continued fractions.
- Linear fractional transformations, quadratic irrationalities.
- Geometric interpretation of continued fractions and convergents.
I really hope that I managed to simplify the general story-telling compared to previous 2 articles.
Here are the major problems that are dealt with in the article:
- Given $$$a_1, \dots, a_n$$$, quickly compute $$$[a_l; a_{l+1}, \dots, a_r]$$$ in queries.
- Which number of $$$A=[a_0; a_1, \dots, a_n]$$$ and $$$B=[b_0; b_1, \dots, b_m]$$$ is smaller? How to emulate $$$A-\varepsilon$$$ and $$$A+\varepsilon$$$?
- Given $$$A=[a_0; a_1, \dots, a_n]$$$ and $$$B=[b_0; b_1, \dots, b_m]$$$, compute the continued fraction representations of $$$A+B$$$ and $$$A \cdot B$$$.
- Given $$$\frac{0}{1} \leq \frac{p_0}{q_0} < \frac{p_1}{q_1} \leq \frac{1}{0}$$$, find $$$\frac{p}{q}$$$ such that $$$(q,p)$$$ is lexicographically smallest and $$$\frac{p_0}{q_0} < \frac{p}{q} < \frac{p_1}{q_1}$$$.
- Given $$$x$$$ and $$$k$$$, $$$x$$$ is not a perfect square. Let $$$\sqrt x = [a_0; a_1, \dots]$$$, find $$$\frac{p_k}{q_k}=[a_0; a_1, \dots, a_k]$$$ for $$$0 \leq k \leq 10^9$$$.
- Given $$$r$$$ and $$$m$$$, find the minimum value of $$$q r \pmod m$$$ on $$$1 \leq q \leq n$$$.
- Given $$$r$$$ and $$$m$$$, find $$$\frac{p}{q}$$$ such that $$$p, q \leq \sqrt{m}$$$ and $$$p q^{-1} \equiv r \pmod m$$$.
- Given $$$p$$$, $$$q$$$ and $$$b$$$, construct the convex hull of lattice points below the line $$$y = \frac{px+b}{q}$$$ on $$$0 \leq x \leq n$$$.
- Given $$$A$$$, $$$B$$$ and $$$C$$$, find the maximum value of $$$Ax+By$$$ on $$$x, y \geq 0$$$ and $$$Ax + By \leq C$$$.
- Given $$$p$$$, $$$q$$$ and $$$b$$$, compute the following sum:
So far, here is the list of problems that are explained in the article:
- DMOPC '19 Contest 7 P4 — Bob and Continued Fractions
- Tavrida NU Akai Contest — Continued Fraction
- Timus — Crime and Punishment
- June Challenge 2017 — Euler Sum
- NAIPC 2019 — It's a Mod, Mod, Mod, Mod World
- Library Checker — Sum of Floor of Linear
- 102354I - From Modular to Rational
- GCJ 2019, Round 2 — New Elements: Part 2
And an additional list of practice problems where continued fractions could be useful:
- UVa OJ — Continued Fractions
- ProjectEuler+ #64: Odd period square roots
- 305B - Continued Fractions
- 346E - Doodle Jump
- 585C - Alice, Bob, Oranges and Apples
- POJ Founder Monthly Contest 2008.03.16 — A Modular Arithmetic Challenge
- 2019 Multi-University Training Contest 5 — fraction
- SnackDown 2019 Elimination Round — Election Bait
There are likely much more problems where continued fractions are used, please mention them in the comments if you know any!
Finally, since CP-Algorithms is supposed to be a wiki-like project (that is, to grow and get better as time goes by), please feel free to comment on any issues that you might find while reading the article, ask questions or suggest any improvements. You can do so in the comments below or in the issues section of the CP-Algorithms GitHub repo. You can also suggest changes via pull request functionality.
346E - Doodle Jump can be solved using the idea of continued fractions.
Thanks! I kind of see how to formulate it in continued fraction terms, but I'm not sure how to solve it. And I couldn't understand the tutorial, unfortunately... Could you please elaborate a bit on the solution?
The main point is that for every $$$i\cdot a\mod{p}\;(1\le i\le n)$$$, there is always a way to go down a platform with step no greater than $$$h$$$. To do so, we can either increase or decrease $$$i$$$, but if we decide to go from $$$i\cdot a\mod{p}$$$ to $$$j\cdot a\mod{p}$$$, we must have $$$h\ge(i-j)\cdot a\mod{p}$$$.
This means $$$(i-j)a = pk + d$$$ for some integers $$$k$$$ and $$$0\le d\le h$$$. Rewriting gives $$$\frac{a}{p} = \frac{k}{i-j} + \frac{d}{p(i-j)}$$$, so it follows that $$$\frac{k}{i-j}$$$ must be a good approximation of $$$\frac{a}{p}$$$.
Using continued fractions, we can find the least positive and negative $$$i-j$$$ satisfying the requirements; say they are $$$+a$$$ and $$$-b$$$ respectively. Then we need only check that for each $$$1\le i\le n$$$, either $$$i+a \le n$$$ or $$$0\le i-b$$$.
Oh, I see now. Very nice!