[問題案] Enumerate Triangles

[noshi91]

問題名: Triangle Enumeration

参考資料: https://www.slideshare.net/catupper/trianguler

問題概要

単純無向グラフが与えられる
3 頂点であってどの組も互いに結ばれているものを列挙

入力

N M
u_0 v_0
: 
u_{M-1}, v_{M-1}

出力

K
a_0 b_0 c_0
: 
a_{K-1} b_{K-1} c_{K-1}

制約

N <= 10^5
M <= 10^5

検討事項

• 列挙 or 数えるだけ
• 列挙なら出力が多いので hash するべき？

[yosupo06]

全出力は流石に不味いです 10^8ぐらい整数を出力しそうで、まともな時間で出力しきれないと思います(あとサーバーが壊れそう)

enumerate primesと違って適度に間引くという感じでもないはずなので、カウンティングかハッシュかですね ( #149 )

[yosupo06]

Counting Trianglesならこれで問題ないです
Enumerate Trianglesしたい場合もう少し考えます

[noshi91]

入力でランダムな x, y を与えて Π(y+(x+a)(x+b)(x+c)) mod P を出力させるなどを検討しました (時間計算量的な余裕は分からないです)

[yosupo06]

確かに　変にミスる可能性とか考えるより証明可能なものを使えばいい気がする

[yosupo06]

一様性を仮定すると、出力数 / modの確率で0になることと、modをlong longにするとC++以外が壊れることを考えるとよくなさそうです

[noshi91]

各頂点にランダムな値を割り当てる (入力)
Σabc mod P を出力
これでどうでしょうか (衝突確率 3/P 以下)

[yosupo06]

良さそう

[yosupo06]

強いて問題を挙げるなら全部Z_pの演算だから変な解法が生まれそう　まあジャッジのコンセプト的に大した問題ではなく、これを回避すると衝突確率は証明できなくなるが

[noshi91]

では

問題名: Enumerate Triangles

入力

N M
u_0 v_0
: 
u_{M-1} v_{M-1}
x_0
: 
x_{N-1}

出力

A

で大丈夫でしょうか

[yosupo06]

N M
x_0 x_1 ... x_{N - 1}
u_0 v_0
:

の方が良さそうです　他は大丈夫です

[yosupo06]

Pは特段強い理由がないなら998244353でお願いします

[ryuhei-mori]

ここに書くべきか分からないのですが、ui != vj ではなくて ui != vi ではないですか？

[beet-aizu]

x_i = 0 があるとその頂点を無視することになりませんか（制約で弾いた方がいいと思います）

[ryuhei-mori]

嘘解法が通っています。
https://judge.yosupo.jp/submission/8705
これは

100000 99999
1 1 ... 1
0 99999
1 99999
...
99998 99999

で落とせます。頂点のインデックスはランダムにした方がいいかもしれません。

[yosupo06]

一応間違えたときに(入力は固定されてるのでランダムではないんですが)ランダム性を仮定すれば十分な確率で検出できる、というモチベでハッシュを選定したので、x_i = 0を許さないと証明が壊れて微妙な感じになるかもしれません　実はx_i = 0を許さなくても証明が出来る or もっといい何かが示せる　かも　誰かHELP

[noshi91]

0 を抜いても 3 / (P - 1) は保証できるので抜いても大丈夫ですが、抜く必要もないという認識です

[ryuhei-mori]

ごめんなさい。通ってしまいました。
https://judge.yosupo.jp/submission/8705
落とす簡単な方法はNとMを大きくすることですが...
ところでエッジ数がM=100000の完全グラフって入力に入っていますか？
これが三角形の数がΩ(M√M)になる例だと思ったのですが。
この場合の実行時間でNとMの上限を決めるのが良さそうだと思いました。

[noshi91]

ある程度の密グラフはありますが、最大ケースは入っていません
制約を上昇させるかどうかは admin の判断を仰ぎたいです

[noshi91]

N=447 M=99681 の完全グラフで、想定解が手元で 150ms でした
現状のケースだと最大 63ms です

[yosupo06]

• 三角形の個数が最大のケースは、あった方がいいです
• O(N^2)が通るのは何も問題ではありません。基本的に制約は大きめに設定していますが、これは嘘を落とすためではなく速度改善がわかりやすくなるようにしたいからです。
• 制約変更は可能な限りしたくないです(このポリシーは検討の余地が残っていると思っていますが)。ですが今回は初期な上に提出している人が全員理解がありそうなので、増やしてもいいかなと思います

[ryuhei-mori]

ありがとうございます。嘘を落とさなくていいなら今のままでもいいかもしれませんね。
ところで完全グラフだと N ≈ √(2M) となって、三角形の個数は大体 (√2/3) M^{1.5} になりますね。
参考文献のスライドの37pに書いてあるものと比べると 1/3 になっていますが、36pの上界の証明では一つの三角形を3回数えているので、1/3 にしてよさそうです。なので完全グラフがほぼ最大ケースでいいと思います。M = N(N-1)/2 の形で書けないときの厳密な最大ケースはよく分かりません。

[yosupo06]

そうですね　別に制約増やさなくてもいい気がします