Comments (11)
自分の提出 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.
Related Issues (20)
- Actions: All generate test failed HOT 3
- [テストケース] matrix pow / characteristic polynomial
- [テストケース] zeros : Polynomial Interpolation
- generate.py の `|` による Union の是非 HOT 1
- [Problem proposal] All Farthest Neighbors in Convex Polygons HOT 6
- 問題案 Incremental SCC HOT 2
- [Problem proposal] Unionfind with Potential HOT 13
- testcase for RMQ: add test where there exists a subarray with multiple minimums HOT 4
- 【テストケース】Furthest Pair of Points HOT 1
- [テストケース案] Consecutive Terms of Linear Recurrent Sequence
- [テストケース] Closest/Furthest Pair of Points のケース near_grid が意図通りでないと思われる HOT 2
- [Problem proposal] Minimum Diameter Spanning Tree HOT 2
- [機能案] 提出頻度制限 HOT 1
- [テストケース] Suffix Array HOT 4
- [テストケース] Eulerian Trail HOT 1
- [問題案] partially retroactive priority queue HOT 3
- Assignment Problem: Make it n-by-m instead of n-by-n?
- Weak testcases in Link-Cut-Tree Problems.
- [機能案] unsolved枠の追加 HOT 3
- Migrate to C++17? HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from library-checker-problems.