On continued fractions. Part 3: In competitive programming

Правка en2, от adamant, 2022-03-31 21:05:11

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:

CP-Algorithms — Continued fractions

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.

Beyond what I already wrote on continued fractions in my previous blog posts, I added several explanatory examples and pictures. I also elaborated on the connection between continued fractions and the Stern-Brocot tree and Calkin-Wilf tree, binary trees that contain all distinct positive rational numbers. Also, I really hope that I managed to simplify the general story-telling in the article.

To make a further teaser, here are the major problems that are dealt with in the article:

  • Given $$$r$$$ and $$$m$$$, find the minimum value of $$$q r \pmod m$$$ on $$$1 \leq q \leq n$$$.
  • 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:
$$$\sum\limits_{x=1}^n \lfloor \frac{px+b}{q} \rfloor.$$$
  • Given $$$r$$$ and $$$m$$$, find $$$\frac{p}{q}$$$ such that $$$p, q \leq \sqrt{m}$$$ and $$$p q^{-1} \equiv r \pmod m$$$.
  • 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}$$$.

There are likely much more problems where continued fractions are used, please mention them in the comments if you know any!

So far, here is the list of problems that are explained in the article:

And an additional list of practice problems where continued fractions could be useful:

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.

Теги tutorial, cp-algorithms, continued fraction, #continued fractions, euclidean algorithm, number theory

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en17 Английский adamant 2022-04-03 19:07:16 2 Tiny change: '[problem:356E]\n* [pr' -> '[problem:346E]\n* [pr'
en16 Английский adamant 2022-04-02 18:59:41 141
en15 Английский adamant 2022-04-02 06:27:52 126
en14 Английский adamant 2022-04-02 06:23:37 33 Tiny change: 'rmations, continued fractions on segments, quadrat' -> 'rmations, quadrat'
en13 Английский adamant 2022-04-02 06:22:06 614
en12 Английский adamant 2022-04-02 06:16:15 141 Tiny change: 's smaller?\n- How to em' -> 's smaller? How to em'
en11 Английский adamant 2022-04-02 05:18:30 303
en10 Английский adamant 2022-04-01 16:35:49 109
en9 Английский adamant 2022-04-01 16:09:33 374
en8 Английский adamant 2022-04-01 03:06:15 2 Tiny change: ' Fractions\n](https://' -> ' Fractions](https://'
en7 Английский adamant 2022-04-01 02:59:55 103
en6 Английский adamant 2022-04-01 02:44:14 537
en5 Английский adamant 2022-03-31 21:14:30 108
en4 Английский adamant 2022-03-31 21:09:57 137
en3 Английский adamant 2022-03-31 21:05:35 256
en2 Английский adamant 2022-03-31 21:05:11 1650 Tiny change: 'article:\n* [Timus' -> 'article:\n\n* [Timus'
en1 Английский adamant 2022-03-31 19:54:49 3507 Initial revision (published)