rng_58's blog

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

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

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:

  1. tourist
  2. ksun48
  3. Um_nik
  4. Marcin_smu
  5. koosaga

Read more »

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

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

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?

Read more »

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

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

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

Contest Link

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.

Read more »

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

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

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

Contest Link

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.

Read more »

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

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

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

Contest Link

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.

Read more »

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

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

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

Read more »

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

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

Let's discuss problems.

By the way, finally reached #1!

Read more »

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

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

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:

Read more »

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

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

https://r.recruit-jinji.jp/code_fes/us/index.html

Details will be announced in early August. In Japanese website, it says there will be 20 slots for international students.

According to Japanese website, the finals will be 25th-26th in November.

Read more »

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

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

AtCoder Grand Contest 018 will be held on Sunday (time). The writer is maroonrk.

Contest Link

Contest Announcement

The point values will be 300 — 700 — 800 — 1100 — 1600 — 1700.

Let's discuss problems after the contest.

Read more »

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

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

Recently I solved an interesting constructive task. Can you solve it? I'll reveal the source a bit later.

N(N + 1) soccer players stand in a row. The height of the i-th player is hi. No two of them are of the same height.

Sir Alex wants to remove N(N−1) players from this row leaving a new row of 2N players in which the following N conditions hold:

  • No one stands between the two tallest players,
  • No one stands between the third and fourth tallest players,
  • No one stands between the two shortest players.

Find one possible way to achieve this.

Constraints: 2 ≤ N ≤ 500, 1 ≤ hi ≤ 109, hi are pairwise distinct.

Read more »

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

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

I couldn't find a place to discuss this.

When will we get results? Is anyone confident with B or F?

Read more »

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

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

AtCoder Grand Contest 017 will be held on Sunday (time). The writer is semiexp.

Contest Link

Contest Announcement

The point values will be 200 — 400 — 1000 (500) — 1100 — 1200 — 1600.

Let's discuss problems after the contest.

Read more »

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

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

AtCoder Grand Contest 016 will be held on Sunday (time). The writer is sugim48.

Contest Link

Contest Announcement

The point values will be 300 — 700 — 700 — 1000 — 1400 — 1600.

Let's discuss problems after the contest.

UPD: Now the editorial (check page 5) is ready.

I'll add some quick comments here.

A.

Spoiler

B.

Spoiler

C.

Spoiler

D.

Spoiler

E.

Spoiler

F.

Spoiler

Read more »

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

By rng_58, history, 6 months ago, In English,
x = 0;

while(x < 1){
    y = x;
    x += rand(); // returns a real number between 0 and 1, uniformly at random
}

What is the expected value of y?

It's not very hard, but the result is surprising.

Read more »

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

By rng_58, history, 6 months ago, In English,
CF Handle Country
1. kevinsogoPhilippines
2. touristBelarus
3. vepifanov (7 years in a row!)Russia
4. marcin_smuPoland
5. simonlindholmSweden
6. mnbvmarPoland
7. EndagorionRussia
8. drinklessRussia
9. -XraY-Russia
10. zemenRussia
11. semiexpJapan
12. SnukeJapan
13. SpyCheeseRussia
14. TeaPotRussia
15. SnapDragonCanada
16. ZloboberRussia
17. moejy0viiiiivChina
18. s-quarkChina
19. hogloidJapan
20. EgorRussia
21. KANRussia
22. AhyangyiChina
23. rng_58Japan
24. LHiCRussia
25. ifsmirnovRussia
26. ivan.popelyshevRussia
27. LewinUnited States
28. PavelKunyavskiyRussia
29. aitchSweden

Read more »

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

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

This year I haven't decided whether I'll participate (the flight won't be paid). Anyway, here is the top 25:

CF Handle Trip to Moscow
1. touristEasy
2. Um_nikEasy
3. rng_58Hard
4. krijgertjeMedium
5. W4yneb0tMedium
6. MilaninEasy
7. PetrEasy
8. dreamoonHard
9. EryxMedium
10. LHiCEasy
11. Alex_2oo8Easy
12. moejy0viiiiivHard
13. aidEasy
14. I_love_Tanya_RomanovaEasy
15. jcccccccccccccccccccccsbHard
16. fqwHard
17. shikHard
18. izbanEasy
19. maksayEasy
20. ilyakorEasy
21. SwistakkMedium
22. snukeHard
23. MicerenHard
24. mnbvmarMedium
25. KANEasy

Read more »

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

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

AtCoder Grand Contest 015 will be held on Saturday (time). The writer is DEGwer.

Contest Link

Contest Announcement

The point values will be announced later.

Let's discuss problems after the contest.

By the way, the writer is currently flying.

Read more »

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

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

1. Tsinghua (Win: 40%, Gold: 90%, Medal: 100% after some rounding)

  • CF max: 3441, 3203, 2967 (agg = 3516)
  • Open Cup: 1, 1, 11, 9 (median = 5)
  • China Final: 1
  • MIPT: 1, 1, 1, 2, 4, 1, 4

2. Warsaw (Win: 15%, Gold: 75%, Medal: 95%)

  • CF max: 3122, 2962, 2826 (agg = 3237)
  • Open Cup: 2, 3 (median = 2.5)
  • Petrozavodsk: 4, 2, 4, 3, 2, 2, 1, 2

3. SPb ITMO (Win: 15%, Gold: 50%, Medal: 90%)

  • CF max: 2880, 2870, 2860 (agg = 3104)
  • Open Cup: 7, 3, 2, 1, 13, 1, 2, 1, 3, 7, 13, 8, 8, 12, 3, 2, 1, 12 (median = 3)
  • Petrozavodsk: 4, 1, 3, 1, 6, 5, 3, 7, 5
  • MIPT: 6, 2, 3, 1, 5, 2, 1

4. SPb SU (Win: 10%, Gold: 40%, Medal: 85%)

  • CF max: 3170, 2951, 2936 (agg = 3281)
  • Open Cup: 9, 21, 18, 5, 3, 4, 9, 9, 6, 1, 2, 2, 7, 1, 4, 23, 20, 4 (median = 5.5)
  • Petrozavodsk: 7, 3, 6, 5, 8, 1, 4, 5, 1
  • MIPT: 2, 4, 2, 3, 1, 10, 8

5. Seoul (Win: 5%, Gold: 40%, Medal: 85%)

  • CF max: 3174, 2919, 2760 (agg = 3250)
  • Open Cup: 4, failed, 4 (median = 4)

6. MIPT (Win: 5%, Gold: 30%, Medal: 75%)

  • CF max: 2928, 2757, 2756 (agg = 3063)
  • Open Cup: 16, 29, 27, 28, 7, 24, 17, 15, 9, 15, 17, 3, 9, 4, 10 (median = 15)
  • Petrozavodsk: 1, 5, 5, 5, 1, 6, 6, 1
  • MIPT: 3, 6, 5, 4, 6, 3

7. MIT (Win: 5%, Gold: 30%, Medal: 75%)

  • CF max: 2900, 2637, 2540 (agg = 2981)
  • Open Cup: Equivalent to 2.5 in NAIPC

8. KTH (Gold: 10%, Medal: 60%)

  • CF max: 2761, 2637, 2273 (agg = 2870)
  • Open Cup: 2, 17, failed, 7 (median = 12)
  • MIPT: 5, 5, 16, 7, 7, 2

9. Fudan (Gold: 5%, Medal: 55%)

  • CF max: 2543, 2367, 2327 (agg = 2667)
  • Open Cup: 6, 13, 9, 6, 13, 18 (median = 11)
  • China Final: 5
  • MIPT: 12, 3, 7, 15, 13, 4, 5

10. New South Wales (Gold: 5%, Medal: 50%)

  • CF max: 3073, 2429, 2006 (agg = 3082)
  • Open Cup: 6, 8, 16 (median = 8)
  • MIPT: 14, 9, 10, 16, 2, 5, 7

11. Tokyo (Medal: 50%)

  • CF max: 2762, 2694, 2424 (agg = 2903)
  • Open Cup: 29, 5, 10, 12, 14, 29 (median = 13)
  • MIPT: 11, 10, 6, 8, 15, 6, 6
  • Barcelona: 1, 1, 1, 2, 3, 1, 1

12. SJTU (Medal: 50%)

  • CF max: 2707, 2609, 2582 (agg = 2874)
  • Open Cup: 26, 3, 18, failed, 21, 12, 10, 20, 26, 14 (median = 19)
  • China Final: 2
  • MIPT: 8, 7, 4, 10, 3, 9, 10

I won't be surprised if the following teams get a medal:

13. NTU (Medal: 45%)

  • CF max: 2772, 2341, 2220 (agg = 2808)
  • Open Cup: 11, 15, 21, 10, 2 (median = 11)

14. Waterloo (Medal: 45%)

  • CF max: 2925, 2908, 2703 (agg = 3100)
  • Open Cup: Equivalent to 12.5 in NAIPC
  • Barcelona: 3, 2, 4, 1, 1, 3, 2

15. Perm SU (Medal: 40%)

  • CF max: 3037, 2850, 2578 (agg = 3127)
  • Open Cup: 6, 18, failed, 3, failed, 9, 18, 7, 24, 15, 14, 16, 16, 7, 21, 16, 21, 17 (median = 16)
  • Petrozavodsk: 8, 12, 10, 14, 10, 10, 2, 6, 6
  • MIPT: 4, 8, 11, 5, 20, 7, 9

16. Peking (Medal: 40%)

  • CF max: 2920, 2566, 2338 (agg = 2965)
  • Open Cup: 21, 3 (median = 12)
  • China Final: 6

17. Helsinki (Medal: 35%)

  • CF max: 2721, 2280, 1516 (agg = 2745)
  • Open Cup: 15, failed, 9, failed, 16, 4, 17, 11, 30, 18, 2, failed, 8 (median = 16)
  • Petrozavodsk: 3, 26, 25, 11, 11, 7, 10, 2, 9
  • MIPT: 10, 16, 14, 6, 23, 17, 3

18. BSUIR (Medal: 30%)

  • CF max: 2825, 2625, 2466 (agg = 2943)
  • MIPT: 7, 13, 8, 11, 9, 13, 12

===

  • Expected win of top 7 = 0.95
  • Expected gold of top 10 = 3.75
  • Expected medal of top 18 = 11.05

And I guess Tokyo Institute of Technology will be around 25th, Keio will be around 40th.

Read more »

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

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

AtCoder Grand Contest 014 will be held on Saturday (time). The writer is yutaka1999.

Contest Link

Contest Announcement

The point values are 300 — 500 — 700 — 900 — 1400 — 2400. Note that the contest duration is unusual (130 minutes).

Let's discuss problems after the contest.

Read more »

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

By rng_58, history, 7 months ago, In English,
 
 
 
 
  • Vote: I like it  
  • +52
  • Vote: I do not like it  

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

Let's discuss problems.

B is very nice. Until the end of the contest, I thought it was a marathon task. Then yutaka1999 told me the following: for an odd prime p, a[p] = 2 - p%4.

And I like geometry tasks like J.

Read more »

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

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

There are lots of important tournaments in this season, and we moved some AtCoder contests to avoid collision. Please check https://atcoder.jp/.

We'll add more ARC/ABCs in May.

Read more »

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

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

AtCoder Grand Contest 013 will be held on Saturday (time). The writer is maroonrk.

Contest Link

Contest Announcement

The point values are 300 — 500 — 700 — 900 — 1600 — 2000. Note that the contest duration is unusual (150 minutes).

Let's discuss problems after the contest.

Read more »

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

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

AtCoder Grand Contest 012 will be held on Saturday (time). The writer is camypaper.

Contest Link

Contest Announcement

The point values are 300 — 700(200) — 1000 — 1000 — 1000 — 2000.

Let's discuss problems after the contest.

Read more »

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