[問題案] Rational Approximation

toriitakuto commented 1 year ago

Problem name: Rational Approximation

Problem

整数 $N,M$ が与えられる．分子・分母がともに $M$ 以下の正の既約分数の集合を $S$ として， $\max \lbrace x\in S|x\leq \sqrt{N}\rbrace, \min \lbrace x\in S|x\geq \sqrt{N}\rbrace$ を求めよ．

Constraint

$1 \leq T \leq 10^5$
$1\leq N\leq 10^{18}, \sqrt{N}\leq M\leq 10^9,$

Solution / Reference

Stern Brocot Tree 上で二分探索をする． $O(\log M)$
https://atcoder.jp/contests/abc294/editorial/6017

Input

T
N_1 M_1
...
N_T M_T

Output

a_1/b_1 c_1/d_1
...
a_T/b_T c_T/d_T

$a/b=\max \lbrace x\in S|x\leq \sqrt{N}\rbrace, c/d=\min \lbrace x\in S|x\geq \sqrt{N}\rbrace$

Note / Disucussion

近似の対象として $\sqrt{N}$ を提案しましたが，何かありますでしょうか

toriitakuto commented 1 year ago

有理数 $A/B$ を与えて，それを $S$ の要素で左右から挟みこむのでもよさそうでしょうか

maspypy commented 1 year ago

有理数を与えて，それを $S$ の要素で左右から挟みこむ

有理数二分探索を verify するのであれば、こっちの方が最悪ケースの類が作りやすそうな気がします。

maspypy commented 1 year ago

（$\sqrt{N}$ の近似分数には Pell 方程式を解くという別の需要がありますね）

maspypy commented 1 year ago

とりあえず具体的な対案をひとつかきます。

[問題] $N, x, y$ が与えられる。分子・分母が $N$ 以下の有理数全体を $S$ として、 $S$ の元のうち、 $x/y$ 以下であるもの、 $x/y$ 以上であるものの max, min を求めよ。

[制約]

$1\leq N\leq 10^6$
$0\leq x< y \leq 10^{12}$

・実用上わりと見る制約・すべての計算が 64-bit でおさまる（おさまらない場合のケアは各自ということで）・ $x< y$ を入れたため、解は必ず存在する（問題準備がすこし楽）。 $x>y$ の場合を $x\leq y$ の場合に帰着するのは容易である。

NachiaVivias commented 1 year ago

私が想像したのはこうでした。

[問題] 分母分子が $N$ 以下の正整数である既約分数の集合を $S$ とする。 $x/y$ 以上の min （存在しなければ $(0,1)$ ）、 $x/y$ 以下の max （存在しなければ $(1,0)$ ）を出力せよ。

[制約]

$0 \leq N \leq 10^9$
$1 \leq x, y \leq 10^9$

TLE する系のバグに対して、 $10^9$ が強い

maspypy commented 1 year ago

私の案と比べて些細な違いだと思っているので、まあそっちでもよいです。どちらをライブラリ化したい場合でも、どちらでも verify に利用可能ですし。

何となく、「有理近似」と言った場合に、「小さい分母で近似する」という文脈である（つまり $\max(x,y)$ ではなく $y$ をおさえる）ことが多い印象があるというくらいです。

maspypy commented 8 months ago

ところで、$1\leq N\leq 10^{18}$, $1\leq x, y\leq 10^{18}$ でも 64bit 整数で全部計算できるはずだな。

maspypy commented 8 months ago

結論として https://github.com/yosupo06/library-checker-problems/issues/960#issuecomment-1527857623 これでお願いします。

全部 $10^{18}$ でも 64 bit に収まるという話はあるのですが、$10^9$ の方が、

def check(a,b): return a/b<=x/y
ans = max_right(check, N)

というタイプのライブラリの verify に都合が良いということで、制約も $10^9$ で。

lpha-z commented 8 months ago

この問題の実装に興味があります。contributions-welcomeとのことなので、やらせていただけないでしょうか。私は競技プログラミングはほぼやりませんが、Stern-Brocot Treeや下りる回数の二分探索は知っているつもりです。また、以前に二回テストケースを追加するプルリクエストを出していますので、Library Checkerの基本的な動作については知っています。基本的には上記NachiaViviasさんのコメントに従って問題作成すればよいとの認識です。

いくつか相談させていただきたいことがあります。

ウェブページに掲載される方の話

問題文などのスタイルやExampleとして何を入れておくべきかについて、よくわかっていません。

問題文のスタイルはあまり気にしない（style.md）ので適当でいいということでしょうか。
Exampleは「非常に小さくて手計算でもわかりそうな例題」「大きくて非自明そうな例題」「コーナーケースを出力するべき例題」があればよいでしょうか。ほかに必要なものがあればご指摘ください。
- 200 314159265 100000000とかがあってもいいかもしれません
オリジナルの問題案では、出力に/を含めるようなフォーマットを指定しています。しかしこのようなフォーマットは他の問題では一般的ではないようです。/を含めないフォーマットで作ってよいでしょうか。

ジャッジサーバーで使う方の話

コーナーケースとしては以下のものがあると思いますが、それだけで十分でしょうか。
- 出力が1/0や0/1になるケース
  - N=0のケース
  - それ以外
- 入力そのものが出力になるケース
  - N=max(x,y)のケース
  - N=max(x,y)のケース
- x/yが既約分数でないケース
落としたい解答としては以下のものがあると思いますが、それだけで十分でしょうか。
- 毎回下る方向を判定する解法（Stern Brocot Treeを一方向に下り続けるケースで撃墜可能）
- 二分探索したところまで下りちゃって$N$を超えちゃう解法（適当なランダムケースで撃墜可能？）
- 大小関係を倍精度浮動小数点数で比較しちゃう解法（大きめのランダムケースが複数あれば撃墜可能？）
  - 拡張倍精度浮動小数点数を精度で落とすのは無理。時間で落とすのは可能だが趣旨に反するだろう

よろしくお願いいたします。

maspypy commented 8 months ago

確認不足だった @NachiaVivias https://github.com/yosupo06/library-checker-problems/issues/960#issuecomment-1527857623 これ $1\leq N$ のつもりだったりしますか？（0/1 や 1/0 が出力に来るし）

NachiaVivias commented 8 months ago

これ $1\leq N$ のつもりだったりしますか？（0/1 や 1/0 が出力に来るし）

（ $N=0$ のときは問答無用で 0/1, 1/0 を出力、これは例外なので許される、みたいなことを考えていたかもしれませんが、）

実際は $1\leq N$ にするのがよいと思います。失礼しました。

maspypy commented 8 months ago

この問題の実装に興味があります。contributions-welcomeとのことなので、やらせていただけないでしょうか。

もちろん，めちゃくちゃありがたいです！

問題文のスタイルはあまり気にしない（style.md）ので適当でいいということでしょうか。

まあそうですね．例えば問題間で，漢字・仮名の使い分けや，スペースの有無や，句読点などの細かい表記の統一まではやっていないです．

今回は問題文も短いですし，あまり変なことにはならないと思います．とりあえず書いていただければ，pull request 後に確認します．

Exampleは「非常に小さくて手計算でもわかりそうな例題」「大きくて非自明そうな例題」「コーナーケースを出力するべき例題」があればよいでしょうか。ほかに必要なものがあればご指摘ください。 200 314159265 100000000とかがあってもいいかもしれません

そのくらいあれば，かなり完璧だと思います．

また，issue 内で少し読み取りにくく感じたので一応補足しておくと，マルチテストケース（ $T$ 問分の入出力をする）の形式でお願いします．この場合，たくさんのケースをひとつの example にしてしまうパターンもありますし（ https://judge.yosupo.jp/problem/min_of_mod_of_linear ），特殊ケースっぽいものを別の example にしたりしてもよいです（ https://judge.yosupo.jp/problem/eulerian_trail_directed ）．

オリジナルの問題案では、出力に/を含めるようなフォーマットを指定しています。しかしこのようなフォーマットは他の問題では一般的ではないようです。/を含めないフォーマットで作ってよいでしょうか。

そうですね、分子・分母の順に 2 数を出力すればよさそうです。（ https://judge.yosupo.jp/problem/stern_brocot_tree ）

コーナーケースとしては以下のものがあると思いますが、それだけで十分でしょうか。落としたい解答としては以下のものがあると思いますが、それだけで十分でしょうか。

上の議論の通り， $N=0$ はなかったことにしてください．

かなりよさそうだと思います．（テストケースはあとからでも足せるというコンテンツなので本当はもう少しさぼってもよいくらいです）

あとは，次のようなものが考えられるかなと思いました．

$1\leq N,x,y\leq 100$ のケース（ $10^6$ 個）を全部作ってしまって small_all_00 ～ small_all_09 に入れておくという感じのことをすると，計算ミスしているタイプの実装はほとんど検出できて楽だと思います．
ある種の最悪ケースとして，黄金比のように SBT の進行方向が変わる回数が最大近いものを入れてもよいかもしれません．

lpha-z commented 8 months ago

深夜にもかかわらず素早い返答ありがとうございます。追加のテストケースの指摘を確認しました。 small_allは、なるほど盲点でした。ではそんな感じで作業していきたいと思います。

yosupo06 / library-checker-problems