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

Автор rng_58, история, 4 года назад, По-английски

Recently, I feel I've passed my peak as a competitive programmer, and ran out of sufficient energy/motivation to keep the top form and be prepared to win the next contest. I think I've done everything I can do as a competitive programmer, and now it's time to end my career as a professional (mind) sport player.

It was a great experience. I'd like to thank everyone involved in the community, especially:

  • Competitors. It was always nice to compete against you all!
  • Problem writers who gave great problems to the community.

I started my career as a competitive math-puzzle solver in 1999. The first contest was a local one named "junior sansu (arithmetic) olympiad". Since then, I enjoyed this sport a lot for 21 years.

In 2007, I started TopCoder, and it changed my life. The problems were great, and every single match of SRM felt like a once-in-a-life event. A lot of legends were competing there — Petr, tomek, ACRush, then tourist, and many more. I watched them on a screen, like a football boy watching Messi on TV. I dreamed to join them one day, and always stayed on practice rooms on TopCoder Arena and tried to improve. Imagine the moment when I finally reached the Finals, met those legends, and competed with them at the same stage!

Then I became an admin, first at TopCoder, then at AtCoder. Especially in AtCoder, I had a right to decide everything as the leader of the writers' team, and tried to make what I consider to be the ideal form of a competitive programming website. I tried to create a community where the legends and top competitors gather, and compete against each other for solving ad-hoc, math-puzzle-like, elementary, thinking-oriented problems, and newcomers who dream to be the star of the next generation join and practice. I hope you enjoyed the contests!

For now, I'll get some rest for a while, live a calm, non-competitive life, and gradually think what to do next. I'll stay in AtCoder and hope to keep in touch with the community in some form.

Good bye, and good luck to the community in the future!

UPD: thank you everyone for the comments!

Полный текст и комментарии »

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

Автор rng_58, история, 4 года назад, По-английски

This weekend, we will hold two AGC contests: AtCoder Grand Contest 050 (Good Bye rng_58 Day 1) and AtCoder Grand Contest 051 (Good Bye rng_58 Day 2). Both contests count for GP30 scores.

For these contests, we use problems that were originally prepared for the postponed World Tour Finals, plus some new problems, divided into two sets. Since we change the admin from next year, these contests will be rng_58's last contests as an author.

The point values will be:

  • Day 1: 500 — 800 — 1000 — 1300 — 1800 — 2000
  • Day 2: 500 — 800 — 1300 — 1800 — 2000 — 2400

Even though this is an online contest, we want to make it a special event like an onsite finals. Thus, we decided to make the participation right to this contest a special prize for those who reached 2000 in AtCoder. We are looking forward to your participation!

Полный текст и комментарии »

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

Автор rng_58, история, 4 года назад, По-английски

Let's hold an ARC Lockout Tournament. The idea is inspired by ecnerwala's Lockout tournaments and kenkoooo's ABC tournaments. This is not an official tournament, so there will be no prize; the winner gets the honor as the champion of the lockout tournament.

The rule is basically the same as ecnerwala's.

  • I use the actual points in the contest (like 300-400-500-600-700-800) to judge the winner.
  • Only the user with the earlier AC time gets the assigned score (tie-break by submission ID)
  • The time penalty doesn't matter.
  • In case of tie, the winner is the first one who reached that score (again the tie penalty doesn't matter).
  • In case both participants skip the round, the winner is the one with the higher rating at that time.

I don't want to mess up the results of rated participants with this format, so you need to be a red or above on AtCoder. If you want to participate, please reply this thread with your AtCoder handle by November 21st, 0:00, JST (that is 21 hours before the start of ARC 108). After that, the tournament bracket will be made in the 18452736 manner by ratings.

The first round is ARC 108, the second round is ARC 109, and so on.

UPD: I don't want to decrease writers because of this; if a match involves a writer or a tester, the result of the match is determined by the next ARC.

UPD: Thank you for the registration! Now the registration closed. Bracket You can add predictions now!

So, tomorrow is the match between Anadi and Golovanov399.

Полный текст и комментарии »

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

Автор rng_58, история, 4 года назад, По-английски

We will hold AtCoder Regular Contest 106.

We are looking forward to your participation!

Полный текст и комментарии »

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

Автор rng_58, история, 4 года назад, По-английски

We will hold AtCoder Regular Contest 105. From this contest, you don't need to choose the option "(with ACL)" to submit solutions with ACL. (The library is installed by default.)

The point values will be 200-300-500-600-700-900.

We are looking forward to your participation!

Полный текст и комментарии »

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

Автор rng_58, история, 4 года назад, По-английски

Hello. Today I announce three revolutions of AtCoder!

1. AtCoder Library (ACL)

We provide a collection of pre-written codes of various algorithms and data structures. I'll describe details in a separate post.

2. New Color Scheme

Previously, we decided colors by ratings. For example, gold for 3600 and above, silver for 3200 and above, red for 2800 and above, etc. However, it's not clear what the rating values mean, for example, 2800. If we design the rating system relatively well, in the short term the rating 2800 corresponds to a certain level. The skill required to reach 2800 today is probably similar to that of a year ago. However, the structure of the contests may change, the number of users may change, the average level of users may change, etc., and the exact value of ratings is very sensitive to these changes (and it may cause inflation/deflation).

Now I believe ranks are more robust against inflation/deflation and more suitable to decide colors, at least for the top people. It's clear what the $$$k$$$-th rank means — it means you are the $$$k$$$-th strongest person, and that corresponds to how likely you are to get titles in major tournaments, advance to onsite finals, get medals in ICPC/IOI, etc.

Here's the comparison of the new scheme and the old scheme. For now, the cutoff of gold/silver in the two schemes are very similar.

ColorOld RequirementNew Requirement
Tourist4000 rating1st rating rank
Gold3600 rating10th rating rank
Silver3200 rating30th rating rank
Bronze-100th rating rank
Red2800 rating2800 rating
Orange2400 rating2400 rating
Yellow2000 rating2000 rating
Blue1600 rating1600 rating
Cyan1200 rating1200 rating
Green800 rating800 rating
Brown400 rating400 rating
Gray0 rating0 rating

For the same reason, we added rank graphs on your profile page. Once you reach the 100th place, this kind of graph will appear and your journey to reach the first place starts. Good luck.

3. New ARC format

Currently, the bottleneck of holding ARC contests are the last (most difficult) problems. We are in short of high-quality problems of current ARC-F difficulty, and that's why ARCs are not frequent recently. Also, in AGCs and ARCs, we followed the "Quality > Quantity" style in an extreme way.

As a result, we now have really a lot of unused problems of difficulty around 600-700 points. Also, we have a lot of unused good problems, if not great, that deserve to be used in some contests.

I think it's time to start holding more contests using these problems. From October, we'll start holding ARCs with a bit lowered difficulty.

Internally, we are planning to classify problems as follows (in the order of difficulty from top to bottom):

Educational ProblemsAdhoc Problems
ABC 100-
ABC 200-
ABC 300R0
ABC 400R0
ABC 500R1
ABC 600R2
ABC 600R3
(don't use)R4
(don't use)R5

Then the basic guideline of an ARC set will be as follows:

AABC 100 or ABC 200
BR0 or ABC 300 or ABC 400
CR1
DR2
ER3
FR4 or R5

So, the difference of difficulties between ARCs and ABCs will be smaller. The major difference is the style of problems — ARCs will focus on more adhoc, thinking problems, while ABCs will focus on more "educational" part, like learning basic algorithms, typical techniques, etc.

Now we have more than 30 ARC sets on our stock this way. You can expect frequent ARCs in the near future.

Note that we don't change the format/style of AGCs — this change won't affect the "crowned" places.

Полный текст и комментарии »

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

Автор rng_58, история, 4 года назад, По-английски

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.

Полный текст и комментарии »

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

Автор rng_58, история, 4 года назад, По-английски

We will hold AtCoder Grand Contest 046. This contest counts for GP30 scores.

The point values will be 200-600-800-1100-1500-2000.

We are looking forward to your participation!

Полный текст и комментарии »

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

Автор rng_58, история, 4 года назад, По-английски

We will hold Tokio Marine & Nichido Fire Insurance Programming Contest 2020.

The point values will be 100-200-500-700-800-1000.

We are looking forward to your participation!

Полный текст и комментарии »

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

Автор rng_58, история, 4 года назад, По-английски

AGC is our de facto Div1 contest, traditionally rated for everyone. However, given the difficulty of the problems, we think we should set a lower bound for the rated range of AGCs. As an extreme example, it was enough to submit anything (even a compile error) to get a brown performance in the last AGC.

Currently, there are three implicit "divisions" in AtCoder:

  • Div 1+ (2800 <= rating). Equivalent to CF mid-high reds.
  • Div 1- (2000 <= rating < 2800). Equivalent to CF low reds, oranges, and purples.
  • Div 2 (rating < 2000). Equivalent to CF blues and below.

And there are three types of rated contests:

  • AGC: Targeted for Div 1 people, especially Div 1+.
  • ARC (or orange-circled, sponsored contest): Targeted for Div 1 people, especially Div 1-, with two easy problems attached.
  • ABC: An educational contest for Div 2 people.

We are planning to make AGC rated for its target range, and the next AGC will be rated for >= 2000. Still, everyone can participate in the contest and they appear in the standings as usual; it's just a matter of rating computation.

P.S. It's possible to reach Div 1 in one ARC contest, but ARCs are not very frequent and in case some strong newcomer misses it, it takes 4 ABCs to reach Div 1 (and it feels a bit too many). There are various ideas, which do you prefer?

  • Keep it. Ask them to participate in 1 ARC or 4 ABCs.
  • Make AGCs rated for >= 1200.
  • Make AGCs rated if your internal rating is >= 2000.
  • Make AGCs rated if you get performance >= 2000 at least once.

UPD: For the next contest we'll go with the second option.

Полный текст и комментарии »

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

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

Unfortunately, due to the new Corona Virus problem, we decided to postpone WTF 2020. In Japan, various sport events were cancelled recently (for example football matches). We discussed internally, and concluded that WTF should be postponed too. We are very sorry for the late decision.

However, we hope to reschedule the event and hold WTF 2020 in the future. We will announce the schedule again when the situation gets better.

Полный текст и комментарии »

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

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

We will hold Keyence Programming Contest 2020.

The point values will be 100 — 200 — 400 — 700 — 900 — 1100.

We are looking forward to your participation!

Полный текст и комментарии »

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

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

We will hold Dwango Programming Contest 6th.

The point values will be announced later.

We are looking forward to your participation!

Полный текст и комментарии »

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

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

We will hold DISCO Presents Discovery Channel Code Contest 2020 Qual.

The point values will be announced later.

We are looking forward to your participation!

Полный текст и комментарии »

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

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

We will hold NIKKEI Programming Contest 2019-2.

The point values will be announced later.

We are looking forward to your participation!

Полный текст и комментарии »

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

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

Sorry for the late announcement and unusual time. It was hard to find a good slot (some local marathon contest and SRM on Saturday, Open Cup on Sunday, sponsored ARC in the next week, TCO after that, etc.)

We hope to hold two more AGCs in this year (excluding this AGC), and guarantee at least one.

We will hold AtCoder Grand Contest 040. This contest counts for GP30 scores.

The point values will be 300 — 600 — 800 — 1100 — 1400 — 2200.

We are looking forward to your participation!

Полный текст и комментарии »

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

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

We will hold AtCoder Grand Contest 039. This contest counts for GP30 scores.

The point values will be announced later.

We are looking forward to your participation!

Полный текст и комментарии »

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

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

How to enter the contest?

The d1 link leads to ejudge.

Полный текст и комментарии »

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

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

We will hold AtCoder Grand Contest 038. This contest counts for GP30 scores.

The point values will be announced later.

We are looking forward to your participation!

Полный текст и комментарии »

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

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

We will hold Japanese Student Championship 2019 Qualification. (Despite its name, the contest is open for all international participants.)

The point values will be announced later.

We are looking forward to your participation!

Полный текст и комментарии »

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

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

Now all advancers are decided.

touristBelarus
PetrRussia
rng_58Japan
ecnerwalaUnited States
ACRushChina
scott_wuUnited States
mnbvmarPoland
snukeJapan
SpyCheeseRussia
Um_nikRussia
RomaWhiteUkraine
aidRussia
EgorGermany
yutaka1999Japan
jqdai0815China
uwiJapan

Полный текст и комментарии »

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

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

We will hold AtCoder Grand Contest 037. This contest counts for GP30 scores.

The point values will be announced later.

We are looking forward to your participation!

Полный текст и комментарии »

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

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

We will hold AtCoder Grand Contest 036. This contest counts for GP30 scores.

The point values will be announced later.

We are looking forward to your participation!

Полный текст и комментарии »

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

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

We will hold AtCoder Grand Contest 035. This contest counts for GP30 scores.

The point values will be announced later.

We are looking forward to your participation!

UPD: We are very sorry, due to an urgent trouble we delay the round by 30 minutes. UPD2: We fixed the trouble and the round will start from 21:30 JST. Again we are very sorry for the inconvenience.

Полный текст и комментарии »

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

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

We will hold diverta 2019 Programming Contest 2.

The point values will be announced later.

We are looking forward to your participation!

By the way, now you can reach here from AtCoder:

Полный текст и комментарии »

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