### rng_58's blog

By rng_58, history, 11 days ago, ,

AtCoder Grand Contest 028 will be held on Saturday (time). The writer is maroonrk. This contest counts for GP30 scores.

Contest Announcement

Contest duration: 150 minutes

The point values will be announced later.

Let's discuss problems after the contest.

•
• +125
•

By rng_58, history, 6 weeks ago, ,

Sorry for the long blank of AGC. Meanwhile there were lots of big tournaments like GCJ, TCO, FHC. Some of our writers were also busy with helping IOI in Japan. I hope we will be able to hold AGCs more frequently from now.

AtCoder Grand Contest 027 will be held on Saturday (time). The writers are camypaper and sugim48. This contest counts for GP30 scores.

Contest Announcement

Contest duration: 140 minutes

The point values will be 200 — 700 (400) — 900 — 1100 — 1300 — 1900.

Let's discuss problems after the contest.

•
• +126
•

By rng_58, history, 2 months ago, ,

CF Handle Country
1. matthew99China
2. Um_nikRussia
3. ecnerwalaUnited States
4. dotoryaSouth Korea
5. s-quarkChina
6. majkCzech Republic
7. PetrRussia
9. touristBelarus
10. LHiCRussia
11. aintaSouth Korea
12. qwerty787788Ukraine
13. rng_58Japan
14. KostromaRussia
15. ErrichtoPoland
16. scott_wuUnited States
17. cki86201South Korea
18. RomaWhiteUkraine
20. ilyakorSwitzerland
21. vepifanovRussia
22. ikatanicCroatia
23. mareksomPoland
24. dreamoonTaiwan
25. natsugiriJapan

•
• +130
•

By rng_58, history, 3 months ago, ,

I'm preparing for upcoming GCJ Finals. This year GCJ supports only Linux, and I want to learn how to compile solutions on Linux (I think I used it 9 years ago in IOI but completely forgot how to do that...).

Suppose that A.cpp, Main.java, A.py are source codes, A.in is the input, and you want to output to A.out.

On Windows+Cygwin, I usually do the following:

• g++ -Wl,--stack,268435456 A.cpp -O2
• ./a < A.in | tee A.out
• javac Main.java
• java Main < A.in | tee A.out
• python A.py

What commands do the same things on Linux?

The following things are installed on the machine:

• Debian Linux 9.4
• C++ 6.3.0
• Java 7 2.2.5
• Python 2 2.7.13

•
• +52
•

By rng_58, history, 3 months ago, ,

AtCoder Grand Contest 026 will be held on Saturday (time). The writer is sugim48 and yosupo. This contest counts for GP30 scores.

Contest Announcement

Contest duration: TBD (about 2 hours)

The point values will be announced later.

Let's discuss problems after the contest.

•
• +151
•

By rng_58, history, 4 months ago, ,

In this post I introduce the existence of https://beta.atcoder.jp/. It's a bit more advanced than atcoder.jp, and usually it's also faster to load.

This is an example of beta version of contest page (tomorrow's ARC). For example you can filter your friends in the standings. Please use it!

•
• +163
•

By rng_58, history, 4 months ago, ,

I do this, as usual.

GCJ Top 25:

CF Handle AtCoder Handle Country
1. ErrichtoErrichtoPoland
2. ifsmirnovifsmirnovRussia
3. Golovanov399Golovanov399Russia
4. eatmoreeatmoreRussia
5. pashkapashkaRussia
7. AhyangyiChina
8. semiexpsemiexpJapan
9. zemenzemenRussia
10. jcvbjcvbChina
11. rng_58rng_58Japan
12. JacobJacobRussia
13. dario2994dario2994Italy
14. wingerwingerUnited States
15. owo (or OO0OOO00O0OOO0O00OOO0OO? I'm not sure)apiad?China
16. kcm1700kcm1700South Korea
17. msg555United States
18. touristtouristBelarus
19. dacin21dacin21Switzerland
20. vepifanovvepifanovRussia
22. SyloviaelyKujouKaren?China
23. LHiCLHiCRussia
24. PavelKunyavskiykunyavskiyRussia
25. overtrollcospleermusoraRussia

DCJ Top 20:

CF Handle AtCoder Handle Country
1. ErrichtoErrichtoPoland
2. mareksommareksomPoland
4. qwerty787788qwerty787788Ukraine
5. TejsDenmark
6. sevenkplussevenkplusChina
7. rng_58rng_58Japan
8. tomekPoland
9. kevinsogokevinsogoPhilippines
10. pparysPoland
11. ecnerwalecnerwalUnited States
12. EgorEgorGermany
13. eddy1021eddy1021Taiwan
14. faguGermany
15. krismazkrismazPoland
16. darnleydarnleyRussia
17. snukesnukeJapan
18. TakanashiRikkaKujouKaren?China
20. pashkapashkaRussia

•
• +175
•

By rng_58, history, 5 months ago, ,

AtCoder Grand Contest 025 will be held on Sunday (time). The writer is yutaka1999. This contest counts for GP30 scores.

Contest Announcement

Contest duration: TBD (about 2 hours)

The point values will be announced later.

Let's discuss problems after the contest.

•
• +61
•

By rng_58, history, 5 months ago, ,

AtCoder Grand Contest 024 will be held on Sunday (time). The writer is DEGwer. This contest counts for GP30 scores.

Contest Announcement

Contest duration: 130 minutes

The point values will be 300 — 500 — 700 — 1100 — 1200 — 2300.

Let's discuss problems after the contest.

•
• +106
•

By rng_58, history, 6 months ago, ,

AtCoder Grand Contest 023 will be held on Saturday (time). The writer is maroonrk. This contest counts for GP30 scores.

Contest Announcement

The point values (and duration) will be announced later.

Let's discuss problems after the contest.

•
• +100
•

By rng_58, history, 6 months ago, ,

We are planning to introduce a division system to AtCoder in the near future.

Here are our current plans (but this is tentative, we may change it based on your feedback):

• The division cutoff is 2000. I think this is about the same as CF's 1900.

• We'll hold div2 contests (called ABC) every week. Usually, 100 minutes and 5 tasks: 100, 200, 300, 400-500, 600-700. Rated for 0-2000.

• Sometimes we'll hold div1 contests. There are two types of div1 contest: AGC and ARC. The first two tasks are shared with div2.

• ARC: Usually 100 minutes and 4 tasks: 400-500, 600-700, 800-900, 1000-1200. Rated for 2000-2800.

• AGC: Similar to current AGC. Rated for 2000-inf.

One major problem is that even strong people have to spend a few matches in Div2. Two "red performance" is good enough to reach Div1. Is it fine?

For example, it says that a gray coder solves a 200-point problem with probability 63%. Note that we use "estimated rating" instead of actual rating for this table (i.e., we don't subtract 1200 from newcomer's rating).

•
• +84
•

By rng_58, history, 7 months ago, ,

Since nobody posts it, I do.

C: Can we solve it faster than ?

B: Is there a simple way to solve this? We want to count the number of integers that appear odd number of times in a given range. To do this, we can use bitset for frequent numbers and sweepline + data structure for rare numbers, but it looked much harder than some other tasks...

•
• +29
•

By rng_58, history, 7 months ago, ,

E: I assumed that the answer is either at most N or infinity. Why is this true?

G: Is there a solution that doesn't require reading papers (or at least reading the wikipedia article mentioned in the statement)? I heard that there's a paper that describes the solution.

•
• +38
•

By rng_58, history, 8 months ago, ,

AtCoder Grand Contest 021 will be held on Saturday (time). The writer is degwer. This contest counts for GP30 scores.

Contest Announcement

The point values will be announced later.

Let's discuss problems after the contest.

•
• +120
•

By rng_58, history, 9 months ago, ,

We've just rescheduled our contests.

Next Saturday, we'll hold a long (most probably 5 hours, but it is not finalized yet) contest on AtCoder. Note that the start time is unusual: please check here.

The problems are based on one of the problemsets of Petrozavodsk camp. If you are a participant of Petrozavodsk camp, please don't participate in this contest. And of course, please keep the problems secret!

This is a rated contest for everyone, and this contest counts for GP30 scores. If you are a Petrozavodsk participant and you care GP30 scores, please let me know. We'll make sure that you won't get disadvantages (please check here, we'll handle you as a writer, i.e., increase the value of Y by one).

The writers are japan02 team (yosupo, sugim48, sigma425).

Note that AGC 021 was postponed to avoid collision with an Open Cup round.

UPD: the contest is actually 5 hours. contest link

•
• +203
•

By rng_58, history, 10 months ago, ,

AtCoder will hold a new onsite contest called AtCoder World Tour Finals 2018.

If you get the top 30 places in AGCs (and maybe some other types of contests), you will get GP30 scores. Eight people with the highest total GP30 scores in 2018 (except for people under 18) will be invited to Japan, probably in February 2019. We will cover flights and hotels. There's no upper bound for the age. You can participate in the finals even if you are employed.

Here's the total GP30 scores in 2017:

Rank Handle Score
1tourist870
2Um_nik519
3W4yneb0t514
4LHiC480
5Petr417
6ksun48347
7yutaka1999331
8V--o_o--V292

UPD: Added detailed information at the bottom of https://atcoder.jp/post/171.

•
• +526
•

By rng_58, history, 10 months ago, ,

You are given the first n (or n + 1 if necessary) terms of a former power series P(x) = c0 + c1x + c2x2 + .... What operations can be performed efficiently?

• Obviously, P(x) + Q(x), P(x) - Q(x), P'(x), , kP(x) for a given constant k, can be done in O(n).

• P(x)Q(x) can be done in O(nlogn) by FFT.

• can be done in O(nlogn): Link, check problem E

• can be done in O(nlogn): Link, check problem E

• exp(P(x)) can be done in O(nlogn): Link, check Figure 1, left

• Open: Can we do more complicated operations like P(Q(x)), P(x)1 / k, sin(P(x)), arcsin(P(x)), etc.? Are there other important operations?

• Probably a bit related to the computation of : when we are given two big decimal number x and y, can we compute x / y?

•
• +319
•

By rng_58, history, 11 months ago, ,

The onsite event of CODE FESTIVAL 2017 will start soon. There will be four contests during the event:

• Final Round. This is the main contest.

• Three rounds of Elimination Tournaments 1 2 3

All contests will have parallel rounds. Only Final will be rated (and corresponding parallel round will be rated too).

Check the schedule of the contests at https://atcoder.jp/.

UPD: Now the final standings is available at https://beta.atcoder.jp/contests/cf17-final/standings.

Congratulations to winners:

•
• +99
•

By rng_58, history, 11 months ago, ,

Does anyone use testlib on cygwin + g++?

It gives a compilation error at the 434th line:

_setmode(_fileno(file), O_BINARY); 

I know two ways to fix this issue:

• Comment out the 434th line. However, it disables this line and I'm not sure whether this is a good way.

• Add <io.h> to testlib. However, it works only on Windows.

How to fix the compilation error in a better way?

•
• +29
•

By rng_58, history, 12 months ago, ,

CODE FESTIVAL 2017 Qualification Round C will be held on Sunday (time). The writers are sugim48 and wo_.

Contest Announcement will be posted later.

This is one of the three qualification rounds of CODE FESTIVAL. In total, 20 foreign students will qualify in three rounds (Check the official site for detailed rules). If you are eligible for the onsite contest, please don't forget to fill the form at https://krs.bz/rhd-itm/m/codefes2017_en. Please check the detail of the tournament at http://codeforces.com/blog/entry/53502.

The contest duration is 2 hours, and there will be 6 problems. The first 4 problems are mainly used for choosing domestic students and much easier than other tournament competitions. However, we added two more problems and we hope these are interesting and challenging enough for choosing 20 qualifiers. Note that there is no time penalty for incorrect submissions. The time penalty is MAX, not SUM.

The point values are 100 — 200 — 400 — 700 — 1600 — 1800. If you are unfamiliar with AtCoder System, 2X-point problem in AtCoder is as hard as TopCoder's d1 X-point problem.

Let's discuss problems after the contest.

•
• +61
•

By rng_58, history, 13 months ago, ,

CODE FESTIVAL 2017 Qualification Round B will be held on Sunday (time). The writers are maroonrk, snuke, and myself.

Contest Announcement

This is one of the three qualification rounds of CODE FESTIVAL. In total, 20 foreign students will qualify in three rounds (Check the official site for detailed rules). If you are eligible for the onsite contest, please don't forget to fill the form at https://krs.bz/rhd-itm/m/codefes2017_en. Please check the detail of the tournament at http://codeforces.com/blog/entry/53502.

The contest duration is 2 hours, and there will be 6 problems. The first 4 problems are mainly used for choosing domestic students and much easier than other tournament competitions. However, we added two more problems and we hope these are interesting and challenging enough for choosing 20 qualifiers. Note that there is no time penalty for incorrect submissions. The time penalty is MAX, not SUM.

The point values are 100 — 200 (100) — 500 — 700 — 1600 — 1600. If you are unfamiliar with AtCoder System, 2X-point problem in AtCoder is as hard as TopCoder's d1 X-point problem.

Let's discuss problems after the contest.

•
• +41
•

By rng_58, history, 13 months ago, ,

CODE FESTIVAL 2017 Qualification Round A will be held on Saturday (time). The writer is sugim48 and DEGwer.

Contest Announcement

This is one of the three qualification rounds of CODE FESTIVAL. In total, 20 foreign students will qualify in three rounds (Check the official site for detailed rules). If you are eligible for the onsite contest, please don't forget to fill the form at https://krs.bz/rhd-itm/m/codefes2017_en. Please check the detail of the tournament at http://codeforces.com/blog/entry/53502.

The contest duration is 2 hours, and there will be 6 problems. The first 4 problems are mainly used for choosing domestic students and much easier than other tournament competitions. However, we added two more problems and we hope these are interesting and challenging enough for choosing 20 qualifiers. Note that there is no time penalty for incorrect submissions. The time penalty is MAX, not SUM.

The point values are 100 — 200 — 400 — 700 — 1600 — 1600. If you are unfamiliar with AtCoder System, 2X-point problem in AtCoder is as hard as TopCoder's d1 X-point problem.

Let's discuss problems after the contest.

•
• +50
•

By rng_58, history, 13 months ago, ,

Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo!

CF Handle Country Semifinal
touristBelarus2
s-quarkChina2
scott_wuUnited States1
-XraY-Russia1
CoderGeorgia2
qwerty787788Ukraine2
Um_nikRussia2
ikatanicCroatia2
rng_58Japan1
XharkSouth Korea1
kuniavskiRussia1
moejy0viiiiivChina1

I heard that one of advancers from 3A withdrew (but I don't know who W4yneb0t).

•
• +75
•

By rng_58, history, 13 months ago, ,

Let's discuss problems.

By the way, finally reached #1!

•
• +143
•

By rng_58, history, 14 months ago, ,

Two years ago, the Codeforces rating system was changed significantly. The system is published here.

Let's take a close look at the formula:

• We compute seedi from old rating, so it corresponds to the performances of all old contests.
• mi is the mean of seedi and actual place. Roughly speaking, 50% of it comes from old contests and 50% comes from the most recent contest.
• R corresponds to mi. 50% of it comes from old contests and 50% comes from the most recent contest.
• The new rating is ri + di = (ri + R) / 2. 25% comes from the most recent contest and 75% comes from others.

I prefer smaller rating changes in a single contest, at least for negative direction. Some reasons are:

• Why do you put 25% weight on the most recent contest, even for experienced contestants (say, 100+ contests)? However, I agree that if the weight is smaller, it is too time-consuming to raise the rating for newcomers, which can be frustrating. In Glicko (an improved version of Elo), you are assigned a value called RD. This value represents how inaccurate your rating is, and when RD is small, your rating change is smaller. You start from a very high RD, and if you keep competing, this value gradually decreases.

• It is possible that someone suddenly becomes stronger in a short period of time. However, the opposite is not true. Yes, if you don't practice, you may gradually decline, but this is much slower. When someone gets very bad performance, it is natural to think that it was because of a bad luck, not because of actual strength.

• It is simply demotivating to lose way too much rating because of a single failure.

• It seems there was "rating cap" in the old system. For example look at this. His rating changes in #270 and #318 were roughly the same.

What do you think?

UPD. Suggestion for the new formula.

I think slight modification is enough. In the current system, we use

di = (R - ri) / 2

Change it to

di = f(k)·(R - ri)

where k is the number of contests you've participated (so, k = 0 for newcomers).

I suggest f(∞) = 1 / 5, and to compensate that f(0) should be a bit bigger. One possible explicit formula is: