Интересно. Всю жизнь называл динамику по таблице — динамикой «снизу вверх», а то, что вы называете рекурсией с мемоизацией — динамикой «сверху вниз». Вроде так и в литературе обычно упоминается.
Т.е. мемоизация не «похожа» на ДП, она обычно, считается, и есть ДП.
В то же рекурсия без мемоизации (никому нахрен не нужная, ясен пень) — тоже, формально говоря, ДП «сверху вниз».
По-моему, он известен только один классический (если я неправ, metar меня поправит и расскажет свой).
Вкратце: для каждого символа динамикой будем считать две величины — длину длиннейших нечетного и четного палиндрома с центром в данном символе. Тогда при линейном проходе можно смотреть, укладывается ли текущий символ в самый правый найденный доселе палиндром. Если нет — ищем втупую, если да — смотрим на уже вычисленное значение для симметричной буквы в «большом» (самом правом) палиндроме, обрезаем это число до границ большого, если надо, а дальше ищем втупую. Получается именно что O(N) времени (каждый проход втупую один раз затрагивает каждый символ при расширении вправо) и O(N) памяти (два массива).
Гм. С интересом послушаю.
Решение за O(N log N) с бинпоиском и хэшами для длиннейшего палиндрома-подстроки знаю, для палиндрома-подпоследовательности — никогда не видел… Посидел немного, подумал — не получается же, не хватает информации, как ни крути, хэши работают с неразрываемыми подстроками символов.
Начинающие стоящие олимпиадники — слышали все.
Более того, они даже понимают, что таким образом можно задать произвольное линейное рекуррентное отношение над произвольным кольцом.
Видел задачи, где быстрым возведением в степень решалась рекуррентность в Z2.
Что-то новое сказать в динамике по профилю элементарно. Василевский, к примеру, ни звуком не заикается о том, что понятие «профиль» — это произвольное состояние, характеризирующее множество битмаской, а не только всяческие строки и столбцы в двумерном массиве. Видел пару человек, которые начитались Василевского, потом сталкивались с динамикой по состояниям, и у них немного сносило мозг и рвало шаблон: «А где же тут таблица-то?»
На Топкодере в 500 Div 1 очень любят часто динамику по состояниям. К примеру, Gifts.
У вас сложный код, как суммы, так и модификации :)
Это же все то же самое можно в несколько строчек записать, если чуть видоизменить операцию перехода. Тогда она, тем более, становится одинаковой для обоих циклов — запоминать проще.
Сумма на отрезке [1; X]:
int sum(int X) {
int ans = 0;
for (int i = X; i > 0; i -= i & -i)
ans += t[i];
return ans;
}
Обновление в точке A[X] += V:
void update(int X, int V) {
for (int i = X; i <= N; i += i & -i)
t[i] += V;
}
Спасибо. Я, собственно, и задумал-то эту статью, потому что сталкивался с множеством человек, которые начинают интересоваться Computer Science (кто-то в вузе по программе, а кого-то просто совесть берет, что программистом работает, а матбазы не учил), читают про, например, моноиды, и начинают ныть: «Нет, ну это все, конечно, красиво, абстрактно, логично и всё такое… но на черта оно надо?» В итоге злость берет =)
Части не будут казаться цельными, тут же единая мысль логическая идет, развивается, накапливается новыми подробностями, завершается кульминацией трех жизненных примеров, и все. Ничего нельзя выкинуть, без контекста оно совершенно не читается, сколько ты не ори триста раз, что «это продолжение статьи по ссылке такой-то, сначала читайте её».
Я прошу прощения у аудитории, что конец статьи получился несколько скомканным. Когда ты публикуешь статью, а она обрезается на полуслове (какого бабуина это ограничение на объём?!), это сильно деморализирует.
Полностью неосвещённым остался третий пример, про движок регулярных выражений, впрочем, я здесь вряд ли смогу сказать больше Евгения Кирпичева, а уж он расписал свою статью в «ПФП» так замечательно, что этот стиль достоин стать в журнале эталоном, имхо.
Ещё одна тема, которой пришлось пожертвовать — свертки и их связь с моноидами. Любознательный читатель может заглянуть в поисках основ в неплохой перевод Катаморфизм в F#, а более глубокое погружение в тему я как-нибудь соберусь с силами и все же накатаю :)
Не, это исключено. Задачи там все же придумывают бывшие ACMщики. Так что в 6 минут вы не влезете в том и только том случае, если не придумаете алгоритм оптимальной сложности.
И не надо никаких новомодных ухищрений, типа кластеров и параллелизма. Не помогут.
P.S. Конечно, качество FHC оставляет желать лучшего пока что, но я верю, что на последних раундах все-таки так все и будет. По крайней мере для Google Code Jam это 100% верно.
Вот простое решение за O(N log N) на Python 2.7, основанное на этой идее:
from functools import cmp_to_key
def comp(a, b):
return -1 if a + b < b + a else 1 if a + b > b + a else 0
def solve(s):
return "".join(sorted(s.split(), key = cmp_to_key(comp)))
В моей душе после этой недели потерялись последние капли уважения к Facebook, Inc.
Судите сами:
Задачи — скучные и простые. В формулировках задач баги, их меняют на ходу, во время контеста, причём втихомолку, ничего участникам не сообщив. Была задача, которая предполагала решение динамическим программированием, но тем не менее прекрасно работал жадный алгоритм. Были задачи, условие которых пришлось перечитать 2-3 раза, чтобы понять (иллюстраций в условиях — никаких).
Тесты — никакие, они иногда почти ничего не проверяют. В задачах утверждают, что количество тесткейсов во входных файлах будет до 100, в реальности оно везде 20. Да даже и 100 для некоторых задач — цифра скучная. В авторских тестах из примера одной из задач — ошибка. Их так и не исправили во время контеста, поэтому мы писали правильное решение на свой страх и риск — хрен его знает, как у них реальное авторское решение и чекер сделаны...
Система — это вообще тихий ужас. Видимо, написана левой ногой за вечер каким-нибудь фейсбуковским интерном, что ли. В интерфейсе кнопки не работают, чтобы отослать решение, нужно раз 300 нажать на «Submit» — авось с какой-то попытки он таки отреагирует и зачтет ответ (а таймер-то тикает!) Вместо входного файла скачивается html, а в некоторых браузерах вообще ничего не скачивается. Некоторые браузеры теряют посылки, даже если кнопка «Submit» умудрилась сработать =) В scoreboard квалификационного раунда показывались лишь первые 10 человек, хотя участвовало явно побольше.
В итоге всего этого безобразия организаторы не выдержали и прекратили контест на 20 минут раньше положенного. Это вообще ни в какие ворота не лезет. Какая бы кривая у вас там ситуация не была — дайте, в конце концов, людям писать! Потом раунд и отменить можно, если что.
В общем, я уже ничего хорошего от этого Hacker Cup не жду. Следующие раунды писать буду из принципа, уже любопытно просто, чего они там на этот раз отчебучат :)
Легко. Вот, например
Т.е. мемоизация не «похожа» на ДП, она обычно, считается, и есть ДП.
В то же рекурсия без мемоизации (никому нахрен не нужная, ясен пень) — тоже, формально говоря, ДП «сверху вниз».
Вкратце: для каждого символа динамикой будем считать две величины — длину длиннейших нечетного и четного палиндрома с центром в данном символе. Тогда при линейном проходе можно смотреть, укладывается ли текущий символ в самый правый найденный доселе палиндром. Если нет — ищем втупую, если да — смотрим на уже вычисленное значение для симметричной буквы в «большом» (самом правом) палиндроме, обрезаем это число до границ большого, если надо, а дальше ищем втупую. Получается именно что O(N) времени (каждый проход втупую один раз затрагивает каждый символ при расширении вправо) и O(N) памяти (два массива).
Решение за O(N log N) с бинпоиском и хэшами для длиннейшего палиндрома-подстроки знаю, для палиндрома-подпоследовательности — никогда не видел… Посидел немного, подумал — не получается же, не хватает информации, как ни крути, хэши работают с неразрываемыми подстроками символов.
Более того, они даже понимают, что таким образом можно задать произвольное линейное рекуррентное отношение над произвольным кольцом.
Видел задачи, где быстрым возведением в степень решалась рекуррентность в Z2.
На Топкодере в 500 Div 1 очень любят часто динамику по состояниям. К примеру, Gifts.
Это же все то же самое можно в несколько строчек записать, если чуть видоизменить операцию перехода. Тогда она, тем более, становится одинаковой для обоих циклов — запоминать проще.
Сумма на отрезке
[1; X]:Обновление в точке
A[X] += V:Эх, сколько бы я еще всего упомянул здесь, будь у меня ещё хоть треть-столько же байт доступно для заполнения…
Полностью неосвещённым остался третий пример, про движок регулярных выражений, впрочем, я здесь вряд ли смогу сказать больше Евгения Кирпичева, а уж он расписал свою статью в «ПФП» так замечательно, что этот стиль достоин стать в журнале эталоном, имхо.
Ещё одна тема, которой пришлось пожертвовать — свертки и их связь с моноидами. Любознательный читатель может заглянуть в поисках основ в неплохой перевод Катаморфизм в F#, а более глубокое погружение в тему я как-нибудь соберусь с силами и все же накатаю :)
Для дальнейшего чтения еще рекомендуется:
Блог Дэна Пипони. Уникальное место и уникальный человек, без комментариев.
Посты Владимира Матвеева о структурах данных.
Monoids and Finger Trees
Finger Trees: A Simple General-purpose Data Structure — основополагающая статья на тему Finger Tree и концепции измеримых моноидами деревьев вообще.
Ropes: an Alternative to Strings — основополагающая статья по концепции Rope.
Вот теперь уж точно — всем спасибо за внимание :)
И не надо никаких новомодных ухищрений, типа кластеров и параллелизма. Не помогут.
P.S. Конечно, качество FHC оставляет желать лучшего пока что, но я верю, что на последних раундах все-таки так все и будет. По крайней мере для Google Code Jam это 100% верно.
Демонстрация:
>>> inp = "jibw ji jp bw jibw"
>>> solve(inp)
'bwjibwjibwjijp'
Судите сами:
- Задачи — скучные и простые. В формулировках задач баги, их меняют на ходу, во время контеста, причём втихомолку, ничего участникам не сообщив. Была задача, которая предполагала решение динамическим программированием, но тем не менее прекрасно работал жадный алгоритм. Были задачи, условие которых пришлось перечитать 2-3 раза, чтобы понять (иллюстраций в условиях — никаких).
- Тесты — никакие, они иногда почти ничего не проверяют. В задачах утверждают, что количество тесткейсов во входных файлах будет до 100, в реальности оно везде 20. Да даже и 100 для некоторых задач — цифра скучная. В авторских тестах из примера одной из задач — ошибка. Их так и не исправили во время контеста, поэтому мы писали правильное решение на свой страх и риск — хрен его знает, как у них реальное авторское решение и чекер сделаны...
- Система — это вообще тихий ужас. Видимо, написана левой ногой за вечер каким-нибудь фейсбуковским интерном, что ли. В интерфейсе кнопки не работают, чтобы отослать решение, нужно раз 300 нажать на «Submit» — авось с какой-то попытки он таки отреагирует и зачтет ответ (а таймер-то тикает!) Вместо входного файла скачивается html, а в некоторых браузерах вообще ничего не скачивается. Некоторые браузеры теряют посылки, даже если кнопка «Submit» умудрилась сработать =) В scoreboard квалификационного раунда показывались лишь первые 10 человек, хотя участвовало явно побольше.
- В итоге всего этого безобразия организаторы не выдержали и прекратили контест на 20 минут раньше положенного. Это вообще ни в какие ворота не лезет. Какая бы кривая у вас там ситуация не была — дайте, в конце концов, людям писать! Потом раунд и отменить можно, если что.
В общем, я уже ничего хорошего от этого Hacker Cup не жду. Следующие раунды писать буду из принципа, уже любопытно просто, чего они там на этот раз отчебучат :)Просто отсортировать строки, но не со стандартным компаратором, а с компаратором вида a + b < b + a
Я когда бор пишу, он у меня от силы несколько десятков строк занимает.