Всем привет, сегодня я хотел бы сделать особый блог, потому что вчера прошëл MRCQ — 1/8 icpc, она же квалификация на 1/4 или, как его официально называют, MRC. Чувства насчëт него у меня смешанные, но это был весьма необычный день, так что хочется поподробнее рассказать, как он у меня прошëл.

Я проснулся в 8 часов от звонка на телефон. Мне не понравилось, что меня разбудили за 30 минут по подъëма, поэтому я его сбросил, посчитав, что звонят скаммеры. Однако оказалось, что это звонил мой тиммейт, чтобы предупредить о том, что в наш вуз организаторы почему-то хотели пускать только до 10, а позже нет (я не знаю почему). Я, увидев это сообщение, мгновенно проснулся, отдëрнул шторы так, что они слетели на пол и быстро побежал собираться. К счастью, выяснилось, что приходить можно было в любой момент до 11, так что беда меня миновала.

По приезде всë проходило весьма спокойно, мы успели запустить все возможные ide, obs studio и т.д. Мы немного поговорили с другими командами, почилили, заслали задачку на тренировочном контесте и начали морально готовиться к самой олимпиаде.

Теперь о самом контесте: мне кажется, что мы выбрали интересную стратегию. Изначально мы хотели распределить A, B, C между собой и начать их решать параллельно, но наш тиммейт предложил другую страту: он решает ABC в соло, пока я и мой второй сокомандник решаем E и D. Я думаю, что такая страта как раз и сумела принести нам низкий штраф. E оказалась сложнее обычного, так что я просидел над ней где-то час, пока моя тима не залила ABCDF. Далее мой первый тиммейт помог мне до конца развить моë решение, предложив определëнную теорию. Далее началось написание самой ешки, которую, к сожалению, впоследствии пришлось немного соптимизировать. После этого она уже зашла. Параллельно, пока этот самый сокомандник писал еë, я решил задачу G — она оказалась на весьма тривиальное дп. Плюсиком у неë была очень маленькая реализация, которую мне удалось написать всего за 10 минут и заслать с первой попытки. Таким образом, на протяжении первой половины контеста мы уверенно держались в топ 50. Далее, трезво оценив наши шансы, мы поняли, что заслать больше 9 задач у нас не выйдет, так что мы решили сконцентрировать все наши силы на H и I. Я взялся за I, а 2 моих тиммейта за H. Результат не заставил себя долго ждать — через час я заслал I. Оставалась только H, и мы все принялись за неë. Моя тима к тому моменту уже придумала неплохое решение с логарифмами и вещ. числами, и мы начали его реализовать. Первая посылка была полна надежд, но еë результат — WA33. Мы отчаялись, посчитав, что точность нам всë заруинила, но... Спойлер: это была не точность — мой друг забыл рассмотреть краевой случай при n = 1,причëм, чтобы задачка зашла нам оставалось заменить всего одну двоечку на единичку. Но мы не растерялись, и за полчаса до конца я придумал совершенно новый подход: считать факториалы по модулю. И начали поспешно его писать. В итоге — мы словили TL l, потом проведя тривиальную оптимизацию — WA28. Это был конец, мы решили только 8 задач. Только придя домой я выяснил: в этом подходе надо было поменять 300001 на 300002, а диапазон прохода — с [r — 5,r + 5] на [r — 10, r + 10]. И оно тоже тогда заходило. Какой из этого можно сделать вывод? Мы во время контеста придумали 2 различных рабочих решения, и ни одно из них не заслали. Так мы могли бы решить 9 задач и сохранить 61 место, войдя в топ 70. А так у нас только 90. Да, мы улучшили результат по сравнению с прошлым годом, но мы ведь могли выступить гораздо лучше. Вот на MRC хочется реально круто выступить, без таких вот просчëтов.