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

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

Так само сфотографував двір і частину будівель університету, усередині від охоронця дізнався, що тримати ввімкнену фотокамеру в приміщенні можна лише зі спеціального дозволу. Цікаво, у ХНТУ такі самі суворощі?

Сьогодні були задачі від автора з КПІ, але оскільки він сам прибути не зміг, лекцію та розбір проводив один із членів команди ІПСА того ж університету.

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

В основному турі було подано 7 задач англійською мовою, через це викрутасів в умовах не спостерігалося. Якщо розглядати їх загалом, то в цілому задачі вийшли легші за попередні дні, але з розв'язками не склалося, оскільки вони не проходили таймліміти. Знання розв'язку задачі не допомагали, оскільки алгоритми потрібно було оптимізувати чи розв'язувати іншими способами, використовуючи спеціальні формули та властивості. Прикметно, що в одному тесті була помилка, через що одну задачу лідерам зарахували після розбору.

Але ми все ж до розв'язку однієї задачі додумалися, поговоривши з тренером, уже перед розбором. Як виявилося, розв'язок не відповідав авторському, але відповідав розв'язку, запропонованому тим, хто вів лекцію, оскільки в цій задачі не було вбивчих тестів, цей розв'язок успішно проходив. На дорозв'язуванні з певної спроби алгоритм був правильно реалізований і задача зарахована. У підсумку тренер і наша команда в рейтингу дорозв'язування числяться відповідно десь на 27-28 місцях.

Тепер про те, що варто було б знати для розв'язання сьогоднішніх задач. Окрім згаданих оптимізації алгоритмів та інверсії в перестановках, варто було знати про перманент матриці й формулу Райзера. Не погано було б уміння рахувати кількість можливих чотирикутників із заданої кількості відрізків різної довжини, що рахувалося через поліноми, ну й решта властивостей переборів, сортувань тощо. Але розв'язки були сильні, оскільки й учасник авторської команди, який пояснював, не всі їх розумів і пропонував свої розв'язки.

Про підбиття підсумків. Щойно на дошці написали адресу www.olimp.sc170.kharkov.ua - інформаційний сайт Школи з форумом. Переможцями дня стала знову команда Pointless КНУ ім. Шевченка. Усі задачі розв'язало 2 команди, а хоча б одну задачу в основний час розв'язало 22 команди, що майже у 2 рази більше, ніж за минулі 2 дні. За волю до перемоги нагородили картиною Миколаївського собору міста Харкова команду RockWellTeam ЛНУ, які правильний розв'язок однієї задачі надіслали на останніх хвилинах. Завтрашній автор уже виїхав і точно буде.

P.S. Вітаю шанувальників біатлону зі здобуттям нашими жінками срібла в естафеті:-)

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