AtCoder Library

Revision en2, by rng_58, 2020-09-07 17:40:44

Recently, the number of algorithms and data structures we use in competitive programming are rapidly growing. It's a nice thing: by using more algorithms, the variety of possible problems gets wider, and we can enjoy more problems.

On the other hand, before reaching adhoc, thinking-oriented part of this competition, we have to spend more and more time to learn algorithms. Sometimes a problem asks matching on general graphs; you have to find a paper describing it, read it, and implement its really complicated algorithm. Or sometimes you have to spend time tuning your library by a constant factor. Or sometimes you use multiple pre-written codes together, the variable names collide, and get annoyed.

Until now, I basically rejected all problems that require pre-written codes of complicated algorithms because I don't like these things. For example, we never used segment trees with lazy propagation in our contests. However this way we can't use otherwise interesting problems and it may limit the variety of problems.

What to do with this situation? There is a great example that solved this issue: C++ STL's set. It actually hides a monstrous data structure inside, but thanks to set we can use it as an oracle and it can be used in many tasks.

For these reasons, we decided to prepare oracles of various algorithms on our side and enable contestants to focus on the interesting part of problems.

All the codes were implemented by yosupo, and testings were done by rng_58, maroonrk, DEGwer. We wanted to make sure that you can use them as oracles, so we prepared a detailed document that describes the usage of these libraries.

As an example, here is the code that computes the convolution of two given arrays:

#include <atcoder/convolution>
#include <cstdio>

using namespace std;
using namespace atcoder;

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<long long> a(n), b(m);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &(a[i]));
    }
    for (int i = 0; i < m; i++) {
        scanf("%lld", &(b[i]));
    }

    vector<long long> c = convolution(a, b);

    for (int i = 0; i < n + m - 1; i++) {
        printf("%lld ", c[i]);
    }
    printf("\n");

    return 0;
}

As you see, it makes the code much cleaner. Of course, this library is installed on the AtCoder server, and you can use it in our contests.

Don't misunderstand us — we are not trying to promote librarish problems. It's the other way around. We are trying to make librarish problems less librarish.

In AGCs/ARCs, until now, we chose problems by comparing the amount of thinking and the amount of implementation including the library part. From now, we can measure the amount of implementation excluding the library part, but that's the only change. For example, we won't use "paste a segtree, then do more implementation after that" kind of problems. We may use "think a lot, paste a segtree, add small amount of code and that's all" kind of problems. Of course, I expect the majority of our problems will still be non-library problems (except for the thematic contest announced below). We will keep the "easy implementation" rule in the future — the next admin maroonrk even says that in order to guarantee that, he is planning to write his solutions to all problems in Python.

Link to various places:

The two ACL contests will be ARC-rated (rated for 1200-2799, 150 minutes, but we may change the lower bound / duration later). Even though the intended solutions of the majority of problems in these contests use ACL, the main part will be the thinking part. These contests may contain some dummy tasks that are irrelevant to the library, so don't try to think problems like "ok, maybe this task requires that library, so the solution should be...".

Now we have two questions for the community:

  • The first version of ACL only contains relatively basic algorithms that many top people already have. Should we include more advanced algorithms (like matchings on general graphs)? Our main concern is the unfairness against Java users.
  • What to do with geometry? Currently we are not sure what's the best way to handle precision issues.
Tags atcoder, library

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English rng_58 2020-09-07 17:40:44 17
en1 English rng_58 2020-09-07 17:34:11 4722 Initial revision (published)