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

The point values will be announced later.

Let's discuss problems after the contest.

# | User | Rating |
---|---|---|

1 | tourist | 3496 |

2 | Um_nik | 3337 |

3 | Petr | 3298 |

4 | W4yneb0t | 3218 |

5 | Radewoosh | 3216 |

6 | OO0OOO00O0OOO0O0…O | 3188 |

7 | Syloviaely | 3168 |

8 | izrak | 3109 |

9 | anta | 3106 |

10 | fateice | 3099 |

# | User | Contrib. |
---|---|---|

1 | tourist | 184 |

2 | rng_58 | 170 |

3 | csacademy | 165 |

4 | Petr | 158 |

5 | Swistakk | 154 |

6 | lewin | 149 |

7 | Errichto | 147 |

8 | matthew99 | 146 |

9 | adamant | 141 |

9 | Zlobober | 141 |

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

The point values will be announced later.

Let's discuss problems after the contest.

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

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

1 | tourist | 870 |

2 | Um_nik | 519 |

3 | W4yneb0t | 514 |

4 | LHiC | 480 |

5 | Petr | 417 |

6 | ksun48 | 347 |

7 | yutaka1999 | 331 |

8 | V--o_o--V | 292 |

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

You are given the first *n* (or *n* + 1 if necessary) terms of a former power series *P*(*x*) = *c*_{0} + *c*_{1}*x* + *c*_{2}*x*^{2} + .... 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 Ecan 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*?

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.

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:

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?

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, 2*X*-point problem in AtCoder is as hard as TopCoder's d1 *X*-point problem.

Let's discuss problems after the contest.

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

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, 2*X*-point problem in AtCoder is as hard as TopCoder's d1 *X*-point problem.

Let's discuss problems after the contest.

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

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, 2*X*-point problem in AtCoder is as hard as TopCoder's d1 *X*-point problem.

Let's discuss problems after the contest.

Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo!

CF Handle | Country | Semifinal |
---|---|---|

tourist | Belarus | 2 |

s-quark | China | 2 |

scott_wu | United States | 1 |

-XraY- | Russia | 1 |

Coder | Georgia | 2 |

qwerty787788 | Ukraine | 2 |

Um_nik | Russia | 2 |

ikatanic | Croatia | 2 |

rng_58 | Japan | 1 |

Xhark | South Korea | 1 |

kuniavski | Russia | 1 |

moejy0viiiiiv | China | 1 |

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

Let's discuss problems.

By the way, finally reached #1!

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
*seed*_{i}from old rating, so it corresponds to the performances of all old contests. *m*_{i}is the mean of*seed*_{i}and actual place. Roughly speaking, 50% of it comes from old contests and 50% comes from the most recent contest.*R*corresponds to*m*_{i}. 50% of it comes from old contests and 50% comes from the most recent contest.- The new rating is
*r*_{i}+*d*_{i}= (*r*_{i}+*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

*d*_{i} = (*R* - *r*_{i}) / 2

Change it to

*d*_{i} = *f*(*k*)·(*R* - *r*_{i})

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:

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.

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

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

Let's discuss problems after the contest.

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 *h*_{i}. 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 2*N* 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 ≤ *h*_{i} ≤ 10^{9}, *h*_{i} are pairwise distinct.

I couldn't find a place to discuss this.

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

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

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

Let's discuss problems after the contest.

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

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.

Try all characters from 'a' to 'z', and assume that we want to get a string that consists only of this character. What greedy strategy should we follow?

B.

Suppose that there are *C* colors in total. Then, each *a*_{i} must be either *C* or *C* - 1, and it means that the difference between the maximum and the minimum is at most one. Do some case-analysis using this fact.

C.

Suppose that *H* is not a multiple of *h*. Put a positive number in a cell if its row-number (0-based) is a multiple of *h*, otherwise put a negative number. Can you choose the "positive number" and the "negative number" properly?

D.

Create a new cell that keeps the xor of all elements. Each operation can be considered as a swap between this cell and another element in the sequence. Reduce it to a graph problem.

E.

Can you get YES/NO for a given pair of vertices (or more generally, a given set of vertices) in *O*(*M*)? Restate it in terms of graphs, then find an *O*(*NM* + *N*^{3}) solution.

F.

The task is about grundy numbers. Can you get *O*(*bell*_{number}(*N*)) solution by trying all possible grundy-number sequences? Can you reduce it to *O*(3^{N}) by DP?

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

CF Handle | Country |
---|---|

1. kevinsogo | Philippines |

2. tourist | Belarus |

3. vepifanov (7 years in a row!) | Russia |

4. marcin_smu | Poland |

5. simonlindholm | Sweden |

6. mnbvmar | Poland |

7. Endagorion | Russia |

8. drinkless | Russia |

9. -XraY- | Russia |

10. zemen | Russia |

11. semiexp | Japan |

12. Snuke | Japan |

13. SpyCheese | Russia |

14. TeaPot | Russia |

15. SnapDragon | Canada |

16. Zlobober | Russia |

17. moejy0viiiiiv | China |

18. s-quark | China |

19. hogloid | Japan |

20. Egor | Russia |

21. KAN | Russia |

22. Ahyangyi | China |

23. rng_58 | Japan |

24. LHiC | Russia |

25. ifsmirnov | Russia |

26. ivan.popelyshev | Russia |

27. Lewin | United States |

28. PavelKunyavskiy | Russia |

29. aitch | Sweden |

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

2. Um_nik | Easy |

3. rng_58 | Hard |

4. krijgertje | Medium |

5. W4yneb0t | Medium |

6. Milanin | Easy |

7. Petr | Easy |

8. dreamoon | Hard |

9. Eryx | Medium |

10. LHiC | Easy |

11. Alex_2oo8 | Easy |

12. moejy0viiiiiv | Hard |

13. aid | Easy |

14. I_love_Tanya_Romanova | Easy |

15. jcccccccccccccccccccccsb | Hard |

16. fqw | Hard |

17. shik | Hard |

18. izban | Easy |

19. maksay | Easy |

20. ilyakor | Easy |

21. Swistakk | Medium |

22. snuke | Hard |

23. Miceren | Hard |

24. mnbvmar | Medium |

25. KAN | Easy |

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

The point values will be announced later.

Let's discuss problems after the contest.

By the way, the writer is currently flying.

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

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

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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/24/2018 08:48:32 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|