[verify] extra/math/pow_of_formal_power_series_test.nimのverifyが失敗する

[haruyama480]

% ulimit -s 65000  
% oj-verify run verify/extra/math/pow_of_formal_power_series_test.nim
(略)
[INFO] slowest: 0.780420 sec  (for M_zero_00)
[FAILURE] test failed: 4 AC / 32 cases
(略)

結構失敗しちゃいます これは手強そう

[chaemon]

https://atcoder.jp/contests/abc317/submissions/46642639

一応、1.6.14で利用実績はあってACしているんですが、環境依存なんですかね。。。109行目です。

[haruyama480]

AC実績情報ありがたいです

[haruyama480]

overflowしてる..?

[INFO] monomial_02
fatal.nim(54)            sysFatal
Error: unhandled exception: over- or underflow [OverflowDefect]

[chaemon]

それは重要な手がかりですね！

[chaemon]

単純な入力でも落ちてるようです。(0の0乗的なものですかね。。。) この例以外はunderflowで落ちていますかね。

[FAILURE] WA input: 2 0 0 0

output: 0 0

expected: 1 0

[chaemon]

あと、こちらの環境では4個ではなく18個は通りましたよ！

[FAILURE] test failed: 18 AC / 32 cases

[chaemon]

Nim-ACL/src/atcoder/extra/math/formal_power_series.nim(485)でunderflowが起こっているようです。

/Users/toshihiroshimizu/git/Nim-ACL/src/verify/extra/math/pow_of_formal_power_series_test.nim(15) pow_of_formal_power_series_test /Users/toshihiroshimizu/git/Nim-ACL/src/verify/extra/math/pow_of_formal_power_series_test.nim(13) main /Users/toshihiroshimizu/git/Nim-ACL/src/atcoder/extra/math/formal_power_series.nim(485) pow /Users/toshihiroshimizu/.choosenim/toolchains/nim-1.6.14/lib/system/fatal.nim(54) sysFatal Error: unhandled exception: over- or underflow [OverflowDefect]

[chaemon]

あ、わかりました！485行目のif i k > deg:というところのi kでオーバーフローしているようです。

[haruyama480]

ちょうど自分もそこ見てました! FPSちゃんと学習できてないので、一旦調査任せてもいいですか?

[chaemon]

はい。degは配列の長さ分しかとらないので常識的な大きさであれば、if i > deg or k > deg or i * k > deg:とすれば良さそうです。

[chaemon]

i, kが0だった場合だけ状況が変わるのでもう少し複雑ですね。

[chaemon]

さっきの0^0のケース以外AC出せました！

[INFO] slowest: 1.451678 sec (for M_zero_00) [INFO] max memory: 67.224000 MB (for monomial_01) [FAILURE] test failed: 31 AC / 32 cases

[chaemon]

0乗の場合に無条件で1にするようにしたら全部ACしました。

PRとか面倒なので、直接pushしちゃいました。すみません。。。

[chaemon]

変更点はこちらです。degが配列の長さでこれが32bitに収まらないサイズでないといけないのですが、配列の長さが32bitより大きくなるのは競プロでは考えられないので、これで大丈夫そうです。

https://github.com/zer0-star/Nim-ACL/commit/80bbcdea1738f47955707cd24547d584607b8dfb

[haruyama480]

ありがとうございます！

degは配列の長さ分しかとらないので常識的な大きさであれば、if i > deg or k > deg or i * k > deg:とすれば良さそう

まさにこれですね

これでfloatの件以外はverifyできましたね:tada: closeよろしくお願いします

[chaemon]

Closeしました。if i > deg or k > deg or i k > deg:だとi=0でk > degの場合で意図した結果と違う結果になるので、pという変数にikの値を保存する(オーバーフローに注意する)としました。

[chaemon]

上記の利用実績ではべき乗するkの値が小さくてi*kでオーバーフローしないのでちゃんと動作していたんですかねー