Первый день госолимпиады по информатике
Сначала в несколько нестандартном формате, прошу простить.
Во-первых, организация, выполняемая Резекненской высшей школой, сосёт.
Во-вторых, я идиот, убейте меня, кто-нибудь, но в то же время я гениален. Я за десять минут до конца заметил, что не учёл одну маленькую деталь в том громоздком решении третьей задачи, которое я писал последние пару часов, нарисовал пример и понял, что эта «деталь» на самом деле является решением. Стёр почти всё, что было, и реализовал его (это заняло шесть минут). Основу обоих алгоритмов составлял поиск в глубину. Затем я посмотрел ещё раз на код, увидел две минимальных оптимизации, лениво реализовал одну и перезаслал. Результат: 96 пунктов, ибо в одном тесте переполнение стека. Разумеется, вторая оптимизация, заключающаяся в убирании локальных переменных из поиска в глубину, уменьшила бы потребление стека в несколько раз (по моим расчётам в 2,86 раз, но, учитывая, что переполнение по моим расчётам не должно было произойти, вероятно, GCC использовал ещё больше памяти в своих целях, чем я учитываю, и тогда экономия была бы меньше). Более того: одним из действий, которые я сделал, переходя от старого алгоритма к новому, был перенос этих переменных из глобальной области определения (где их был целый массив) в локальную. TL;DR: я за десять минут до конца придумал решение третьей задачи и в течение шести минут его написал (с использованием части старого кода); однако я, не подозревая того, сделал всё, чтобы вызвать переполнение стека, и таки получил его на одном тесте.
Мои очки: 100, 100, 96, итого 296.
Очки Эдика: 100, 100, 0, итого 200.
Где-то недалеко за мной Нормунд (но 100 очков у него только за вторую задачу), за Эдиком - Карлис (Сенько) и Петерис.
Напоминаю наши официальные имена: Oļegs Ošmjans, Eduards Kaļiņičenko, Normunds Vilciņš, Kārlis Seņko, Pēteris Eriņš.
А теперь в более привычной форме…
В полвосьмого к назначенному месту подъехал автобус, на котором многие рижане собирались ехать на олимпиаду в Резекне. Мы ехали где-то с без десяти минут восьми до половины двенадцатого. В Резекне автобус заехал в тупик на улице, соседней с той, на которой находится Центр информационных технологий Резекненской высшей школы, там водитель вышел, спросил у людей возле Центра, как к ним подъехать, и довёз нас до Центра по правильной улице. Там нас никто не встречал. Случайно оказавшийся рядом Эдик, вообще-то идущий в общежитие, повёл нас на регистрацию в здание экономического факультета РВШ. Разумеется, пройдя через дыру в заборе, мы пересекли то самое место, где водитель автобуса выходил, чтобы спросить дорогу. В РВШ мы зарегистрировались, но почему-то не всем сказали, что надо платить и что будут выданы (при оплате) талоны на еду. В итоге все таки получили талоны и пошли обедать. Опять же никто нам не показал дорогу и вообще ни слова не сказал… да, в общем-то, ни о чём. Следуя за Эдиком, мы попали в ресторан «Латгале» и пообедали. Забавно, что официантка сначала давала тарелку с едой, а уже потом просила талон, к тому же она, похоже, не слишком пристально проверяла талоны, так как я ей случайно отдал талон на обед второго дня и заметил это далеко не сразу. После обеда, всё ещё не видевшие ни одного официального лица за пределами обеденного стола (и никем не ведомые), мы добрались обратно до РВШ и сели в зал в ожидании церемонии открытия. На церемонии, в частности, Мартынь Опманис убеждал нас в замечательности выезда олимпиады за пределы Риги и упомянул, что с прошлого года организация и в особенности денежные вопросы сильно изменились. Да, мы заметили! Организация, похоже, просто испарилась, причём прихватила с собой деньги. В этом году за проживание и питание надо платить самим участникам. Он также рассказал, что ещё пару лет назад в МОН не хотели даже слышать о проведении государственной олимпиады за пределами Риги. И правильно делали, считаю я. Самое загадочное предложение я, к сожалению, в точности не воспроизведу, но оно было похоже на «Если бы олимпиаду проводило министерство, то разве могли бы вы получить медали с дизайном, сделанным мной?»
Сами соревнования проходили в двух местах: у небольшой части участников там же, где была регистрация и открытие, а у остальных в Центре информационных технологий РВШ. До Центра нас (наконец-то!) кто-то довёл, и мы сели решать задачи. Всё как обычно: пять часов, три задачи, по сто пунктов за каждую задачу. Про задачи скажу лишь, что либо я стал лучше решать, либо задачи стали легче, либо и то, и другое. В то же время, как я уже сказал, полное решение третьей задачи я придумал только за десять минут до конца пяти часов… но оно было очень простое. Если бы я был чуть-чуть внимательнее, я бы придумал его раньше - хотя бы потому, что ту самую идею, которой мне не хватало, я уже один раз рассматривал, просто не понял, что её одной вполне хватает для полного решения.
После соревнований мы пошли ужинать, а потом на автобусе доехали кто до Дома спорта РВШ (хотя мне из автобуса показалось, что он ничем не отличается от обычного школьного спортзала), кто до общежитий на Московской улице (часть людей ночевала возле Центра информационных технологий). К слову, эти общежития - единственный посещаемый нами объект, не находящийся на аллее Освобождения. Все участники, кроме нас с Эдиком, перед этим ещё поблуждали в поисках автобуса; мы же задержались в ресторане, а когда вышли, как раз наткнулись на остальных, возвращавшихся к ресторану, чтобы там дождаться автобуса. О том, что происходило в Доме спорта, возможно, напишет Эдик; во всяком случае, я там не был. В общежитии Эдика беспроводной Интернет был, а вот на Московской улице его не было. Зато из стены торчала витая пара, но, насколько я понял, к ней тоже просто так подключиться было нельзя.
Дополнение, написанное 12 марта в Риге: я перестал понимать, где именно мы ночевали. На выданных нам листочках с адресом общежитий написано Maskavas iela 22. На карте на том же листочке (явно распечатанной из Гугла, хотя логотипа не видно) они обозначены в месте, которое карты Гугла идентифицируют как Maskavas iela 16-18. С сайта 1188 старую карту убрали, оставив только карту Гугла, а при поиске объектов возле интересующей меня точки выдаётся Rēzeknes augstkola (так!), studentu viesnīca по адресу Maskavas iela 22. На первом этаже того здания, где мы ночевали, на стене большими буквами было написано RA (или Rēzeknes Augstskolas, точно уже не помню) Inovāciju centrs.