Вот и заканчивается IOI 2013. Расскажу кратко о том, что произошло с момента предыдущего поста (начала открытия). Открытие оказалось достаточно коротким, что всегда радует участников олимпиады. После открытия лидеров повезли на очередное собрание GA (General Assembly — собрание лидеров команд), посвященное разбору проблем пробного тура, а затем дали возможность ещё раз встретиться с участниками и обсудить услышанное на собрании, и дать последние наставления своей сборной (как правило, самое главное наставление в таких случаях — будьте готовы к любым проблемам, и используйте своё самое мощное оружие — мозг). После того, как участников увели в карантин (изолировали от любых коммуникаций с внешним миром), началась самая тяжёлая часть для лидеров команд и тех, кто изъявил желание помогать им в переводе задач на национальные языки.
В этот раз от России приехали трое тренеров, что позволяет перевести все три задачи на русский язык уже в процессе, когда задачи предлагаются для ознакомления членам GA, чтобы те могли высказать свои замечания. С самим переводом особых проблем не возникло, однако к сожалению, после этого нужно ещё и залить сделанные переводы в wiki, которая с прошлого года используется для этих целей. Вот тут-то и поджидали нас проблемы, потому что, как выяснилось, часть фраз (поначалу — целые разделы) в принципе невозможно было залить в эту систему (они в итоге оказывались по-английски). По мере сообщения о наличии таких фраз организаторы пытались исправлять эти проблемы, однако даже в финальном варианте условий осталась пара непереводимых заголовков таблиц. Кроме того, ближе к концу перевода в системе перестала также работать генерация pdf-условий (генерировались странные ошибки или просто устаревшие версии условий), поэтому pdf пришлось генерировать вручную. Когда в два часа ночи (через 7 часов после того, как задачи были выданы) мы наконец закончили перевод, мы ушли с надеждами, что хотя бы у участников завтра проблем не будет. К сожалению, эти надежды были ложными.
Первый тур начался с задержки на час, в то время, как гостей привезли в 9 утра на экскурсию к музею, который открывается в 10 (поразительное сходство). Поначалу таблица результатов не работала, впрочем, мы не сильно переживали по этому поводу — такое уже бывало ранее. Однако заработав через полтора часа на несколько минут, таблица результатов обновляться перестала, и стали распространяться печальные слухи, что участники тоже испытывают проблемы. К сожалению, это оказалось правдой — тестирование во время большей части тура работало очень медленно, с задержками на час и более. По завершению тура участники были очень злые, а гостей для создания аналогичного настроения привезли последним пунктом экскурсии в планетарий, котороый как раз ровно в этот день оказался выходной. Дальше я ничего не помню — пошёл спать :)
В день между турами всех повезли на пляж, на котором даже можно было купаться в океане, несмотря на то, что в Австралии сейчас зима. Там было хорошо, единственный недостаток, что ланч представлял собой два твёрдых куска льда — один из которых являлся сэндвичем, а второй — соком. Впрочем, с едой тут почти всегда какие-то проблемы :(
Правда, время возвращения с пляжа было рассчитано плохо. По расписанию, лидеры и им сочувствующие должны были приехать в университет в 16.00 при отъезде с пляжа в 15.00, однако в реальности ехать пришлось два часа. И опять состоялось уже второе собрание по задачам, однако в этот раз всё прошло не так гладко. По третьей задаче (game) поступило некоторое количество жалоб на то, что она слишком стандартная, а также при выданных ограничениях в ней проходит решение "в лоб". В результате научный комитет предоставил в качестве опции запасную задачу на замену, но она оказалась хорошо использованным баяном, по крайней мере, она встречалась на национальных сборах как минимум пяти стран, в том числе российских. Поэтому, решено было менять ограничения и переделывать тесты к задаче game. Уж не знаю, как это связано, но в результате до полуночи нельзя было вводить в систему фразы перевода этой задачи, а желающим ввести в своё условие на национальном языке финальные ограничения вообще было предложено либо ждать 7 утра, либо идти спать, добавив фразу "см. английское условие для того, как устроено разбиение на подзадачи". Впрочем, даже выбрав "идти спать", мы всё равно пошли спать в 4 часа ночи, как это ни печально. В итоге, проснувшись на следующее утро в 8 и увидев проливной дождь и небо без единого просвета, я решил не ехать на второй пляж, экскурсия на который была организована для гостей, и проспал почти весь день.
Окончательный наш результат — три золотых медали (KAN zemen malcolm) и одна из первых серебрянных (tunyash), второе командное место (после Китая). При этом KAN разделил третье место в абсолютном зачёте.
Очень высокий результат, хочется пожелать ребятам, и тем, кто с ними работал, родителям, педагогам, дальнейших успехов! Для нас сейчас очень важно сохранить высокий уровень подготовки и высокие результаты, для которых, на мой взгляд, очень важно наличие трёх следующих глобальных начинаний:
Летняя компьютерная школа (ЛКШ), которая хоть и не ставит своей целью подготовку к олимпиадам, тем не менее, играет большую роль в обучении школьников алгоритмам и популяризации информатики. А также просто настраивает людей на хорошее :)
Интернет-олимпиады (и другие командные олимпиады) школьников по информатике, которые стали достаточно массовыми и проникают в самые отдалённые уголки нашей страны.
И конечно, самое важное — это команда тренеров, которые на самом высоком уровне занимаются непосредственно подготовкой всероссийских сборов школьников по информатике!
Очень надеюсь, что мы сможем и дальше двигаться вперёд и покорять всё новые и новые вершины. Не хотелось бы, чтобы нас постигла печальная участь Польши, которой в итоге не досталось ни одного золота. Ещё раз подчеркну, для всех, кто участвует так или иначе в процессе подготовки школьников, студентов, в своей школе, регионе, вузе или на всероссийском уровне: всё, что вы делаете — важно. Помните, что вы работаете для конкретных людей, которые через много лет обязательно скажут вам спасибо! А пока, зная, как редко благодарят педагогов собственные ученики непосредственно в процессе обучения, говорю огромное спасибо вам всем от себя лично :) Мы с вами победим!
Если не секрет, то хорошо использованный баян, в том числе и на российских сборах, предоставленный на замену — это что за задача?
Как я понял она в точности повторяет задачу 3 с финала FHC 2011 (про вечеринку).
А можно ссылку?
А какие изначально ограничения были в game и какая тупость там проходила, если не секрет?
Полагаю, просто хранить все числа вместе с координатами в одномерном массиве, а при запросе просматривать их все и считать НОД тех, координаты которых попадают в нужный прямоугольник. Может быть максимум 22000 чисел и 250000 запросов — получается 5,5 млрд. раз выполнить 4 сравнения и посчитать НОД за 13 секунд. Я пробовал такое заслать, но, ясное дело, прошёл только первый субтаск.
10000 изменений и запросов в сумме, 2 секунды. Какая тупость — неизвестно, ее предложили тренеры команды Австралии, и научный комитет согласился, что проблема есть. Но, скорее всего, при таких слабых ограничениях — почти любая, НОД не так долго работает, как может поначалу показаться.
Нод n чисел работает за O(n + log(maxValue)), потому что каждый вызов либо сразу обрывается, либо уменьшает ответ.
Поздравляю команду России! Желаю и в дальнейшем достигать таких результатов!