rng_58's blog

By rng_58, history, 4 days ago, In English,

AtCoder Grand Contest 031 will be held on Saturday (time). There are unusually many writers: yutaka1999, yosupo, DEGwer, maroonrk, hogloid, HIR180. All of them are participating in Oman camp now, and they formed a problemset together.

This is the first GP30-rated contest in this season — see this post for details.

Contest Announcement

Contest duration: TBD

The point values will be announced later.

Let's discuss problems after the contest.

Read more »

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

By rng_58, history, 12 days ago, In English,

World Tour Finals 2018/19 has ended, and we will start the new season soon.

The next two contests will be:

UPD: Due to a fatal trouble (namely, the hardest problem turned out to be known) we had to reschedule it. We are very sorry about this.

And these two will be counted for this season's GP30 race. Like last year, the top 8 (or more, in case we get richer) people of the race ranking will be invited to the onsite finals in the beginning of 2020.

There were several requests to increase the number of contests. Currently our goal is to hold

  • 1 AGC or other all-rated contests per month on average (or 12 per year).

  • 2 ARCs or other <2800-rated contests per month on average (or 24 per year).

(This looks like the maximum number I can handle myself).

Read more »

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

By rng_58, history, 4 weeks ago, In English,

We decided to hold a mirror contest of yesterday's finals because there were several requests.

This contest is unrated, but we want to keep it as fair as possible. Please do not participate in case you already know the problems (e.g., participants of Beijing camp), and do not discuss solutions with others during the contest.

This contest is recommended for reds and very ambitious oranges.

Read more »

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

By rng_58, history, 6 weeks ago, In English,

Recently we noticed that the number of international participants to ARC-level contests are declining, so we decided to make announcements here.

When a contest is rated for ~2799, regardless of the name of the contest, the problems are prepared in the same way as ARC contests. We try to make the contest interesting even for reds (by the way, you can estimate the difficulty from point values). I think it's rather a div 1.5 contest rather than a div 2 contest (In this particular contest, since there are no divisions, the contest is like div 1.5 + div2 + div3 contest). We always have English editorials for ARCs these days.

Yahoo Programming Contest 2019 will be held on Saturday (time). The writer is DEGwer.

Contest Link

Contest Announcement

Contest duration: 120 minutes

The point values will be 100 — 200 — 400 — 600 — 800 — 900.

Let's discuss problems after the contest.

Read more »

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

By rng_58, history, 3 months ago, In English,

UPD: The contest is tomorrow, from 11:00 JST (4 hours). You can watch the standings from here. The problems will be published later (not during the contest, because finalists have the internet access).

Congratulations to finalists! The date of the event is February 21st.

Full table of GP30 scores

AtCoder Profile CF Handle Country
touristtouristBelarus
cospleermusoraV--o_o--VRussia
PetrPetrRussia
LHiCLHiCRussia
Um_nikUm_nikRussia
yutaka1999yutaka1999Japan
apiadOO0OOO00O0OOO0O00OOO0OOChina
ksun48ksun48Canada

By the way, now you can set your picture and CF/TC handles in your AtCoder profile page from https://atcoder.jp/settings.

Read more »

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

By rng_58, history, 3 months ago, In English,

AtCoder Grand Contest 030 will be held on Saturday (time). The writers are semiexp, sugim48, and DEGwer.

Contest Link

Contest Announcement

Contest duration: 110 minutes

The point values will be 200 — 800 (300) — 1000 — 1000 — 1400 — 1600.

Let's discuss problems after the contest.

By the way, this is the last contest of the year, and after this match, top 8 people by GP30 scores will qualify for tour finals. Four people (tourist, V--o_o--V, Petr, LHiC) have already qualified, but there are four more slots. Good luck!

Current Standings

Read more »

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

By rng_58, history, 3 months ago, In English,

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

Contest Link

Contest Announcement

Contest duration: TBD (around 2 hours)

The point values will be announced later.

Let's discuss problems after the contest.

Read more »

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

By rng_58, history, 4 months ago, In English,

We will not hold AtCoder Regular Contests for a while. Probably the next ARC will be in March. Instead, there will be several sponsored tournaments.

The onsite rounds of these tournaments are only for Japanese (we are sorry for that), but we will try to translate majority of qualification rounds into English. In case the problems are translated, usually the contest is rated for <2800 (there can be exceptions, so please check individual announcements). The difficulty/quality of those rounds are at the same level as usual ARCs — so please participate in those contests! There will be one such contest this Saturday (20:00 JST, an hour earlier than usual), and I think it will be announced soon.

There will be two more AGCs this year. date/time of AGC029 date/time of AGC030

After these AGCs, we will announce the top 8 people (by GP30 scores), and they will be invited to World Tour Finals in February 21st!

UPD: We decided to move one AGC to the end of year because it overlapped with NEERC. In next two weeks there will be ABCs, an AGC on 15th, a contest rated for <2800 on 22nd, and an AGC again on 29th.

Read more »

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

By rng_58, history, 5 months ago, In English,

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

Contest Link

Contest Announcement

Contest duration: 150 minutes

The point values will be announced later.

Let's discuss problems after the contest.

Read more »

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

By rng_58, history, 6 months ago, In English,

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 Link

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.

Read more »

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

By rng_58, history, 7 months ago, In English,

Please write a comment if you have more information.

CF Handle Country
1. matthew99China
2. Um_nikRussia
3. ecnerwalaUnited States
4. dotoryaSouth Korea
5. s-quarkChina
6. majkCzech Republic
7. PetrRussia
8. ksun48Canada
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
19. RadewooshPoland
20. ilyakorSwitzerland
21. vepifanovRussia
22. ikatanicCroatia
23. mareksomPoland
24. dreamoonTaiwan
25. natsugiriJapan

Read more »

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

By rng_58, history, 7 months ago, In English,

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

Read more »

Tags gcj, dcj
 
 
 
 
  • Vote: I like it  
  • +52
  • Vote: I do not like it  

By rng_58, history, 8 months ago, In English,

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

Contest Link

Contest Announcement

Contest duration: TBD (about 2 hours)

The point values will be announced later.

Let's discuss problems after the contest.

Read more »

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

By rng_58, history, 9 months ago, In English,

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!

Read more »

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

By rng_58, history, 9 months ago, In English,

I do this, as usual.

GCJ Top 25:

CF Handle AtCoder Handle Country
1. ErrichtoErrichtoPoland
2. ifsmirnovifsmirnovRussia
3. Golovanov399Golovanov399Russia
4. eatmoreeatmoreRussia
5. pashkapashkaRussia
6. RadewooshStonefeangPoland
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
21. SnapDragonCanada
22. SyloviaelyKujouKaren?China
23. LHiCLHiCRussia
24. PavelKunyavskiykunyavskiyRussia
25. overtrollcospleermusoraRussia

DCJ Top 20:

CF Handle AtCoder Handle Country
1. ErrichtoErrichtoPoland
2. mareksommareksomPoland
3. OO0OOO00O0OOO0O00OOO0OOapiadChina
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
19. RadewooshStonefeangPoland
20. pashkapashkaRussia

Read more »

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

By rng_58, history, 10 months ago, In English,

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

Contest Link

Contest Announcement

Contest duration: TBD (about 2 hours)

The point values will be announced later.

Let's discuss problems after the contest.

Read more »

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

By rng_58, history, 10 months ago, In English,

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

Contest Link

Contest Announcement

Contest duration: 130 minutes

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

Let's discuss problems after the contest.

Read more »

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

By rng_58, history, 11 months ago, In English,

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

Contest Link

Contest Announcement

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

Let's discuss problems after the contest.

Read more »

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

By rng_58, history, 11 months ago, In English,

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?

Supplementary data

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).

Please post here if you have some opinion about it.

Read more »

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

By rng_58, history, 11 months ago, In English,

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...

Read more »

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

By rng_58, history, 12 months ago, In English,

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.

Read more »

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

By rng_58, history, 13 months ago, In English,

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

Contest Link

Contest Announcement

The point values will be announced later.

Let's discuss problems after the contest.

Read more »

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

By rng_58, history, 14 months ago, In English,

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

Read more »

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

By rng_58, history, 15 months ago, In English,

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.

Please check the details here.

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.

Read more »

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

By rng_58, history, 15 months ago, In English,

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

  • : Link

  • 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?

Read more »

Tags fft
 
 
 
 
  • Vote: I like it  
  • +319
  • Vote: I do not like it