В воскресенье 06.10.2013 в 10:00 MSK будет проходить командная олимпиада для школьников.
Олимпиада будет проходить в базовой и усложненной номинациях.
Длительность в базовой номинации 3 часа, а в усложненной — 5 часов.
Зарегистрироваться можно здесь.
Свою номинацию можно посмотреть здесь.
После окончания предлагаю обсудить задачи здесь.
Good luck and have fun!
P.S. Больше информации здесь.
P.P.S. Соревнование окончено, как решалась F в усложненной номинации?
Проблемы с реакцией на письма на [email protected] больше не будет.
Расскажите, как решались задачи A и B усложненной, пожалуйста.
Берем все позиции '^' и запоминаем, каким числам после них они соответствуют. Довольно понятно, что если существует последовательность сносок, то максимальный индекс в нем не более 1000000 (лучшая оценка это 185186).
*1 Давайте из всех максимальных подпоследовательностей индексов '^', из которых получается последовательность сносок, выберем лексикографически минимальную. Это можно сделать, взяв в качестве первой сноски самую раннюю позицию '^1', потом взяв самую раннюю позицию '^2', но которая позже '^1', потом раннюю '^3', которая позже '^2' и так далее пока есть позиции.
*2 Теперь зная какой максимальный индекс у максимальной последовательности сносок, аналогично идем в обратную сторону и пытаемся найти лексикографически максимальную подпоследовательностей индексов '^', из которых получается последовательность сносок.
Пусть earlyi — это самая ранняя позиция '^i' из всех, который встречались в максимальных последовательностях сносок (этот массив мы предпосчитали *1). А latei — это самая поздняя позиция '^i' из всех, которые встречались в максимальных последовательностях сносок (этот массив мы предпосчитали *2).
Несложно понять, что если позиция '^i' находится на отрезке [ earlyi, latei ] и latei — earlyi > 0, то она может являться и сноской, и степенью, так как если она станет степенью, то на отрезке еще есть другая '^i', чтобы подставить в последовательность сносок вместо нее. Если позиция '^i' находится на отрезке [ earlyi, latei ], но earlyi = latei, то она может быть только сноской. Если позиция '^i' не находится на отрезке [ earlyi, latei ], то позиция может быть только степенью.
Код
Не утверждаю, что это самое простое решение, просто, что влезло в голову, то и написал.
Насчет F, мне интересно, есть ли нормальный способ найти модуль хэша?
Очевидно, что база ищется легко и быстро (запросы 'ab' и 'aa'), а вот с модулем, чтобы сдать задачу пришлось повозиться: получилось несложное решение, но на нем не работали случаи, когда база была из множеств {36, 37} и {73, ..., 93}, поэтому пришлось обрабатывать их отдельно.
В общем, какая-то лажа и глобальный пропих, соответственно интересно, как делать это по-нормальному?
Это насчет F.
А вообще, конечно, по некоторым задачам (С, G и I) были такие ограничения, которые несколько ставили под сомнение тот факт, что правильное решение пройдет по TL.
Я базу искал запросом 'aa', Потом генерил такую строку s = 'aaa...', чтобы хеш в перый раз пришлось взять по модулю. На основе этой информации сгенерил набор модулей, которые подходят s и стал генерить рандомные строки, по ходу считая хеши этих строк по всем модулям: если хеш не подходит под значение сервера, значит плохой модуль, выбрасываем, и так, пока не останется 1 модуль. Этот модуль — ответ.
Код
Да уж, конечно, с базой я переборщил, а в целом, если убрать все извращения из моего кода, то получится примерно такое же решение.
Спасибо.
Чем вас смущает O(N^3) в G?
Да уж, какой-то психологический аспект.
Если смотреть на все это, как на O(N3), то видишь N ≤ 500 и радуешься, а вот если считать именно числа, учитывая что один из множителей не больше 1000 (а не 500), то получается 500 * 500 * 1000 = 2, 5 * 108, что нас чуть-чуть задержало.
Добавьте, пожалуйста, в тренировки.
Ждем, пока появится архив тренировки на сайте. Как только, так сразу. Надеюсь, в этот раз обойдется задержки.
Добрый вечер.
Архивы на сайте, небольшая задержка связана с написанием Открытого кубка параллельно с проведением олимпиады.
В тренировках: 2013-2014 Цикл интернет-олимпиад. Вторая командная олимпиада, базовый уровень (6 октября 2013 года), 2013-2014 Цикл интернет-олимпиад. Вторая командная олимпиада, усложненный уровень (6 октября 2013 года).