Зимова школа з програмування, день 5
Автором задач четвертого змагального дня був Андрій Лопатін із Санкт-Петербурзького державного університету. Темою лекції були алгоритми роботи з рядками, а саме методи пошуку підрядків у тексті. На початку було поставлено запитання, хто знає, що таке суфіксне дерево — піднялося трохи рук, а що таке суфіксний автомат, готові були відповісти лише одиниці.
Спершу розповіли про алгоритм пошуку Кнута — Морріса — Пратта, також відомий як z-функція, але і це було складно для розуміння, бо раніше я з ним не стикався, а складніша частина лекції пройшла повз. У ній ішлося вже про пошук багатьох підрядків, де розбиралася побудова суфіксних дерев і робота суфіксного автомата, було згадано суфіксний масив. Загалом, тема дуже корисна для будь-якого програміста, тільки за одну лекцію її вивчити практично неможливо. Тому вважаю, що такий пошук рядків варто було б розглянути в моєму університеті на теорії алгоритмів, ну а вивчення ймовірнісних автоматів замінити вивченням суфіксного :-)
Під кінець лектор дав назви корисних книжок із цієї теми: Д. Ґасфілд «Рядки, дерева та послідовності в алгоритмах. Інформатика та обчислювальна біологія» й книга англійською, що добре розглядає суфіксні автомати: «Applied Combinatories on Words», але, практично, без жодних доведень.
Загалом, лекція пройшла на високому рівні, і стало добре видно, чому пітерський університет був чемпіоном світу.
На самих змаганнях було надано 11 задач про царів Петю та Васю, умови були поставлені добре, та історії про ворогуючих царів практично не відволікали від розуміння умови.
Думаю, передусім варто відзначити, що на 55 хвилині з першої спроби наша команда відіслала правильне розв'язання однієї із задач і отримала перший бал в основній частині змагань та повітряну кульку. У задачі потрібно було знайти периметр прямокутника, що обмежує задану множину точок. Більше в основному турі повністю правильні розв'язання решти задач нами отримані не були, але ми опинилися попереду тренера, який не надіслав правильного розв'язання в основний тур.
Тепер про те, що потрібно було знати для розв'язання решти задач. Перша задача мала розв'язуватися динамічним програмуванням і використанням геометричних формул обчислення кутів і довжин відрізків. Для решти задач, загалом, потрібне було динамічне програмування, код Брюхера, побудова дерев, робота з полярними координатами у тривимірному просторі, знаходження перетину відрізка та кола, ну і, як завжди, робота з графами, за які ми й не бралися.
Одну задачу також добили потім, бо вона розв'язувалася повторенням ітерацій до певної точності й мала таймліміт 2 секунди, на основному турі до такого легкого розв'язання не додумався, але після обґрунтувань лектора й тренера задачу розв'язав. Ще один цікавий момент сплив, що умовою однієї задачі можна було знехтувати й робити алгоритм для іншої, легшої задачі, і обидва алгоритми однаково проходили авторські тести.
Під кінець дня згідно з рейтингом цього дня ми розділили 28 місце ще з однією задачею, у дорозв'язуванні 24 місце, а в загальному заліку в нас 31 місце з 49 можливих.
На початку підбиття підсумків оголосили, що в задачі К першого дня 34 тест неправильний і результати будуть переглянуті. Приз за найкраще розв'язання, навіть коротше за авторське завдяки процедурам, отримали DefaultDream ХНУРЕ. Ну, а найкращий результат дня показали Scorpions з ЛНУ. Після нагородження лектор продовжив розповідати про втрату точності в обчисленнях і потім перейшов на тему про саму ситуацію зі спортивним програмуванням, досягнення в написанні програм за останні роки. Були розказані історії про випадки на змаганнях минулих років. Зачепили й зв'язок математики та програмування.
Ведучий запропонував цікаву гру для розвитку командної роботи. У ній треба написати програму, але учасники мають писати рядки коду по черзі й не можуть спілкуватися.
З розмов про ігри вийшов висновок, що позиційний аналіз має дуже важливе значення й може замінити перебори та інше. Для кожної гри й ситуації існує свій позиційний аналіз. Але проти позиційного аналізу в хрестиках-нуликах існує чит — розставляти нулики ходами коня.
Загалом, видався день із найдовшими, найцікавішими та найкориснішими лекціями завдяки Андрію Лопатіну. Після його виступу були вручені призи переможцям минулих днів, і Школу на сьогодні було завершено.
Надворі нас зустрічав сніг, що почався надвечір і вже добре притрусив усе.
Редагувалося 22.02.2008