NyaanNyaan commented 2 years ago

問題概要

Convolution (Large)

T 個のテストケースに答えてください。

整数 N, M, S が与えられます。まず、以下の疑似コードにより長さ N の列 A, 長さ M の列 B を復元してください。

追記：コーナーケースを入れる必要性も考えると、入力は以下の乱数ではだめそう

state = S
for i = 0...N-1
    state = (state * 1103515245 + 12345) modulo 2^31
    a_i = state >> 2
for i = 0...M-1
    state = (state * 1103515245 + 12345) modulo 2^31
    b_i = state >> 2

次に

c_k = [x^k] (sum_i A_i x^i)(sum_j B_j x^j) mod 998244353

を満たす列 c_0,c1, ..., c{N+M-2} を計算して、すべての要素の xor を取ったものを出力してください。

入力

T
N_1 M_1 S_1
N_2 M_2 S_2
\dots
N_T M_T S_T

制約

T <= 100
N, M <= 2^{19}
0 <= S < 2^31
10 sec

https://judge.yosupo.jp/problem/convolution_mod は速度を計るにはテストケースが小さすぎる問題があり、実行時間のブレを減らすために制約が大きい版がほしくなったので立てました。(N <= 2^{22} にするみたいな案もありそう)

hos-lyric commented 2 years ago

N <= 2^{22} (で適切なケース数) がいいかなと思っています．

入力は何が適切かよくわかりません (疑似乱数とされているかつ速い，とかが要件？)
出力の関連 #149

hly1204 commented 2 years ago

Seems useful! Actually I found that when doing mutiple convolutions, the O(log n) precomputation of the twiddle factors is slower than O(n) (fullly) precomputation of the twiddle factors if I am not wrong. Maybe more testcases are needed.

yosupo06 commented 2 years ago

既存のconvolutionと同じ形式で、N<=2^25とかにしたのを作るのはどうでしょうか？　別アルゴリズムが必要になるので入れたさはあります

懸念は入出力が重すぎてバックエンドの何処かが壊れることですが、やってみないとわかりません

NyaanNyaan commented 2 years ago

いろいろ案はありそうですが、FFT の実行時間を測るだけなく多少の実用も見込めそうなので N <= 2 ** 25 でとりあえず準備してみました。

TL, ML 関連

実行時間は SIMD あり FFT を持ち出せたら雑に書いても入出力込みで 3 sec 程度で動きそうなので、 10 ~ 15 sec にすれば適切に実装した C++ なら通りそうです。

一方、空間の定数倍が想像より重く、1ケースあたり 1.5 GB でした。 N <= 2^{24} に下げるか ML を 2GB にするのがちょうど良さそうです。

また、Windows では手元実行の際に correct.cpp のコンパイルオプションの都合でスタック領域が足りず落ちてしまいます。これに関しては別途 Issue を立てました。 #721

入出力

とりあえずそのままで準備してみたところ、

実行時間の 5 ~ 6 割程度が入出力
testlib.h がおそらく遅く、output_checker が手元で 1 ケースチェックするのに 2 ~ 3分程度かかる
- もしもジャッジ上でも同じ感じだとしたら 1 提出のジャッジに数十分かかってまずそう
CI の際もおそらく同様に数十分かかる？
テストケースのサイズが全ケース合わせて 11GB (+ 入れたいコーナーがあるので +数 GB)

とワクワク要素が詰まった感じになりました。特に output_checker が遅いのがまずそうで、少なくとも出力だけでもハッシュ化した方が良さそうに思いました。

NyaanNyaan commented 2 years ago

入力に関しても、seed, ab_min, ab_max を与えて「入力は https://github.com/yosupo06/library-checker-problems/blob/master/common/random.h を貼って自分で生成してください。」という風にすれば、入力ファイルを与えるのと同程度に疑似乱数としての強さがあり、かつ all_zero や fft_killer のようなコーナーケースもある程度自由に生成できるのではないかと思いました。

yosupo06 commented 2 years ago

コードを見たいので、準備していただいたコードでとりあえずPull Requestを作っていただくことは可能でしょうか？　

output checkerに2^26個の整数を入れたら6sで終わりました、generator.pyになにかバグがあるか、環境依存かもしれません

NyaanNyaan commented 2 years ago

pull request しました (確かに言われてみると自分の環境は output 回りが遅いので環境依存のような気もしてきました)

defnotmee commented 7 months ago

The constraints have a weird typo in it, it says 1 <= n, m <= 2^24 = 2^24.

I believe it's supposed to be either 1 <= n, m <= 2^24 or n, m = 2^24.

maspypy commented 7 months ago

Thank you for reporting it! I will fix it. It was originally displayed as 「 $\cdots=16777216=2^{24}$」, and now, the constant is automatically converted into exponential form.

yosupo06 / library-checker-problems

[問題案] Convolution(large) #720

問題概要

入力

制約

TL, ML 関連

入出力