Блог пользователя Noam527

Should Codeforces Have a Standard Library?
Автор Noam527, история, 4 часа назад, По-английски

Recently I started making my own library for competitive programming; mainly for our ICPC notebook but also to use in online contests.

While I like the advantage that it gives to me, in my opinion it is against the sport. I don't think we should compete on who has dijkstra ready to be copy-pasted, and who needs to write it from scratch.

Obviously everyone can have their own library prepared, so that they will never have to code up dijkstra again, but this just means that the "quality of life" is worsened — why should we assume that everybody needs to do identical preprocessing to be on equal grounds? This just means we require more work from everybody in the community. Should we also ban vectors and sets and let everybody code their own?

The only downside I see of this is the sheer amount of work required to be 100% sure that the library is bug-free. Of course, it is still possible, just like std::set does it.

What do you think? I hope this post stirs up some discussion on this and maybe we'll improve the global experience from the sport.

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
4 часа назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

There is already the atcoder library which implements a lot of data structures and algorithms.

→ Ответить
»
4 часа назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

Should we also ban vectors and sets and let everybody code their own?

Unironically yes. Maybe we won't get tons of retarded blogs like "why my solution with unordered_map fails with TL" or "why my solution with deque fails with ML" if people actually implement and understand how data structures work.

→ Ответить
»
3 часа назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Don't forget to add these algs to the library:

  • 5D incremental convex hull in $$$O(n\log n)$$$ + 5D onion decomposition in $$$O(n\log^2 n)$$$
  • 3D Voronoi diagram in expected $$$O(n\log n)$$$
  • 4D online half-hyperspace intersection in $$$O(\log n)$$$ per query
  • Fast arbitrary precision floating point numbers for super precise calculations
  • Bigint as a consequence of the previous point
  • FFT, Newton's method, Burnikel-Ziegler-Verfahren algorithm as a consequence of the previous point
  • KD tree, Vantage point tree, R-tree for getting AC with $$$O(n^2)$$$ solutions
  • Visual debugging tool for all that mess

these are only $$$1\%$$$ of "Geometry" topic. Good luck in implementation xD xD xD.

→ Ответить
»
2 часа назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

You will still need to explore what does the codeforeces library have then. Someone will know about some functions, someone won't. Still unfair xd

Also, we need that library for all the possible contest languages? Creating a large library only for one language is also very unfair

→ Ответить
  • »
    »
    2 часа назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    With similar documentation to cpp's standard library, it is the same as some people knowing about rbegin of set or _Find_first of bitset.

    I don't claim to eliminate this type of unfairness, I think it is impossible — you can prepare your own very-particular segment tree and use it. The goal is to minimize this difference that is based on non-problemsolving skills.

    However, regarding the supported languages you are right, I didn't think about this. It means the amount of work is multiplied. Perhaps this means that this should be a community project rather than handled by a few select people.

    → Ответить
»
2 часа назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think it can be one large library where we all as users can contribute to improve it, it might be a great idea

→ Ответить