rng_58's blog

By rng_58, history, 2 weeks ago, In English

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.

Read more »

 
 
 
 
  • Vote: I like it
  • +210
  • Vote: I do not like it

By rng_58, history, 5 weeks ago, In English

We will hold AtCoder Regular Contest 106.

We are looking forward to your participation!

Read more »

 
 
 
 
  • Vote: I like it
  • +168
  • Vote: I do not like it

By rng_58, history, 7 weeks ago, In English

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!

Read more »

 
 
 
 
  • Vote: I like it
  • +64
  • Vote: I do not like it

By rng_58, history, 3 months ago, In English

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.

Read more »

 
 
 
 
  • Vote: I like it
  • +598
  • Vote: I do not like it

By rng_58, history, 3 months ago, In English

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.

Read more »

 
 
 
 
  • Vote: I like it
  • +1385
  • Vote: I do not like it

By rng_58, history, 5 months ago, In English

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!

Read more »

 
 
 
 
  • Vote: I like it
  • +129
  • Vote: I do not like it

By rng_58, history, 6 months ago, In English

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!

Read more »

 
 
 
 
  • Vote: I like it
  • +124
  • Vote: I do not like it

By rng_58, history, 6 months ago, In English

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.

Read more »

 
 
 
 
  • Vote: I like it
  • +208
  • Vote: I do not like it

By rng_58, history, 9 months ago, In English

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.

Read more »

 
 
 
 
  • Vote: I like it
  • +425
  • Vote: I do not like it

By rng_58, history, 10 months ago, In English

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!

Read more »

 
 
 
 
  • Vote: I like it
  • +68
  • Vote: I do not like it

By rng_58, history, 11 months ago, In English

We will hold Dwango Programming Contest 6th.

The point values will be announced later.

We are looking forward to your participation!

Read more »

 
 
 
 
  • Vote: I like it
  • +123
  • Vote: I do not like it

By rng_58, history, 12 months ago, In English

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!

Read more »

 
 
 
 
  • Vote: I like it
  • +70
  • Vote: I do not like it

By rng_58, history, 13 months ago, In English

We will hold NIKKEI Programming Contest 2019-2.

The point values will be announced later.

We are looking forward to your participation!

Read more »

 
 
 
 
  • Vote: I like it
  • +52
  • Vote: I do not like it

By rng_58, history, 13 months ago, In English

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!

Read more »

 
 
 
 
  • Vote: I like it
  • +166
  • Vote: I do not like it

By rng_58, history, 14 months ago, In English

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!

Read more »

 
 
 
 
  • Vote: I like it
  • +32
  • Vote: I do not like it

By rng_58, history, 14 months ago, In English

How to enter the contest?

The d1 link leads to ejudge.

Read more »

 
 
 
 
  • Vote: I like it
  • +39
  • Vote: I do not like it

By rng_58, history, 14 months ago, In English

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!

Read more »

 
 
 
 
  • Vote: I like it
  • +120
  • Vote: I do not like it

By rng_58, history, 15 months ago, In English

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!

Read more »

 
 
 
 
  • Vote: I like it
  • +96
  • Vote: I do not like it

By rng_58, history, 15 months ago, In English

Now all advancers are decided.

touristBelarus
PetrRussia
rng_58Japan
ecnerwalUnited States
ACRushChina
scott_wuUnited States
mnbvmarPoland
snukeJapan
SpyCheeseRussia
Um_nikRussia
RomaWhiteUkraine
aidRussia
EgorGermany
yutaka1999Japan
wxhtxdyChina
uwiJapan

Read more »

 
 
 
 
  • Vote: I like it
  • +86
  • Vote: I do not like it

By rng_58, history, 15 months ago, In English

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!

Read more »

 
 
 
 
  • Vote: I like it
  • +142
  • Vote: I do not like it

By rng_58, history, 16 months ago, In English

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!

Read more »

 
 
 
 
  • Vote: I like it
  • +198
  • Vote: I do not like it

By rng_58, history, 17 months ago, In English

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.

Read more »

 
 
 
 
  • Vote: I like it
  • +109
  • Vote: I do not like it

By rng_58, history, 17 months ago, In English

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:

Read more »

 
 
 
 
  • Vote: I like it
  • +146
  • Vote: I do not like it

By rng_58, history, 18 months ago, In English

I do this as usual.

HandleCountry
ACRushChina
rng_58Japan
touristBelarus
ksun48Canada
RadewooshPoland
bmerrySouth Africa
EgorGermany
Marcin_smuPoland
cki86201South Korea
dacin21Switzerland
mnbvmarPoland
ecnerwalaUnited States
SpyCheeseRussia
krijgertjeNetherlands
eatmoreRussia
EndagorionRussia
ErrichtoPoland
kevinsogoPhilippines
yutaka1999Japan
aintaSouth Korea
KANRussia
xiaowuc1United States
semiexpJapan
qwerty787788Ukraine
dreamoonTaiwan

Read more »

Tags gcj
 
 
 
 
  • Vote: I like it
  • +112
  • Vote: I do not like it

By rng_58, history, 18 months ago, In English

Has it changed since last year?

Now I can't run it for last year's tasks (Judge return code: 255)

It works fine for this year's tasks.

Read more »

 
 
 
 
  • Vote: I like it
  • +25
  • Vote: I do not like it