Финал Google CodeJam состоится 29 июля в 4:00 по Москве
Рассказ одного из участников Первая часть, Вторая часть
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
6 дней
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
6 дней
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 25.11.2024 03:02:47 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
To Egor: Good Luck! +1 to your TopCoder Quote.
Сегодня получил футболку Russian Code Cup - а это, как и было где-то уже написано, маломерка.
Так вот, во избежание, что можете сказать по этому поводу о гуглофутболках? Они нормального размера?
(кстати, до финала уже меньше суток: начнется в 4 утра по Москве)
Really? Turing state machine, second year of CS university. Yes, the actual problem is quite funny, but I cannot really call it so brilliant.
I like the concept of the problem, but dislike the process of solving it=)
For anyone familiar with Turing machines the solution with O(NlogN) runtime and (log2(N) + C) program size should be obvious. I spent a lot of time optimizing the constant C to fit 30 commands limit.
The final submission contained: writing the binary number (13cmd), left-pass with decrease (7cmd) and right-pass with move (8cmd) with total of 28cmd for large output.
It's quite interesting what is the minimal number of commands required for large output. Also I don't understand how increasing the alphabet size can help in optimizing the program, since a lot of states must be sensitive to all the possible chars.
First of all, higher bits of the number should be placed to the left. Otherwise you won't be able to easily decrement in left-pass. So left-pass decrement is iterating over digits from lower-valued to higher-valued.
For decrement, there are two working states. The difference is: whether we have to decrement the rest of the number or not. For these two working states we have to write commands for all possible input chars (empty/0/1), so we get 6 commands. Also we need one special state and one command to step left from initial(empty) position to the first digit of number. When the decrementing robot steps on the empty slot, it either drops the cake (if still wants to dec) or simply steps to the right (if does not want to dec).
For right-shifting the number, there are also two working states. The difference is: whether the previous digit was 0 or 1. Of course we have to react to all possible chars (empty/0/1), so we require 6 commands for these working states. However, we need one special state and two commands to handle the first digit properly, because previous digit for the first digit is "empty".
So for each of the decrement and move passes there are three states, one of them is "starting state" and the other two are "working states". And of course there are other 13 states+commands for initialization.
Each step now consists of:
- subtracting 1 - takes one pass from right to left and 2 states (whether we still have to subtract)
- shifting the entire counter 1 cell to the right - takes one pass from left to right and 3 states (carrying empty/zero/one)
If we have to subtract from empty cell on the left edge, that means we've finished, so do final pass to the right (1 special state) and halt.
Total runtime is approx. 2 * N * logN, which is about 130000 with N=5000.
I squeezed it into 29 rules (not much optimization was really needed) and it passed in practice.
UPD: final pass is actually not needed if we encode N+1 instead of N-13 (and halt at left edge), that fits in 27 rules.
GCJ 2012 will be held in Paris, as it was said on the awards ceremony.
In rng_58's submission for problem A, he computes the modular inverse for all i modulo MOD:
inv[1] = 1;
for(i=2;i<MOD;i++) inv[i] = (MOD - MOD/i) * inv[(int)(MOD%i)] % MOD;
How do justify this algorithm? Thanks in advance!
Ok, I figured it. First, MOD - i*MOD/i == MOD%i
so i*(MOD-MOD/i) == MOD%i modulo MOD
then i*inv[i] modulo MOD simplifies to 1:
i*inv[i] == i *(MOD-MOD/i) * inv[MOD%i]
i*inv[i] == (MOD%i) * inv[MOD%i] modulo MOD
i*inv[i] == 1 modulo MOD
The complexity is O((RC)^2).
The idea is to modify the map, by increasing some fields, without changing the
result:
1) If the height of each field is increased up to the nearest multiple of M,
the result is unchanged.
With that property, each erosion decreases heights by either 0 or M.
We can rescale the map by dividing everything by M, and assume from now on that
M=1.
2) If a field needs d days to reach the level 0, then it's as if its
height is d.
3) If each field with positive height has a lower neighbour, then the result is
the maximum height over the map.