[問題案]Matching on Bipartite Graph(bipartitematching) about library-checker-problems HOT 11 CLOSED

自分の提出 2678, 2679, 2680 が Library Checker では AC となっていますが、他の問題で落ちたので多分ライブラリとして間違っています。

との報告がきた　ランダムだけだと弱いよね…(トホホ)

from library-checker-problems.

https://judge.yosupo.jp/submission/3463 いろいろミスってるのに通った

from library-checker-problems.

最悪ケースがよくわからなかったが、https://codeforces.com/blog/entry/58048 ここに情報がまとまっていそう

from library-checker-problems.

テストケース追加済っぽいので、 close

from library-checker-problems.

Would it be possible to increase the limits to the same sizes as the bipartite ones? (V <= 10e5, E <= 2e5?). The current fastest runtimes are all 1ms, and the theoretical best running times of general graph matchings seem to be the same as the bipartite case?

from library-checker-problems.

Basically, we don't change the constraints once the problem is published. However, we may add a hard version of a problem if necessary.

The current fastest runtimes are all 1ms, and the theoretical best running times of general graph matchings seem to be the same as the bipartite case?

Many solutions solve:

• Bipartite matching in $\Theta(m\sqrt{n})$ time, and
• General matching in $\Theta(n^3)$ or $\Theta(nm\polylog(n,m))$, etc.

Consequently, it seems hard to solve general matching within the same constraints.

from library-checker-problems.

General matching also has some m\sqrt{n} time algorithms that seem implementable: https://arxiv.org/abs/2012.03582, https://dl.acm.org/doi/pdf/10.1145/115234.115366

Agree that it's a much harder problem though. Not clear if such variants will ever show up on CP.... I was just looking for a place where such implementations can be benchmarked.

from library-checker-problems.

Thank you.
It is possible to add the problem to Library Checker regardless of whether they are included in competitive programming questions. However, preparing the answers might be difficult. Would it be possible for you to provide them if you have the appropriate implementation?

from library-checker-problems.

My (likely false) impression from the bipartite case is that 'just' augmenting paths with some randomized tie breaking does fine, so I feel if it's a 5s limit, running a slower code for 5 minutes be more than sufficient to generate data.

There are all sorts of generators from http://archive.dimacs.rutgers.edu/pub/netflow/instances/matching/ as well. So I should be able to put together and maintain a data set.

from library-checker-problems.

I said about the implementation of the solution.

from library-checker-problems.

I think https://judge.yosupo.jp/submission/51989 is a linear memory solution, so it should just work for 10^5 edges.

My guess is constructing data to make this (plus some greedy initializations) is already a major challenge.

I have heard of people with m^{1.5} implementations (e.g. https://tmt514.github.io/ has written papers on this). Let me ask around ...

from library-checker-problems.