yosupo06/library-checker-problems

The problem data (Test case generator, judge's solution, task, ...) of Library Checker

library-checker-problems's Issues

[問題案]System of Linear Equations(system_of_linear_equations)

N x M次元の行列A、長さNのベクトルbが与えられます。A x = bを満たすxを求めてください。(mod 998244353)

入力

N M
A
b0 b1 b2 ...

出力

解空間のランク(存在しない場合-1)
解のうちどれか一つ
解空間の基底ベクトル(M次元) (行ベクトルとして、縦に並べる)

制約

N, M <= 500

[問題案]K-th of Partition Function(partition_function)

[問題案]Static RMQ(staticrmq)

手元で単一ファイルのらくらくテスト

欲しくない？ 僕は欲しい

[問題案]k-th root

a,n, mが与えられる

x^n = a(mod m)を満たすxを求める

[問題案]Unionfind(unionfind)

[問題案]Point Add Range Sum(point_add_range_sum)

長さNの数列a_iにQ個のクエリ

• 1 k x: a_k += x
• 2 l r: sum a_l ~ a_{r-1}

N, Q <= 500,000(200,000?)
0 <= a_i, x <= 1e9

想定

• fenwick tree
• segment tree

deployが同じファイルでも違うhashを生み出す

サンプル

• サンプルが欲しい
• どういう形式？

想定誤解法を扱う機能

ローカルで自分のソースコード群に対してテストできるように

[問題案]Multipoint Evaluation(multipoint_evaluation)

[問題案]Convolution(convolution_mod)

[問題案]漸化式のkth / berlekamp massey

入力の順番

[問題案]Discrete Logarithm(discrete_logarithm_mod)

Tケース

x, y, mが与えられる。x^k = y (mod m)なるkのうち、最小を答えよ(存在しない場合-1)

• 1 <= T <= 100?
• 1 <= m <= 10^9
• 0 <= x, y < m

[問題案]Determinant of Matrix(matrix_det)

[問題案]A + B(aplusb)

clangでコンパイルできなくてもCIが通る

[問題案]Run Enumerate(runenumerate)

[問題案]Lowest Common Ancestor(lca)

[問題案]Strongly Connected Components

キャッシュ機能

generator.pyにキャッシュみたいな機能ほしい

Directed MST の output

Directed MST のサンプル #2 の答えがおかしいように思います.

[問題案]分数a/b , c/dが与えられるから、a/b < x < c/dを満たす中でもっとも分母が小さいやつを求めるやつ

[問題案]Matching on Bipartite Graph(bipartitematching)

[問題案]Determinant of Sparse Matrix(sparse_matrix_det)

空vectorをshuffleすると壊れる

壊れる。

チェックしたいライブラリ

随時募集中

• 個別のissueが立ったもの
• 重複しているもの
• 問題として追加されたもの

はガンガンresolvedにしていきます

[問題案]オイラー路

euler tour / pathなどをどうするか？

全部まとめる？

[問題案]郵便配達問題(有向, 無向)

https://ja.wikipedia.org/wiki/%E4%B8%AD%E5%9B%BD%E4%BA%BA%E9%83%B5%E4%BE%BF%E9%85%8D%E9%81%94%E5%95%8F%E9%A1%8C

[問題案]Directed MST(directedmst)

run enumerate

runの定義が間違っているのでは？と話題に
具体的にはaaaaaaaaaaの時に、周期=2,3,..を全部出すか、最大だけを出すか

[問題案]Polynomial Interpolation(polynomial_interpolation)

[問題案]Sum of Floor of Linear(sum_of_floor_of_linear)

outputchecker

• どういう形式?
• そもそも必要か？(diffで対応できない問題はあるか？)

warningを消す

そして-Werrorをたす

solution / verifyのパス

solution = "correct.cpp"
verify = 'verify.cpp'

これ必要かな？これじゃないケースがあるか

[問題案]2 Sat(two_sat)

入力 / 出力 形式をどうするか？

• DIMACS標準形式？

CIが重過ぎる

そもそもg1-smallってのが無理があるんだよね、cloudbuildなど、CIを回すときだけ強いサーバーを借りるような方針で

[問題案]Suffix Array(suffixarray)

[問題案]Assignment Problem(assignment)

[問題案]Sqrt Mod(sqrt_mod)

Tケース

y, pが与えられる。x^2 = y (mod p)なるxを1つ求めよ(存在しない場合、-1)

• 1 <= T <= 100,000
• 2 <= p <= 10^9
• 0 <= y < p
• p is prime

ログの順番がめちゃくちゃ

generator.pyの並列化対応 / generator.pyの高速化

#55 を解決するために必要不可欠

[問題案]Factorize(factorize)

[問題案]Range Add Range Max(range_add_range_max)

長さNの数列a_iにQ個のクエリ

• 1 l r x: a_k += x
• 2 l r: max a_l ~ a_{r-1}

N, Q <= 500,000(200,000?)
0 <= a_i, x <= 1e9

想定

• (Lazy) segment tree

[問題案]Dominator Tree(dominatortree)

テストケース生成が重い(sqrt_mod)

#27

[問題案]Z Algorithm(zalgorithm)

checkerがコンパイル通るかわからない

solutionsが無いときにコンパイルしないから