Suggested Test Case for "Matching on Bipartite Graph"

yosupo06 / library-checker-problems

The problem data (Test case generator, judge's solution, task, ...) of Library Checker

https://judge.yosupo.jp/

Apache License 2.0

494 stars 117 forks source link

Suggested Test Case for "Matching on Bipartite Graph" #1068

Closed SzilBalazs closed 1 month ago

SzilBalazs commented 7 months ago

The following solutions gets the accepted verdict using Hopcroft-Karp while allowing multiple visits to the same node in the same iteration. This is a fundamental flaw and makes running time exponential. https://judge.yosupo.jp/submission/174363

One counter test can be seen at cses.fi's school dance test case 15. Note that the problem uses 1 based indexing. Testcase: https://cses.fi/file/ecf9c3c8ee0ce18cbcc322695da6a744b3dfa6a5a9494f16922b4dace171ca25/1/1/

maspypy commented 2 months ago

https://cses.fi/file/ecf9c3c8ee0ce18cbcc322695da6a744b3dfa6a5a9494f16922b4dace171ca25/1/1/ I can't access this URL. Can you publish it, or explain the hack case?

SzilBalazs commented 1 month ago

Looks like cses modified how testcases can be accessed, new url: https://cses.fi/view/1/ecf9c3c8ee0ce18cbcc322695da6a744b3dfa6a5a9494f16922b4dace171ca25 On pastebin: https://pastebin.com/rpFS7Nxn

maspypy commented 1 month ago

Thank you! I understand it.

maspypy commented 1 month ago

I have confirmed that the submission in question is now resulting in a TLE. Thank you!