Зимняя школа по программированию, день 4
- Местоположение: Kharkov
Утро ничем не отличалось от остальных. Разве что было чистое небо, благодаря этому на улице сделал неплохие снимки гостиницы немного закрытой деревьями, и близлежащей арены.
Так же сфотографировал двор и часть зданий университета, внутри от охранника узнал, что держать включённую фотокамеру в помещении можно только со специального разрешения. Интересно, в ХНТУ такие же строгости?
Сегодня были задачи от автора с КПИ, но так как он сам прибыть не смог, лекцию и разбор проводил один из членов команды ИПСА того же университета.
На лекции были рассмотрены задачи на инверсии в перестановках, более сложная вторая тема не было затронута, так как проводивший лекцию не был уверен в своих знаниях этой темы.
В основном туре было представлено 7 задач на английском языке, через это выкрутасов в условиях не наблюдалось. Если рассматривать их в общем, то в целом задачи вышли легче предыдущих дней, но с решениями не заладилось, так как они не проходили таймлимиты. Знание решения задачи не помогали, так как алгоритмы нужно было оптимизировать или решать другими способами, используя специальные формулы и свойства. Примечательно, что в одном тесте была ошибка, из-за чего одну задачу лидерам засчитали после разбора.
Но мы все же до решения одной задачи додумались, поговорив с тренером, уже перед разбором. Как оказалось, решение не соответствовало авторскому, но соответствовало решению, предложенному ведущим лекцию, так как в этой задачи не было убийственных тестов, это решение успешно проходило. На дорешивании с некоторой попытки алгоритм был правильно реализован и задача зачтена. В итоге тренер и наша команда в рейтинге дорешивания числятся соответственно где-то на 27-28 местах.
Теперь о том, что следовало бы знать для решения сегодняшних задач. Кроме упомянутых оптимизации алгоритмов и инверсии в перестановках, следовало знать о перманенте матрицы и формуле Райзера. Не плохо было бы умение считать количество возможных четырёхугольников с заданного количества отрезков разной длины, что считалось через полиномы, ну и прочее свойства переборов, сортировок и т. п. Но решения были сильные, так как и объяснявший участник авторской команды не все их понимал и предлагал свои решения.
О подведении итогов. Только что на доске написали адрес www.olimp.sc170.kharkov.ua - информационный сайт Школы с форумом. Победителями дня стала снова команда Pointless КНУ им. Шевченка. Все задачи решило 2 команды, а хотя бы одну задачу в основное время решило 22 команды, что почти в 2 раза больше, чем за прошлые 2 дня. За волю к победе наградили картиной Николаевского собора города Харькова команду RockWellTeam ЛНУ, которые правильное решение одной задачи отправили на последних минутах. Завтрашний автор уже выехал и точно будет.
P.S. Вітаю шанувальників біатлону зі здобуттям нашими жінками срібла в естафеті:-)
Редактировалось 22.02.2008