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

Автор Noam527, история, 12 часов назад, По-английски

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.

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

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

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

»
12 часов назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

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.

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

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.

»
11 часов назад, # |
  Проголосовать: нравится +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

  • »
    »
    10 часов назад, # ^ |
      Проголосовать: нравится 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.

»
11 часов назад, # |
  Проголосовать: нравится 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

»
8 часов назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

I would say that having a library prepared beforehand is fair game. Here are my arguments:

  • Everything templateable is already on the internet. If you don't have your own Dijkstra implementation, you are not on much worse position than other better prepared contestants. Searching for it would immediately yield you a code in your prefered language. In the nearest months, maybe even AI will be able to provide implementations for those boilerplate algorithms and data structures.

  • A template library is part of contestant preparation. Sure, you can use segment tree from the internet but having your own implementation can make you adaptable to more exotic use cases (let's say that the operation is xor by x, query max which you are unlikely to find on the internet).

  • Even if you forbid any outer source of code or library, one could argue that better prepared contestants have the code memorized and that's unfair because now they can implement some DS faster then others.

  • Preparing a library is a natural part of CP journey: while solving a set like CSES or studying classical textbooks like Cormen you discover a broad lore of widely applicable algorithms. While training, you are encouraged to implement them yourself and to save the implementations for later use.

  • I can't imagine implementing rare, large templates each time from scratch (like max flow, convex hull trick, simplex etc.). It would be a source of lots of bugs, WAs and frustration.

  • What about the overal template with macros, typedefs etc? Is the usage of such template unfair as well?

  • [edit] One more: selecting a template from library is rarely a crucial part of solving a problem. The library is intended to help with the most mundane and reapetable parts of problemsolving.

»
6 часов назад, # |
Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

I feel like you are shifting the point of a standard library a little bit. You don't need to create your own library to use algorithms. You can use somebody else's codebase. Or atcoder library, for example. The only advantage of a codeforces library would be that you don't need to copy-paste this code into your source file so it would save you a minute. I am not against it but I don't see it as any kind of important thing. I've never used atcoder library myself but I appreciate the fact that when someone uses it, it makes it easier to see what is actually new in the solution and what is standard. See where the actual solution idea is.

You are talking about the fact that using plain c++ is not a part of the sport but in my opinion, it is a part of the sport! Yes, std::set is a data structure, but I get much more joy if I can solve a problem using std::set instead of a segment tree. This is a so-called "no data structures" achievement. There are these artificial "constraints" but they are the beauty of the sport. Plus, I really enjoy reading the libraries of other people sometimes. It is very cool to see how people put a lot of thought into trying to figure out the most general and easy-to-use black-box implementations of algorithms and data structures.

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

Imo, part of the fun of competitive programming is googling similar problems during contests and copy-pasting their solutions together. A standard library would kinda take away from that.

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

I think it's up to contestants to prepare their library in their own familiar coding style.

Atcoder's library is convenient and fast, but many files are ridiculously long because of extreme optimizations. It makes little sense to print it and bring into ICPC contest floors: you won't want to type pages of convolution template before starting a polynomial problem.

Our team have two different segtree templates, each written by one of the two main coders.