CodeChef November Cook-off

Всем привет!

Приглашаю вас поучаствовать в очередном коротком контесте на сайте CodeChef.com (http://www.codechef.com/COOK16). Начало запланировано на воскресенье, 20 ноября, на 20:00 по московскому времени (посмотреть время начала в других часовых поясах можно здесь). Автором задач на этот раз буду я, а тестировал контест Антон Лунёв (Anton_Lunyov). Антон внёс большой вклад в подготовку контеста, за что ему отдельное спасибо :)

Также информация для тех, кто не знаком с форматом соревнований на CodeChef. Длительность контеста -- 2,5 часа, проводиться он будет по традиционным правилам ACM. Состоит контест из пяти задач различного уровня сложности. Специальной регистрации на сам контест не требуется, достаточно лишь зарегистрироваться на сайте.

К сожалению, я не смогу наблюдать за ходом контеста -- в этот же день проводится ВКОШП. Тем не менее, Антон сможет ответить на все вопросы участников, если таковые будут.

Удачи! ;)

Комментарии (28)

Показать архивные | Написать комментарий?

Shuaib

12 лет назад, # |

Is this the first time you are setting a problem set for a contest? Would love to see problem set from you on Topcoder and Codeforces too.

→ Ответить

steiner

12 лет назад, # ^ |

http://codeforces.com/contest/17/

abdukodir

Могу ли я дорешивать прошедшие контесты?

Sereja

Да, в Practice.

Slamur

Необходима ли предварительная регистрация на контест? Если да, то не могли бы подсказать, как это сделать - я не смог найти ничего похожего на регистрацию.

k-va	12 лет назад, # ^ \| +7 см. выше: "Специальной регистрации на сам контест не требуется, достаточно лишь зарегистрироваться на сайте." → Ответить

Edvard

А это нормально что я после того как сдал 3ю задачу упал в ранклисте на 50 мест и теперь ниже чем те у кого 2 задачи?

Anton_Lunyov

Уже стало нормально. Оно у них так всегда лагает.

Да получше)

Petr

Отличные задачи!

Единственное - что за лажа с тайм лимитом в задаче Buying Candies? Или ее надо было решать быстрее, чем за N*K^2?

У меня решение на яве не заходит, на плюсах еле зашло после оптимизации в 2 раза. Ну и все бревна из-за багов в переводе с явы на плюсы и в этой оптимизации.

Авторское имеет сложность O(N+K^4).

Petr	12 лет назад, # ^ \| 0 Ого, понятно. А как это - в двух словах не объяснить? → Ответить

Уже выложили разбор
http://www.codechef.com/wiki/november-2011-cook-problem-editorials

Petr	12 лет назад, # ^ \| +8 А, я кажется понял. Бессмысленно любого остатка в дельте брать больше k. Круто! → Ответить

KADR	12 лет назад, # \| 0 Задачи понравились! Как решать Buying Candies? Я написал жадность за O(NK²), она поначалу ТЛила, а после минут 20 оптимизации оказалось, что она неправильная. → Ответить

Отличные задачи! Кто-нибудь может рассказать Buying Candies?

-7

Вопрос снимается. Решение понял из асимптотики в комменте выше

forest

А как посмотреть rating graph (или хоть какую history) для short contests

phantom11

Thanks for the wonderful problems .They were really logical and thought provoking:)

is there rating graph for short contests? if(yes) {where can I find it?} else if(you are planning){when it will be ready?}

Kostroma

← Rev. 2 →

you can find it in your profile

UPD sorry, I read it badly

_jte_

Actually it's for long contests.

no. there are 2 ratings - for long and for short. for example, i haven't participate in long contests, but i have "short" rating

Short

197

1210.356(

>>is there rating graph for short contests?

Was there any question about the rating itself?

sorry, my bad, I can't read :D

← Rev. 4 →

правильна ли такая динамика в Colorful Chains:

dp[i + 1][true] = dp[i][true] + 2 * dp[i][false] / m;

dp[i + 1][false] = (m - 1) * dp[i][true] + (m - 2) * dp[i][false] / m;

где dp[i][flag] - количество раскрасок ячеек от 1 до i таких, что ячейка с номером i - m покрашена, в соответствии с bool flag в цвет, который встречается 1 или 2 раза среди ячеек с номерами от i - m до i

P.S. по модулю беру, и деление делаю в поле по модулю 10⁹ + 7

код

UPD нашел багу