Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

yosupo's blog

By yosupo, history, 2 months ago, In English,

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).

Let's enjoy your library maintenace!

(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)

 
 
 
 
  • Vote: I like it
  • +842
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Auto comment: topic has been updated by yosupo (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

Nice idea.

»
4 weeks ago, # |
  Vote: I like it +58 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

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 weeks ago, # ^ |
    Rev. 3   Vote: I like it +15 Vote: I do not like it

    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 weeks ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      That makes sense, thanks!

»
4 weeks ago, # |
  Vote: I like it +31 Vote: I do not like it
»
4 weeks ago, # |
  Vote: I like it +41 Vote: I do not like it

Planarity check, please.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Amazing

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it +46 Vote: I do not like it

    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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

so how to "Decompose a graph into three-connected components" ...

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can I learn about polynomials ? I have read article about polynomials on cp-algorithms.com. Can anyone suggest any other resources ?

»
2 weeks ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

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)

»
2 weeks ago, # |
Rev. 3   Vote: I like it -7 Vote: I do not like it

Ignore this message