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

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

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.

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

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

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

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

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

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.

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

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

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится -7 Проголосовать: не нравится

    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.

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

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

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.

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

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.

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

    I disagree with some of your points, mainly that the difference is not only the minute it takes to copy-paste, but rather that having such a library will remove the process of everybody making their own + will cause more people to be aware of what they're missing against other contestants.

    However, given that there are these well known libraries like atcoder's, and that it is (apparently) common for people to use libraries, I see how the difference it would make is not worth the effort. I wasn't aware of these two facts, maybe I've been living under a rock for the past few years.

    So while I'm still not against the library, it is probably not as important as it seemed to me beforehand.

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

      such a library will remove the process of everybody making their own

      I still don't get it. If you don't want to make your own library, you don't have to now. And if there will be a codeforces library, anybody who wants to still will be able to make one. I don't understand how adding a codeforces library is not isomorphic to the current situation + copy-paste.

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

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.

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится -21 Проголосовать: не нравится

    is this true? hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh

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

      Well it is kind of rare. There was this one leetcode contest problem that I solved that was just copy-pasted from a bunch of online places. Also, idk exactly how to find the bitwise $$$OR$$$ of numbers in the range $$$l...r$$$ very quickly, so I copy pasted that for some problem here a while ago. Also, I noticed quite a bit less inane questions in the cf comment sections today. It is okay, though. No one can work hard every day $$$24/7$$$.

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

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

I think the library isn't necessary. In fact most basic templates are very short, so the extra time spent on writing templates is not significant compared to the time you actually use to figure out the solution(I can write dij in 1~2min and segtree in 3min). For complicated/long templates(e.g. floorsum/FFT/flows/bignum/toptree), everyone uses their own library, so this makes no difference.

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

    What is dij? Dijkstra?? First time I'm seeing this shortcut, lol.

    And btw, while the time to write short templates may be negligible, you still can make a bug while writing it, so it's better have them in your library too. And even small time saves may matter in the competition: just remember all the times when you solved a problem in a few last minutes.