Таблица результатов Краткий обзор задачNowruz — это первая со времён канадского maze в 2010 году задача на IOI с открытыми тестами. Забавный факт состоит в том, что nowruz, как и maze, это задача про клетчатый лабиринт. Дано клетчатое поле, в котором некоторые клетки свободны, и нужно оставить от них связное подмножество клеток, образующее дерево (в том смысле, что от любой клетки до любой есть единственный путь). Требуется максимизировать количество листов в получившемся дереве. Оценка линейно зависит от количества листов, при этом в тесте дано, сколько умеет жюри, и результат жюри считается за полный балл на тесте. Говорят, оптимизационная задача, в которой есть много разных подходов, по ощущениям приятнее того же канадского maze.
Wiring — в этой задаче дано несколько различных точек на прямой, часть из которых красная, а часть синяя. Можно соединять красные с синими проводами, стоимость провода равна расстоянию между точками. Нужно провести сколько-то проводов, чтобы к каждой точке был подсоединён хотя бы один провод, и суммарная стоимость проводов была как можно меньше. Утверждается, что последовательным прохождением групп можно прийти к динамике с жадными соображениями, которую потом подсчётом частичных сумм и каких-то минимумов можно довести до линейного (после сортировки) решения.
Trains — эта задача выглядит самой исследовательской и интересной из сегодняшних. Дан ориентированный граф, часть вершин которого принадлежат A, а часть — B. Также часть вершин является отмеченными. Они играют в игру — есть фишка, которая исходно стоит в вершине s, на каждом ходу игрок, который владеет текущей вершиной, выбирает одно исходящее ребро, активирует его и перемещает фишку вдоль этого ребра. Как только фишка окажется в ранее посещённой вершине, игра заканчивается, и рассматривается образовавшийся цикл из активных рёбер. Если на нём есть хотя бы одна отмеченная вершина, выигрывает A, а иначе — B. Нужно определить для каждой стартовой вершины s, кто выиграет при правильной игре.
Также имеются подзадачи: граф простого специфичного вида, перебор/динамика по подмножествам, все вершины принадлежат A, все вершины принадлежат B, есть ровно одна отмеченная вершина и без дополнительных ограничений. Довольно легко решаются первые три подзадачи, а четвёртая и пятая являются ключом к решению всей задачи.
SPOILER ALERT: в комментариях и теле этого поста, скорее всего, будут обсуждаться задачи соревнования, поэтому если вы участвуете в каком-либо онлайн-зеркале, либо хотите порешать задачи самостоятельно, будьте к этому готовы.
05:00: В итоге Вова на последнем часу сдал вторую задачу на сотню, чем поднял себя до 21 места. Далее следуют Денис на 28, Егор на 36 и Саша на 54 местах. Это очень хороший результат, у всех без исключения есть шансы на золото, для чего мальчикам надо сохранить имеющийся темп или чуть-чуть его улучшить, а Саше попытаться отыграться за счёт какой-нибудь задачи во второй день. До встречи во вторник!
04:24: У всех ребят, кроме voidmax, приличный набор подзадач по последней задаче. Надеюсь, Вова сейчас закроет эту дырку и поднимется мест на 30-40.
03:29 Саша сдаёт посденюю на 39 и поднимается ещё вверх. Сейчас бы ей сдать на причный балл, наконец, novruz, и тогда она окажется вообще в золоте.
03:07 arsijo сдаёт задачу Wiring на полный сдал, в результате чего поднимается на второе место.
02:46 Egor.Lifar практически добил nowruz, у него 92 и это текущий рекорд по этой задаче. Denisson чуть-чуть улучшил свой результат по trains и сейчас находится на пятом месте.
02:40 Полтура позади. У yutaka1999 появились 20 баллов по Nowruz, кажется, добить их до 80+ для него это дело техники. У Саши, тем временем, появились 11 по последней. Ей бы сейчас переключиться на первую и набрать халявные баллы — это может сильно придать уверенность на второй половине тура.
02:22 Egor.Lifar досдал несколько тестов по Nowruz и поднялся на 32 место. При этом у Егора есть ещё несколько тестов, которые он не сабмитил вообще. За ним следом voidmax сдаёт вторую задачу на 7 баллов Вова.
02:09 yutaka1999 полностью решил wiring и (внезапно) train и лидирует почти на сто баллов.
02:04 В топ-3 попадает arsijo, набравший 84 балла по первой и 30 баллов по второй. У наших ничего принципиально не меняется, только Денис сдаёт вторую на 13, и Егор принимается за первую.
01:31 Ничего интересного не происходит. По задаче train рекордный балл у китайского участника consecutivelimit, он решил все группы, кроме четвертой и последней (которая стоит, к слову, 51 балл).
01:16 ВНЕЗАПНО появилось три сотни по wiring. Для полного решения нужно сперва выписать квадратную динамику, после чего применить какую-то из стандартных оптимизаций.
01:10 voidmax почти догоняет Denisson по первой задаче, сейчас они 8 и 2 места соответственно. Интересно, что Вова сразу послал все тесты в среднем на 6.5 баллов, тогда как Денис предпочитал сдавать по одному тесту, но со сравнительно более высоким средним баллом. Для Дениса сейчас самое время оставить свои решения в фоне искать ответ получше и заняться другими задачами.
01:05 Тем временем, у всех российских школьников уже не ноль: voidmax тоже бросился на nowruz, сдав на максимально возможный балл один из тестов, а demon1999 и Egor.Lifar предпочли задачу wiring, набрав по ней по 13 баллов.
01:00 Denisson продолжает продвигаться по nowruz, заслав еще два теста на примерно 9 баллов из 10. Сложно сказать, что у него происходит, но решать все тесты индивидуально может оказаться слишком затратно по времени. Уже четыре участника имеют по этой задаче порядка 80 баллов. В топ10 из дружественных сборных замечены Денис, kefaa и saba_tavdgiridze.
00:58 Egor.Lifar получил 13 баллов по wiring, это группа на одну простую формулу, которая тем не менее очень важна для полного решения.
00:55 Иранский участник ITDOI уже имеет больше 80 баллов по nowruz и с большим отрывом лидирует. По остальным задачам пока открыты только простые группы.
00:53 Если я правильно понимаю, то зарегистрированных участников 312 человек, а значит, можно легко посчитать количество медалей каждого вида, зная, что они соотносятся в пропорции 1:2:3:6. Таким образом, 26 место это последняя золотая медаль, 78 место это последняя серебряная и 156 место это последняя бронзовая.
00:46 Denisson открыл счёт среди участников нашей сборной, начав сдавать задачу nowruz. Эта задача примечательна не только тем, что в ней partial scoring, но также тем, что это первая с 2006 2010 года задача с открытыми тестами на IOI. Как видно из таблицы результатов, по ней можно довольно быстро набрать неплохой балл, но мы опасаемся, что при неудачном стечении обстоятельств на ней можно сильно застрять. У Дениса к текущему моменту засланы ответы на первые два теста из десяти.
00:42: У российской сборной пока ещё нули. Из дружественных сборных отметим sancho и Arthur, которые начали с решения простой второй подзадачи в задаче Wiring.
00:31: Таблица как-то заработала. Пока что все баллы не превышают 20, а на первом месте участник из Бангладеша.
00:27: Говорят, задержки вызваны наличием второй площадки проведения. Напомню, что в этом году впервые в истории IOI помимо основной площадки в Тегеране есть альтернативная в Иннополисе в России, на которой пишет сборная Израиля. Видимо, со стартом соревнования на двух площадках возникла какая-то рассинхронизация.
00:18: По состоянию на текущий момент таблица результатов, а также условия задач пока недоступны. Я сейчас выясню, можно ли уже рассказывать о задачах, и попробую пересказать их своими словами.
Всем привет!
С вами на связи из солнечного Тегерана, принимающего 29 международную олимпиаду школьников по программированию, мы с Михаилом Endagorion Тихомировым.
Примерно через четыре часа начнётся первый тур главного школьного события года, на котором Российскую Федерацию представляют четверо классных ребят, представленных на фотографии ниже.
Герои нашего сегодняшнего повествования слева направо по фотографии:
Владимир voidmax Романов, Денис Denisson Шпаковский, Александра demon1999 Дроздова и Егор Egor.Lifar Лифарь.
Стоит отметить, что это чуть одна из самых молодых сборных в истории российских команд: на четверых ребята закончили всего 37 классов школы!
В рамках этого поста мы с Михаилом будем вести трансляцию, в которой попробуем комментировать происходящее на туре, следить за успехи наших ребят и их коллег из других сборных, а также всё то, что покажется нам интересным. Приглашаем всех болеть за участников и делиться мыслями о происходящем на туре в рамках этого поста.
PS Также поделюсь для всех ссылкой на телеграм-канал, в котором мы выкладываем разные фоточки с мероприятий вне туров.
Некоторые полезные ссылки (список будет пополняться):
