elizarov


Блог Романа Елизарова


Previous Entry Share Next Entry
Результаты NEERC и разбор задач
elizarov

Закончился 17-ый ежегодный Полуфинал Чемпионата Мира по Программированию и проходящий в его рамках Чемпионат России. Победителем и Чемпионом России стала команда моего родного Санкт-Петербургского Университета Информационных Технологий, Механики и Оптики, решившая 11 из 12 задач за 5 часов соревнования. На втором месте команда Московского Государственного Университета, на третьем команда Белорусского Государственного Университета, на четвертом команда Санкт-Петербургского Государственного Университета, которые решили по 10 из 12 задач. Вся таблица результатов доступа на сайте соревнования.

Условия задач выложены на сайте соревнования здесь. Краткий разбор задач я выложил здесь. Если в разборе что-то не понятно, то первым делом я рекомендую почитать мои решения из архива выложенного здесь. Можете задавать вопросы в комментариях к этой записи.

Задача H "Hyperdrome" в этом году явилась неожиданно удачной иллюстраций к некоторым моментам, которые я освещаю в своей серии записей про производительность. Дело в том, что её асимптотически-эффективное решение n раз обновляет счетчики битовых шаблонов четности-нечетности различных суффиксов исходной строки в хеш-таблице, и n*(k+1) раз ищет элементы в этой хеш-таблице, где k это количество букв в алфавите, которое в данной задаче фиксировано и равно 52. Таким образом, решение работает за время порядка O(n*k). Однако, из-за того что n достаточно велико (до 3*105), хеш-таблица получается большой и доступ к её произвольным элементам становится узким местом из-за ограничений подсистемы доступа к памяти. Если же предварительно отсортировать массив со всеми возможными битовыми масками за O(n*log n), сделать проход для подсчёта количества разных масок, а потом k раз пройтись по результирующему отсортированному массиву используя алгоритм слияния с двумя указателями для выявления элементов отличающихся на один бит, то результирующий алгоритм будет иметь сложность O(n*k + n*log n), то есть будет асимптотически более медленным, но, по факту, например на моем компьютере, работает почти в 3 раза быстрей, из-за того что осуществляет только последовательный доступ к памяти. Эффективный алгоритм можно оптимизировать, сократив в два раза количество проверок в хеш-таблице, но он все равно отстает по времени от алгоритма слиянием, который последовательно проходит по памяти.

Для тех, кто писал решение задачи Н на C++, было два любопытных способа совершить ошибку. Один заключается в использовании std::map, который реализует сбалансированное дерево и выполняет свои операции за O(log n), что увеличивает асимптотическую сложность решения до O(n*k*log n), но, правда, все равно проходит из-за исключительного гуманизма жюри. Другая же ошибка, которую допустили некоторые команды, заключалась в использовании оператора [] для поиска элементов. Этот оператор создает элемент, если тот не существует, приводя к тому, что их количество возрастает до O(n*k) вместо O(n) и такое решение уже никак не укладывается в ограничения по времени.


  • 1

Сложность алгоритма

Роман, указаные вами грабли про std::map и оператор [] должны быть видны, мне кажется, в современном IDE до компиляции (так сказать, препрофайлинг, хотя бы в справочном подсчёте), поскольку "нужно контролировать каждый занятый байт памяти и каждую выполняемую инструкцию".
Тогда бы никто на них и не встал.

Re: Сложность алгоритма

Хорошо бы, но таких "современных IDE" для языка C++ просто не существует.

  • 1
?

Log in

No account? Create an account