### yosupo's blog

By yosupo, history, 4 years ago,

Hello, codeforces!

Today, I introduce yet another online judge, Library-Checker!

As the name suggests, the object of this site is checking your libraries. The problems are "Implement RMQ", "Enumerate Primes", "Exp of Formal Power Series", "Decompose a graph into three-connected components"... and so on.

All problems are managed by me. In other words, I'm the admin of this site.

Anything of problems (testcases, solutions, generator, ...) are managed in github. It means,

• Anyone can add problems add testcases. Already most of the problems are prepared by other competitive programmers.
• Testcases are stronger and stronger with time (ideally).

(For competitive programmers who can do "real" programming: Have you ever think that "I want to test my library in CI..."? This judge will achieve your hope! Please refer verification-helper)

• +902

| Write comment?
 » 4 years ago, # |   +8 Auto comment: topic has been updated by yosupo (previous revision, new revision, compare).
 » 4 years ago, # |   +29 Nice idea.
 » 4 years ago, # |   +58 This is awesome, I was just thinking a few weeks back that I wish something like this existed when I wanted to test my maths library. Thanks!
 » 4 years ago, # |   +26 yosupo In the solution for sparse determinant, what's the reasoning for line 412? if (!u.freq(0)) return 0; I know that the characteristic polynomial for the matrix has constant term 0 iff the matrix has determinant 0 (but I don't see why this implies correctness).Also, is there somewhere I can read about this technique?
•  » » 4 years ago, # ^ | ← Rev. 3 →   +15 https://yukicoder.me/wiki/black_box_linear_algebra This is an article about "black box linear algebra (and sparse determinant)" written by anta. I don't know another article about this technique, though this is japanese... at least, you can find references(参考文献).In my code, $u$ is a linear recurrence of $l (AD)^i r$ for a given matrix $A$, and random vectors $l, r$, and a random diagonal matrix $D$. $u$ is the divisor of an eigen polynomial of $AD$ because the eigen polynomial is also the linear recurrence of $l (AD)^i r$(Cayley–Hamilton theorem).Therefore if $u$ has $0$ as a root, the eigen polynomial of $AD$ has $0$ as a root, and $\mathrm{det}(A)$ is $0$ because $\mathrm{det}(D) \neq 0$. Is this an answer of your question?
•  » » » 4 years ago, # ^ |   +10 That makes sense, thanks!
 » 4 years ago, # |   +31 This is amazing. Why didn't you told me? ;)
•  » » 4 years ago, # ^ |   +10 I look forward to your stream
 » 4 years ago, # |   +41 Planarity check, please.
•  » » 4 years ago, # ^ |   +38 Anyone can add problems add testcases.
•  » » » 4 years ago, # ^ |   +26 I think that this doesn't change my message xd
•  » » 4 years ago, # ^ |   0 Sounds too easy, let's add edge add/delete query
 » 4 years ago, # |   0 Amazing
 » 4 years ago, # | ← Rev. 2 →   0 Can you make the test cases available for download? Since this is intended to help people test their code it might help people debug. I see that the generator code is available for download on Github but it would be easier if we can just download the tests directly.
•  » » 4 years ago, # ^ |   +46 Thank you for suggestion!Actually this service is sustained by my pocket money and downloading big data consume money... so I don't plan to implement this function now, sorry.But I maintenance Github as easy to generate test case. And I support you if you have some trouble.
•  » » » 4 years ago, # ^ |   0 I see, thank you for making such a cool resource!
 » 4 years ago, # |   0 so how to "Decompose a graph into three-connected components" ...
•  » » 4 years ago, # ^ |   +26
•  » » » 4 years ago, # ^ |   0 fabulous! thanks!
•  » » » » 4 years ago, # ^ |   0 You can also test your code on this problem!
•  » » » » » 4 years ago, # ^ |   0 i kinda recall there was a problem on codechef that is related but can't remember.
 » 4 years ago, # |   0 Where can I learn about polynomials ? I have read article about polynomials on cp-algorithms.com. Can anyone suggest any other resources ?
•  » » 4 years ago, # ^ |   +3
•  » » » 4 years ago, # ^ |   0 Thank you!
 » 4 years ago, # | ← Rev. 2 →   +13 Hello! Can someone please send a resource for an algorithm that is fast enough to solve https://judge.yosupo.jp/problem/k_shortest_walk? Thanks! (In english)
•  » » 4 years ago, # ^ |   +18 Here.I've implementated it before and it's not that hard.
•  » » » 4 years ago, # ^ |   +6 Thanks!
 » 4 years ago, # | ← Rev. 3 →   -7 Ignore this message
 » 4 years ago, # |   0 What does PE mean while judging the code??
 » 4 years ago, # |   +9 The site is very cool. In fact, a few days ago I was discussing that idea with a friend because it is true that many times it is necessary, mainly when you are learning new algorithms or data structures and you want to try them on something very classic, and then, afterwards, begin to apply them to more complex things.
 » 4 years ago, # |   -15 Thank you for providing this resource, it is amazing. From the perspective of a newbie, I had a suggestion — to add some sort of rating to the problems present on the Library-Checker site. Regards
•  » » 4 years ago, # ^ |   +86 The number of ACs indicates the difficulty.For newbies: Be careful, you cannot use this site for increasing your rating. Most of problems are useless for other sites, especially atcoder (and codeforces rounds coordinated by antontrygubO_o). I provide this site for library addicts.
 » 4 years ago, # |   0 My solution is getting tle in Associative Array. I am using map.What should I do?
•  » » 4 years ago, # ^ |   0 At first, you are not using map, but unordered_map (it's complexity is $O(Q^2)$). And at second, you read from empty file (ONLINE_JUDGE is not defined on this site).
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Ok, I did 2 submissions, one using unordered map and other using map. Thanks for the help, I will comment that part.
 » 4 years ago, # |   0 I have started doing Library Checker, But I am finding it difficult to see the cases where my solutions goes wrong. Can somebody tell me how to see the test cases. Thanks
 » 3 years ago, # |   +11 Some of my solutions, despite being accepted, are shown blue instead of green. What does that mean?
 » 2 years ago, # |   +43 Could you implement a "show only fastest submission of each user" toggle for the "fastest" tab? In most problems, most of the fastest submissions are from just a few people, and the codes by a single person are most often very similar to each other.
 » 13 months ago, # |   0 I am not able to submit any code. Tried it from two machines. Please fix!
 » 11 months ago, # |   0 Recently all of my solved problems turned blue (accepted with old data). Is this expected? Am I supposed to rejudge all of my submissions?
 » 4 months ago, # |   0 I recently came across this site due to some discussions/debates (which may or may not have involved gaming, alcohol, and over-sized cows) about the actual effectiveness of the V^{1/2}E time matching algorithms.It ended up being very useful for getting a sense of the effectiveness of (heursitics versions of) these on bipartite graphs. So I'm now wondering if there is any chance that the general graph matching data sets can be augmented to the same sizes as the bipartite ones? (V <= 10e5, E <= 2e5?). The current fastest runtimes on there are all 1ms, while time limits are 5000ms.
 » 4 months ago, # |   0 Site is down, please check.