Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

[問題案]General Matching(general_matching) #77

Open
yosupo06 opened this issue Sep 24, 2019 · 11 comments
Open

[問題案]General Matching(general_matching) #77

yosupo06 opened this issue Sep 24, 2019 · 11 comments
Assignees
@yosupo06
Labels
contributions-welcome 審査済み testcase About testcase

Comments

@yosupo06
Copy link
Owner

制約

// O(V^3), O(VE), O(VE log V)?

  • 1 <= N <= 300
  • 1 <= M <= N(N - 1) / 2

// O(E sqrt V)

  • 1 <= N <= 100,000
  • 1 <= M <= 100,000
@yosupo06
Copy link
Owner Author

計算量によって実装量がかわり過ぎるのをどうするか

@yosupo06 yosupo06 mentioned this issue Sep 24, 2019
Open
@yosupo06
Copy link
Owner Author

#3 (comment)

@yosupo06
Copy link
Owner Author

O(V^3)でとりあえず作る

@yosupo06 yosupo06 self-assigned this Oct 17, 2019
@yosupo06 yosupo06 mentioned this issue Oct 19, 2019
Merged
@yosupo06
Copy link
Owner Author

https://judge.yosupo.jp/submission/987 嘘解法が通っている(ランダムケースだけだからね…)

@yosupo06 yosupo06 reopened this Oct 23, 2019
@yosupo06 yosupo06 mentioned this issue Nov 11, 2019
Closed
@potetisensei
Copy link

強い（らしい）乱択が落ちるケースが試行回数低いと落ちるケースが入ってる（らしい）ジャッジ:

@yosupo06
Copy link
Owner Author

激 Love

@potetisensei
Copy link

上のも含めて大体ソースはCFです。
http://acm.math.spbu.ru/~sk1/courses/1718f_au2/conspect/conspect.pdf
↑General Matchingの乱択について書かれていて、乱択で増加路を見つけられる確率が頂点数の指数の逆数オーダー（？）であるようなグラフがあると書かれているが、具体的な例が載っていないため何もわからない（5ページ目、最後）
乱択
http://uoj.ac/submission/233938

@yosupo06
Copy link
Owner Author

ありがとうございます！　

@yosupo06
Copy link
Owner Author

(ところでロシア語なんですが…>＜)

@potetisensei
Copy link

いや俺も読めないけど
元のCFの記事貼ったほうがいいですか、割とネタバレになり得るので貼ってなかったんですが

@maspypy
Copy link
Collaborator

maspypy commented Mar 27, 2023

テストケース追加の作業者募集状態っぽい

@maspypy maspypy added testcase About testcase contributions-welcome 審査済み labels Mar 27, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@yosupo06 yosupo06

Labels
contributions-welcome 審査済み testcase About testcase
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@potetisensei @yosupo06 @maspypy