Отборочный тур LIO 2009: день второй, а также дополнения к записи про день первый
Вот и закончился второй день отборочного тура 22‑й латвийской олимпиады по информатике. Можно подводить итоги, поздравлять победителей и готовиться к балтийской олимпиаде по информатике, которая пройдёт с 18‑го по 22‑е апреля в Стокгольме (столица Швеции - для тех, кто не в курсе).
Во вчерашней записи я исправил одну орфографическую ошибку и несколько типографического плана, а ещё добавил, что в регистрационных списках моим учителем была записана Айя Лусе, хотя на LIO и на награждениях прошлогодних участников и призёров международных олимпиад эта графа оставалась пустой. Ещё я забыл написать (но во вчерашнюю запись не добавляю), что на компьютерах стояло какое-то непонятное программное обеспечение, регулирующее доступ к сетевым портам наружу (ICMP-пакеты проходили свободно в любом направлении, а вот подсоединиться к чему-нибудь, кроме тестирующего сервера, по HTTP, например, было невозможно), и что господин Аттека, когда зашёл в мой кабинет один раз до начала соревнования, строго сказал, что писать код в это время нельзя, на что ему кто-то то ли из жюри, то ли из ISEC ответил, что мы не можем ничего полезного сделать по причине отсутствия у нас условия задач (правильность этого утверждения я комментировать не буду).
Главный результат сегодняшнего дня: в Стокгольм едем мы с Мартынем, Эдиком, Нормундом, Петером и Андреем Валюмом. Полные официальные результаты доступны на сайте LIO, а версия с неофициальным переводом имён на русский - в дневнике Эдика.
Я вчера написал апелляцию по поводу того, что у нас было на шесть минут меньше регламентированного времени на решение задач, с просьбой зачесть мне решение, дописанное в 16:32. Сегодня после выдачи предварительных результатов каждому лично было рассмотрение апелляций, и мою просьбу удовлетворили, в результате чего я потерял пять пунктов в задаче «Дерево». Вчерашние же просьбы Эдика сказать ему количество полученных им очков и выдать детализированные результаты отдельно от выдачи результатов всем остальным удовлетворены не были.
Задачи были в среднем, наверно, чуть сложнее вчерашних (учитывая лёгкость задачи «Скобки»). Первую задачу придумал, видимо, Артур (Верза); это была единственная задача Первая задача была единственная, которую Рихард (Опман) не смог нам рассказать на разборе задач и решений. Как видно из результатов, большинство написало просто «что получится» и только Петер и Мартынь отличились, написав решения, берущие по 84 пункта, хоть и валящиеся на разных тестах. Причём Петер целенаправленно использовал функцию Эйлера (количество натуральных чисел, которые меньше заданного натурального числа и взаимно просты с ним, причём единица считается взаимно простой с любым другим числом), а Мартынь придумал всё решение с нуля. Вторая задача была авторской задачей Сергея Ильича, как он нам потом рассказал, и как-то даже жалко, что её раскрыли, ведь её никто даже частично не решил. Ну, кроме Валдиса Адамсона, получившего 23 очка, но не факт, что это не просто везение - он умудрился и в «Квадратах» каким-то халявным решением получить 68. Ну и, наконец, была третья задача, самая простая, но почему-то её решили только мы с Нормундом. Даже проще, чем вчерашнее «Дерево»: динамическое программирование с одной-единственной двумерной таблицей, O(N²).