Зимняя школа по программированию, день 5
- Местоположение: Kharkov
Автором задач четвёртого соревновательного дня был Андрей Лопатин из Санкт-Петербургского государственного университета. Темой лекции были алгоритмы работы со строками, а именно методы поиска подстрок в тексте. В начале был задан вопрос, кто знает, что такое суффиксное дерево - было поднято немного рук, а что такое суффиксный автомат были готовы ответить только единицы.
В начале было рассказано про алгоритм поиска Кнута - Морриса - Пратта так же известный как z-функция, но и это было сложно для понимания, так как раньше не сталкивался с ним, а более сложная часть лекции прошла мимо. В ней рассказывалось уже про поиск многих подстрок, где разбиралось построение суффиксных деревьев и работа суффиксного автомата, был упомянут суффиксный массив. В общем, тема очень полезная для любого программиста, только за одну лекцию ее изучить практически невозможно. Поэтому считаю, что такой поиск строк следовало бы рассмотреть в моем университете на теории алгоритмов, ну а изучение вероятностных автоматов заменить изучением суффиксного :-)
Под конец лектор дал названия полезных книг по данной теме: Д. Гасфилд "Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология" и книга на английском, хорошо рассматривающая суффиксные автоматы: "Applied Combinatories on Words", но, практически, с никакими доказательствами.
В общем, лекция прошла на высоком уровне, и стало хорошо видно, почему питерский университет был чемпионом мира.
На самих соревнованиях было предоставлено 11 задач про царей Петю и Васю, условия были поставлены хорошо и истории про враждующих царей практически не отвлекали от понимания условия.
Думаю, в первую очередь следует отметить, что на 55 минуте с первой попытки наша команда отослала верное решение одной из задач и получила первый бал в основной части соревнований и воздушный шарик. В задаче требовалось найти периметр прямоугольника, ограничивающего заданное множество точек. Больше в основной тур полностью правильные решения оставшихся задач нами получены не были, но мы оказались впереди тренера, не отправившего правильное решение в основной тур.
Теперь о том, что требовалось знать для решения остальных задач. Первая задача должна была решаться динамическим программированием и использованием геометрических формул вычисления углов и длин отрезков. Для остальных задач, в общем, требовалось динамическое программирование, код Брюхера, построение деревьев, работа с полярными координатами в трехмерном пространстве, нахождение пересечения отрезка и окружности, ну и, как всегда, работа с графами, за которые мы и не брались.
Одну задачу так же добили потом, так как она решалась повторением итераций до определенной точности и имела таймлимит 2 секунды, на основном туре до такого легкого решения не додумался, но после обоснований лектора и тренера, задачу решил. Еще один интересный момент всплыл, что условием одной задачи можно было пренебречь и делать алгоритм для другой более легкой задачи, и оба алгоритма одинаково проходили авторские тесты.
Под конец дня согласно рейтингу в этот день мы разделили 28 место с еще одной задачей, в дорешивании 24 место, а в общем зачете у нас 31 место из 49 возможных.
В начале подведения итогов объявили, что в задаче К первого дня 34 тест неправильный и результаты будут пересмотрены. Приз за лучшее решение, даже короче авторского за счет процедур, получили DefaultDream ХНУРЭ. Ну, а лучший результат дня показали Scorpions из ЛНУ. После награждения лектор продолжил рассказывать про потерю точности в вычислениях и потом перешел на тему о самой ситуации со спортивным программированием, достижениях в написании программ за последние года. Были рассказаны истории про случаи на соревнованиях прошлых лет. Была затронута и связь математики и программирования.
Ведущий предложил интересную игру для развития командной работы. В ней надо написать программу, но участники должны писать строки кода по очереди и не могут общаться.
Из разговоров об играх вышло заключение, что позиционный анализ имеет очень важное значение и может заменить переборы и прочее. Для каждой игры и ситуации существует свой позиционный анализ. Но против позиционного анализа в крестиках-ноликах существует чит в виде расстановки ноликов в виде ходов коня.
В общем, определился день с самыми длинными, интересными и полезными лекциями благодаря Андрею Лопатину. После его выступления, были вручены призы победителям прошлых дней, и Школа на сегодня была закончена.
На улице нас встречал уже хорошо заметный идущий снег, начавшийся под вечер.
Редактировалось 22.02.2008