AtCoder Grand Contest 023 will be held on Saturday (time). The writer is maroonrk. This contest counts for GP30 scores.
The point values (and duration) will be announced later.
Let's discuss problems after the contest.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
12:45:56
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
12:45:56
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 04:49:04 (k1).
Десктопная версия, переключиться на мобильную.
При поддержке
Minor quibble: it overlaps with tomorrow's BOI mirror, you could consider moving it slightly later. Of course, the overlap is just 30 minutes out of the 5-hour BOI, so it's not a big deal.
Unfortunately, it overlaps with google hashcode.
There are lots of contests in weekends and it's difficult to avoid all of them. Also, I think it's not a very good idea to move contests too frequently.
Thank you for the information, but we won't move it this time, sorry. Of course we will care more important contests (like CF, TC, major tournaments, etc.)
reminder: 5 mins
Problem F is similar to this
Is this contest popular among Chinese?
This problem is for the provincal OI team selection contest several days ago. It may be popular among the high school students.
And it is similar to a very old problem.
On C, how to get the formula for number of ways to fill the first K positions of our permutation such that all squares are black (the C(K - 1, N - K - 1) part) ?
You need a set {a1, a2, ..., aK} with a1 = 1, aK = N - 1.
Let di = ai + 1 - ai. Thus, this is equivalent to choosing d1 + d2 + ... + dK - 1 = N - 2. Since di is either 1 or 2, we find that we must have N - K - 1 2s and the rest are 1s. This immediately gives C(K - 1, N - K - 1).
In case someone's wondering (like me), why exactly, N - K - 1 2s. Here is the explanation:
If all were 1, the sum would be K - 1, which is not equal to N - 2. Hence we need some 2s. Lets say we need 'x' number of 2s. So,
2 * x + 1 * (K - 1 - x) = N - 2
x + K - 1 = N - 2
x = N - 1 - K
You have k numbers 1 = a1 < a2, ... < ak = n - 1 such that ai - ai + 1 = 1 or 2. We have to have 2 as a difference n - 1 - k times. Because N - 2 = ak - a1 = (a2 - a1) + (a3 - a2) + ... + (ak - ak - 1) = k - 1 + #(of twos). We want to have a sequence of differences of length k - 1 with n - 1 - k — twos, hence the formula.
Quality of problems on Atcoder never make me disappointed.
Thanks a lot for a great contest!
I have a question with regard to how Java is judged at AtCoder. After the contest I've submitted a solution to problem E that is slighly more complicated than in editorial (multiplies O(nlogn) 3x3 matrices), and I keep getting MLE. 4nlogn 3x3 matrices don't indeed fit into memory (they would take ~600M), but at any moment of time there should not be more than ~4n matrices in memory. So it seems that garbage collection does not happen or something like that.
Could it be that you're passing -Xmx<big number>? Could you maybe adopt the approach from http://codeforces.me/blog/entry/43696 ?
To clarify, this is the submission that I believe should pass: https://agc023.contest.atcoder.jp/submissions/2432391
And here it (barely) passes with manual reuse of allocated arrays: https://agc023.contest.atcoder.jp/submissions/2432665
Yes, we'll look into it.
In problem E, can anyone explain the part "the number we want compute is exactly a half of the number of valid permutaions (after the replacement)."? Why it is true?
I assume because when Ai==Aj, positions i and j are completely symmetric, and thus in exactly half of all cases there will be an inversion.
There is a typo in the editorial for F: "Let p be its children". It should be "Let p be its father".