Зимняя школа по программированию, день 3
- Местоположение: Kharkov
День начался, как и большинство прошедших: с песни Circle of Life из бродвейского мюзикла, которая была быстро прекращена выключением сигнала будильника в мобильном:-) И эта ночь была теплее за счет повышения температуры труб за счёт приходящих морозов.
Лекция началась с "вiдпалу" львовской команды, капитан которой был автором этого дня.
Все началось с представления "перекладача", который в основной перекладывал задания с места на место, но на лекции он переводил капитана команды с украинского на английский для гостей с Грузии и России. После весёлой речи, сопровождаемой переводом, было объявлено, что задачи будут очень легкие и лекции по алгоритмам не будет. Но ценная информация для многих участников соревнования была дана - на доске написали, как в Си открыть файлы для чтения и записи. Наша команда согласилась, что эта лекция оказалась полезнее предыдущей. Под конец выступал тренер грузинской команды, который вручил всевозможные дипломы той же команде из города льва, которая на у них на соревнованиях заняла первые места, но не успела забрать документы, подтверждающие это.
На самих соревнованиях было дано 7 задач различной сложности, в условиях которых рассказывалось про кумовей, сало и горилку. Конечно же, все условия были на государственном языке. Это решение прошло лучше, так как хотя бы некоторые задачи частично решили - две заваливалось на 11-м тесте, а одна или парочка на первом или втором. В итоге результат тот же, жаль, что дают очки только за прохождение программой всех тестов, а не за каждое прохождение одного из тестов, как на остальных соревнованиях.
Про задачи писать не буду, отмечу только моменты, которые следовало бы знать. Больше всего времени, я потратил на задачу, которую надо было решать Венгерским алгоритмом, теперь все же надо с ним разобраться. Так же не хватало знаний формул комбинаторики и упрощения формулы, состоящей с факториалов. Одну задачу надо было решать произведением матрицы в степени на вектор, ну и задачи на работу с графом не обошлось. Требовались знания свойств рядов и работа с троичной системой счисления для одной задачи.
На разборе решения задач были рассказаны методы их решения, но часть решений ссылалась на "общеизвестные" алгоритмы и свойства, а часть решений была представлена самыми сложными способами. В общем, после дорешивания тот же результат, но, похоже, что рейтинг этого дня очень схож с рейтингом предыдущего - только у первых 22 команд есть какие-то результаты, не считая баллы за дорешивание, так как их не запоминал. Но ещё подведение итогов не началось, следующий абзац наберу во время их оглашения.
Согласно наградам, победила команда из университета им. Шевченка. Лучшее решение задачи и самое быстрое оказалось решение четвёртой задачи, про горилку, сделала, как это не странно, команда Львовского национального университета им. И. Франка. Автор задачи, по совместительству тренер и капитан этой команд, отметил, что удивлён от куда взялось на столько оригинальное и быстрое решение.
Пока ясно, какой день претендует на звание самого весёлого.
Редактировалось 22.02.2008