Внимание, присутствуют спойлеры по задачам!

Не далее как в минувшую субботу в Виннице и Бухаресте прошел полуфинал АСМ в юго-восточном европейском регионе. Этот контест запомнился мне больше всех остальных официальных контестов, и пока впечатления еще свежы, я спешу ими поделиться.

Надо сказать, что мы заранее боялись этого контеста — вспомнить только, что творилось в прошлом году. И если в прошлый раз организаторы откатились до более старой и непроверенной версии тестирующей системы в ночь перед контестом, то в этом году подготовка была явно лучше — за неделю до контеста пришло письмо, что теперь проверяющей системой будет e-judge, и что писать можно будет только из-под Ubuntu. Если первая новость была действительно радостной, то вторая означала отсутствие студии. Можно долго вести холивары на тему того, нужен ли дебаггер, но мы всегда использовали его, если была возможность (а на тренировках она была), и его отсутствие напрягало. Еще одним неприятным сюрпризом стало то, что у Shtrix в ночь перед отьездом поднялась высокая температура, и нам всем пришлось добираться в Винницу в разное время тремя разными поездами.

Пробный тур порадовал сразу несколькими вещами. Во-первых, сервер оказался в Виннице, что породило волну шуток в духе "А давайте 17 раз случайно споткнемся о провод? Да-да, тот, который ведет в Румынию" и "Ну что, на этот раз в Бухаресте пишут до 4:30?" и породила некоторую уверенность, что система все-таки не упадет. Скажу заранее, она таки не упала, и вообще на нее не было никаких нареканий.

Казалось бы, ну какие проблемы могут быть с задачами пробного тура, они уже несколько лет одни и те же.. Не тут то было. На 45ой минуте пришел клар — "Мы ошиблись. В этой задаче нужно посчитать не количество непустых строк, а количество пустых строк". И все-таки нашлись уникумы, сдавшие эту задачу с плюса, тем самым подтвердив гипотезу про четное число ошибок.

После одной из посылок, получившей СЕ на сервере и нормально компилировавшейся локально, мы вежливо поинтересовались, будет ли возможность посмотреть отчеты об ошибках компиляции, и правда ли, что локальная и серверная версии g++ совпадают. Нам ответили, что возможности не будет, а версии совпадает. Когда мы показали, что это не так, пришел совершенно гениальнейший ответ — в духе, "Да, вы правы, они различны. Но между ними нету никакой разницы.". Впрочем, на контесте было еще чудесатее:) А о таких мелочах, как запрет прикасаться к мышкам до начала контеста, я вообще умолчу.

Итак, контест начался. Начался с информации, что задачу А пока не стоит трогать. Проглядев ее и увидев 100 мегабайт аутпута, мы ее отложили. Быстро раздеребанив условия и вычленив С, в которой всего-то надо было запустить решето Эратосфена до 10М, мы быстренько подсунули ее KADR , который и сдал ее на 9ой минуте. Это была первая удачная сдача в контесте, что немного повысило нашу уверенность в себе. Пока он набирал, я нашел задачу I, в которой тоже было что-то несложное — для каждой вершины дерева найти максимально удаленную. Хотя у меня и были сомнения, что это вторая по сложности задача в контесте, ничего другого пока не было и ее тоже подсунули KADR. В то время, пока он читал свой не заработавший с первого раза код на бумажке, я набирал G, в которой оказалась простая симуляция с сэтом. После удачной сдачи I и неудачной G KADR пытался придумать уже кем-то сданную в то время B, а мы со Shtrix курили распечатку и условие G в попытке разобраться, что же не так. Наконец, в условии была обнаружена двузначность — фраза "энзим можно использовать в течении часа" могла означать как "купив энзим его надо использовать на протяжении близжайшего часа" так и "можно ждать целый час и использовать его в начале следующего". И на тестах из условия оба понимания дают одинаковые ответы, естественно. Отправив клар и получив ответ, мы сдали и эту задачу. В ответ на наши возражения что условие двузначно и просьбу снять попытку нам сказали, что оно однозначно, а когда мы привели пример, нам ответили замечательнейшей фразой "No comments". Решив, что спорить с жюри сейчас не время, мы забили. В этот момент мы уже шли на втором месте, отставая от Unicon где-то на 5 штрафных минут.

Где-то в этот же момент раздалось восклицание KADR что "да тут же просто фенвик и все" и я уступил ему место у компа, а сам сел более аккуратно выводить формулы для Е — простая симуляция, но надо разобрать 8 случаев. К 80 минуте обе эти задачи мы сдали, однако отставание от Unicon становилось все больше, заставляя нервничать.

Если задача G с ее неоднозначностями была еще так себе, то задача D оказалась уже классической румынской задачей SEERC, одних ограничений нету, другие — в формулировке "few millions", чтобы разобраться, понадобилось несколько кларов. Наконец, к 2 часам и она была сдана, однако отставание от Unicon уже было таково, что чтобы их обогнать, нам нужно было сдать на одну задачу больше. В голову нет-нет да и закрадывалась мысль "ну где же эта задача, на которой мы сможем оторваться, у нас все таки опыта побольше?". А задачи не было.

Быстро написав А, я получив WA1. Так как в коде было достаточно много индексов, мы в течении более чем получаса и еще одной штрафной "авось" попытки пытались ее сдать, безуспешно. Наконец, предположив, что тесты не соответствуют формату, в котором "после последней строки сразу идет конец файла", мы переделали ввод, чтобы он не был так зависим от пробела в конце, и получили АС. Порядком разозленные, мы написали в ультимативной форме клар, в котором говорилось о кривых авторах^W тестах и требовании снять штрафные попытки. Нам пообещали перетестировать, и мы чуть-чуть успокоились.

Увидев, что задача H была сдана sdya и Seyaua в начале 3его часа, мы решили, что она простая, и надо обязательно решать еще как минимум две. Задача F с ограничениями 42⁴² отпадала, так что пока я вбивал наивное решение на H, тиммейты думали над J. H в нашем решении свелась к нахождению общего члена арифметических прогрессий, вот только начальные элементы и разности там были до 2⁶³ - 1. Оказалось, что мы не так-то хорошо умеем находить эти общие члены — сначала неработающий кусок кода вписал KADR затем неработающую формулу написал я, но в конце концов мы все-таки написали решение, совпадавшее с наивным на маленьких тестах. К этому времени сначала sdya и Seyaua сдали 8 задач, со штрафом в 1006, затем румынская команда со штрафом в 1079, а затем и третья команда из нашего вуза, Reckless, со штрафом в 1005. Наше решение на с++ упорно давало ВА 1 и было принято решение перекодить его на яве. После перекоживания мы прикинули, сколько штрафных попыток мы можем сделать,чтобы после сдачи выйти на первое место, вышло около 5. До конца контеста оставалось пол часа, ситуация нервнее некуда, сдача на яве дает ту же ВА 1. Вылавливаем мелкий баг, и получаем ТЛ 3. 1000 запусков расширенного Евклида для BigInteger — и ТЛ 3. Ругаемся, переписываем Евклида на лонги, посылаем опять — и опять ТЛ 3. Это уже какая-то ересь.. До конца контеста 15 минут, и тут нам в голову приходят две полубезумные идеи. KADR предлагает пока числа маленькие, написать такое же решение и запускать его в лонгах, а я говорю, что еще стоит отсортировать инпут, чтобы члены прогрессий дольше оставались маленькими. Посылаем — ВА 9. Наконец, за 4 минуты до конца, уже не веря, что этот бред может работать, меняем константу того, когда работает решение в лонгах с 2млрд на 2млн, посылаем и получаем АС. Ощущения в этот момент передать сложно.. Быстро подсчитываю на бумажке наш штраф. До того 564, сдача почти в 300 минут, 7 штрафных =... 1004. Еще раз смотрим на монитор, где у Reckless 1005 и нашу команду дружно распирает истерический смех. Из-за кулис выходит Milanin смотрит на нас и стучит кулаком по голове:) Последние 4 минуты на последних нервах смотрим, не радуюется ли кто-то еще. Вроде нет, но мы все равно почти трясемся. Сразу после контеста узнаем, что все ОК, мы таки первые, но радоваться сил уже почти нет:) Думаем только, что свой запас везения мы исчерпали на много месяцев вперед.

Уже вечером после аппеляции нам и румынской команде сняли некоторые штрафные попытки, так что наш штраф стал равен 910, но это уже было не важно. Важно, что Kyiv NU BZFlags едут на финал. Увидимся:)

Итак, совсем недавно завершился первый раунд Snark News Summer Series. Предлагаю тут его обсуждать, а также напишу небольшой разбор.

Вероятно, самая простая задача раунда, с которой и начали большинство участников. Для ее решения следовало заметить, что существует ровно свободных бит в палиндромах с длиной битовой записи Х - биты, начиная с второго по сташинству, до середины строки. То есть палиндромов с длиной битовой записи Х всего . Таким образом можно узнать длину битовой записи палиндрома, который нам нужен, и номер нашего палиндрома среди всех палиндромов такой длины. Ну а само число тогда получить уже очень просто:

A

Итак, в этой задаче можно было просто выполнить то, что было написано в условии – перебрать все числа от A до B, для каждого из них перебрать все перестановки модулей и проверить, что не менее чем для 7 перестановок f(x)=x.

А еще можно было заметить следующее. Пусть p=min(p1,p2,p3,p4). Тогда если x<p, то, очевидно, при взятии любого модуля x не изменится, ведь он меньше любого модуля. Очевидно также, что в противному случае он изменится, потому что будет взят по определенному модулю, меньше или равному х. Таким образом, вне зависимости от перестановки модулей, для числа либо выполняется равенство f(x)=x, либо не выполняется. Некоторые участники просто проверили для определенной перестановки модулей, подходит ли каждое число из промежутка, и вывели количество чисел, для которых равенство выполняется. Однако достаточно было даже просто посчитать количество чисел в пересечении интервалов [0;p-1] и [a;b].