CodeChef invites you to participate in the April CookOff 2013 at http://www.codechef.com/COOK33.
Time: 21st April 2013 (2130 hrs) to 22nd April 2013 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.
Details: http://www.codechef.com/COOK33/
Registration: Just need to have a CodeChef user id to participate.
New users please register here
Problem Setter: Vitaliy Herasimiv
Problem Tester: Hiroto Sekido
Editorialist: Pradeep Mathias
It promises to deliver on an interesting set of algorithmic problems with something for all.
The contest is open for all and those, who are interested, are requested to have a CodeChef userid, in order to participate.
Решил две задачи из пяти первым — и теперь чувствую себя идиотом, решающим не в монитор. Что-то здесь не так:)
Как первую решать (про шары)? Я ничего умнее составления какой-то неработающей динамики "сколько цветов расставили — сколько плохих стыков имеется" не придумал.
Такой динамикой и надо решать. При переходе перебираем, на сколько групп делим очередной цвет и сколько плохих стыков мы устраняем. Отсюда однозначно определяется новое количество плохих стыков, а само значение динамики надо еще домножить на количество способов выбрать эти самые стыки, а также количество способов разбить A шаров на B групп (это равно C(A - 1, B - 1)).
Что тут сказать, прямые руки странным образом превращают неработающую динамику в работающую.
Спасибо за объяснение:)
Отдельная благодарность witua за интересный контест)
Она работающая. Переберем, на сколько групп делим шары очередного цвета, сколько групп впихиваем в плохие стыки и переходим к новому состоянию, где количество плохих стыков уменьшается на количество тех, в которые мы воткнули группы, и увеличивается на количество шаров такого цвета минус число групп (это как раз и будет количество плохих стыков среди новых групп).
Сегодня проходили какие-то большие сложности, например, в задаче про строки зашло N^2logN, а в задаче на матожидание N^5.
У меня в строках голый квадрат, если что.
Фиксируем смещение одной строки относительно другой, далее 2 указателя. Будем поддерживать максимальное по ширине окно, для которого расстояние Хэмминга не больше k. Двигаем левый указатель, во внутреннем цикле правый до тех пор, пока можно. Тогда для каждого положения правого мы будем знать, какой для него соответствующий левый, и можем добавить к ответу длину этого промежутка.
В матожидании тупой N^5 зашел?
Я на контесте сдал N^5 с отсечением по ненулевых ответах до N^4. Думаю, Burunduk1 смог бы доказать, что при данных ограничениях это честные N^4 :)
Сейчас в практисе попробовал без отсечения — TL.
Там получается примерно такое количество действий (M2 * N3) / 6
Соль в том, что у меня с отсечением на ненулевой ответ внутрь цикла, который
заходит на любом из авторских тестов менее 50000 раз. И даже если в каждом из этих вхождений мы попадем на символ "0" в образце и надо будет сделать еще цикл по m, то все равно оценка сверху как 50000*50. Что в численном эквиваленте на дотягивает даже до N^4.
The editorials are available here: http://discuss.codechef.com/tags/cook33/
Забавный факт: при вычислениях можно заменить var=dp/m на var=dp*nm, где имеем прекалькнутое nm=1.0/m. Сегодня в случае задачи на матожидание это дало мне ускорение на четверть.
Казалось бы, все логично... И, может быть, этот прием вообще известен всем, кроме меня:) Но на всякий случай спрошу — у такого подхода есть какие-нибудь минусы? Потеря точности, к примеру. Или что-то более хитрое.