AtCoder Grand Contest 007 will be held on Saturday (time). The writer is dreamoon_love_AA.
The point values are 200 — 400 — 1000 — 1200 (600) — 1400 — 1500.
Let's discuss problems after the contest.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
24:13:22
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
24:13:22
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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
Время на сервере: 22.11.2024 17:21:40 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
dreamoon? Isn't the writer dreamoon_love_AA on Codeforces?
dreamoon was his old name if i remember correctly. It's quite confusing.
Yes, I also think it's quite confusing. I want to change it back next year....
I also change my handle between tozangezan and wolf_sothe once a year so don't worry about it.
Does it support virtual participation?
There's an unofficial one. Link
The description is all written in Japanese but I posted a YouTube video explaining how to use. Link
Just curious, will we have contests start at different time?
It seems this is the only slot that is good for both Japan and Europe, so I think all future AGC/ARC will be in this slot. However, some tournament rounds may be held at different time.
Great contest, good problems!
A couple of features for the website I would like to propose though: 1) Make it visible which tasks you solved on the "Tasks" page 2) Maybe a chat or comments system so participants can talk after the contest? Since the editorial is in Japanese and I would like to know how to solve the last 2 tasks..
Well done, though, great job!
The editorial is also in English. Scroll down to see it
Found it, thanks!
After receiving a WA on D, debugging for a long time, I found out that using "%I64d" to print a long long will get a WA.:( Isn't there any statements about this?
Please email us your handle. We'll change your result for this contest.
Feature request: Add option for viewing country standings.
+1
Thank you for requests, we are currently busy with CODE FESTIVAL but we'll implement some of them in the future.
Can any one please explain solution of C? The editorial is too short to get the full idea. Thanks.
In the original problem the distances were one (so the input takes only one integer N), but it turned out that this version can be solved with OEIS and thus we had to change it to arithmetic sequences.
For example, suppose that N = 3 and the distances are (1, 1, 1, 1, 1, 1). Let f(1, 1, 1, 1, 1, 1) be the answer of the problem in this case.
As there are three balls, there are six possibilities in the first step. In the first step, the chosen ball always move by the distance of 1. After this step, the "state" of the balls and holes will be one of the following: (1, 1, 1, 1), (3, 1, 1, 1), (1, 3, 1, 1), (1, 1, 3, 1), (1, 1, 1, 3), (1, 1, 1, 1). The "average" of theses state is (4 / 3, 4 / 3, 4 / 3, 4 / 3). Thus, we get
f(1, 1, 1, 1, 1, 1) = 1 + f(4 / 3, 4 / 3, 4 / 3, 4 / 3).
We can prove that when the state is an arithmetic sequence, the expected state after the next step is also an arithmetic sequence. The remaining part is easy I think.
But, if we call the answer g(N, d1, x), you can show that g(N, d1, x) = g(N, d1 + (N - 1 / 2)x, 0) = (d1 + (N - 1 / 2)x)g(N, 1, 0), so it still translates to the problem with all distances one.
Because of that properties, C was still solvable with OEIS. Not what I've tried, but I know someone who got AC with that.
With brute force we can notice answer = x * f(n) + d1 * g(n), so we can search for f(n) and g(n), which results in something related to http://oeis.org/A001705
Still, I loved all rest of problems!
My solution doesn't use arthimetic property. For a segment, I compute expected number of ball rolls over. For example, if there are k balls before this segment. Then expected number of ball before rolls over is:
.
I know it's been a long while since you've written this comment, but would you mind explaining how you ended up with that formula? In the contest I've tried computing the same thing but I was unable to do it and I thought a lot about it. I think it would be very useful to me to find out how to do it (as this was the way I tried to think it, so this is the path I would have chosen if I were able to finish the reasoning, rather than changing my whole perspective to solve it the same way as them).
For a ball and a segment, you should calculate the probability of the ball rolls over the segment. It relies on balls between them and other ball at opposite side.
really desire the english solution :)
anyway, atcoder is very good to me.
The english editorial is below the Japanese editorial