Зимова школа з програмування, день 6

В останній день змагань автор задач знову був із СПбДУ. Цього разу прибув призер міжнародних чемпіонатів, тренер чемпіонів світу, голова та член журі різних російських чемпіонатів, найкращий тренер минулого року Андрій Станкевич, і це не всі заслуги лектора.

Темою цієї лекції була «Структури даних для статистик на відрізках».

Лекція тривала до останнього й була проведена на дуже високому рівні, усі питання було розглянуто досить докладно на відміну від попередніх, але сприйняття матеріалу такого рівня передбачало знання певних основ і наявність досвіду, що не дозволило більшості, як мені здається, присутніх зрозуміти зміст лекції, у тому числі й нам. Можу зауважити, що під кінець лекції було розказано про багатовимірне дерево відрізків. Загалом, наголос робився на використання структур та оптимізацію програми за часом.

На основному турі змагань було представлено десять задач англійською мовою, умови були як стандартні, так і без сюжету. Сам рівень задач відповідав рівню автора, у підсумку хоча б одну задачу змогло розв'язати близько чотирнадцяти команд. Ми ж, навіть якщо й знали, як зробити робочий алгоритм, то розуміли, що він не пройде за часом або знадобиться для виконання нашого варіанту 4 ГБ пам'яті, при 256 МБ дозволених. У підсумку більшість задач ми й не могли намагатися розв'язувати. В одній чи парі вимагалася робота з графом, але й це б не допомогло. Для багатьох задач вимагалася робота зі структурами, а цього ніхто з нас не міг робити, та й з оптимізацією досвіду роботи не було. Пам'ятаю, тільки у ФТЛі вчили писати оптимальні й універсальні програми, а не програми, які не функціонують при критичних вхідних даних.

Лекція, що розбирала розв'язки задач, була найдовшою (закінчилася о 17:00) та найдокладнішою. Розглядався розв'язок кожної задачі до дрібниць зі згадуванням нюансів, але знову ж таки за рівнем розв'язки перевершували знання більшості учасників і докладний розбір мало чим допоміг, хіба що викликав у декого головний біль. Під кінець було відзначено, що весь контест складався зі злегка змінених задач Петрозаводських зборів.

На дорозв'язуванні мало хто займався розв'язанням сьогоднішніх задач із зазначених вище причин, та й частина команд від'їжджала сьогодні. Ми ж зайнялися дотисканням спонсорської задачі, оскільки вдень було тільки три її розв'язки. У підсумку більшість часу дорозв'язування пішла на організацію читання чисел, розділених комами. Після цього вийшла майже робоча програма, після швидкої модифікації основного алгоритму програма виявилася робочою, хоч розв'язок вийшов не найоптимальніший, але основні цікаві тести проходив. Після цього вихідник відправлено з двох моїх скриньок на потрібне мило. На вечерю я й тренер (решта команди покинула дорозв'язування задовго до завершення розв'язання спонсорської задачі) прибули пізніше за всіх, коли більшість народу покинула їдальню. Після швидкої вечері попрямували на підбиття підсумків.

Як не дивно, заключна частина дня виявилася доволі короткою порівняно з попередніми. Команда VIP із ДонНУ отримала однограмовий платиновий злиток за найкращий розв'язок задачі, оскільки їхній код задачі C вийшов лаконічнішим за авторський. Найкращою командою дня вкотре вийшла команда Pointless КНУ з розв'язаними дев'ятьма задачами. Після цього останній день змагань був завершений, і ми вирушили до готелю, де цього разу не робили спроб почати холівар, а обговорювали досягнення й враження від індустрії інтерактивних комп'ютерних розваг і не тільки, наприклад, провели пару тестів фотокамер.

Тепер лишилося чекати закриття Школи, де буде оголошено місця, які посіли учасники, й підбито заключні підсумки, ну й буде роздача пряників. Тільки сумніваюся, що останній день змагань сильно вплинув на статистику рейтингів команд.

Редагувалося 22.02.2008