Всем привет!
В эту субботу (26 октября) в НИУ ИТМО пройдет четвертьфинал Северного региона ACM ICPC. Для участия в нем зарегистрировалось более 70 команд. Хотелось бы напомнить участникам, что необходимо удостоверится, что вся ваша команда прошла регистрацию, и каждый участник заполнил раздел "Extra information".
А в воскресенье (27 октября) состоится Двадцать первый командный чемпионат школьников Санкт-Петербурга по программированию, в котором примет участие более 70 команд.
Монитор и расписание четвертьфинала, как обычно, будут доступны здесь. Чемпионата школьников — здесь.
Так же за новостями соревнований теперь можно следить в твиттере.
Хештег четвертьфинала: #NSNEERC2013, чемпионата школьников: #СПбКОШП2013
Свои фотографии с четвертьфинала можно добавить сюда, со школьного чемпионата — сюда.
Желаем всем участникам удачи,
Пресс-служба соревнований.
UPD: Результаты прошедшего четвертьфинала.
Поздравляем команды, прошедшие в полуфинал:
SPb SU 4 (Kunyavskiy, Egorov, Suvorov)
SPb NRU ITMO 1 (Bardashevich, Minaev, Vasilyev)
SPb SU 1 (Pyshkin, Smykalov, Andreev)
SPb SU 2 (Simonov, Gordeev, Sayfutdinov)
SPb SU 6 (Krachun, Kuzmina, Voronetskiy)
SPb NRU ITMO 2 (Komarov, Krotkov, Demianiuk)
SPb NRU ITMO 5 (Peresadin, Belonogov, Voit)
SPb AU 1 (Sluzhaev, Krasko, Savinov)
Petrozavodsk SU 1 (Shapovalov, Filev, Ioffe)
SPb NRU ITMO 4 (Garder, Vedernikov, Kovsharov)
Northern FU 2 (Dodin, Chesnokov, Popovich)
SPb AU 2 (Kolganov, Velikiy, Ivanov)
Pskov SU 1 (Kovalenko, Barsuk, Petrova)
Petrozavodsk SU 4 (Ermishin, Krasnov, Starkov)
Pskov SU 2 (Dmitriev, Shalabod, Shantarin)
SPb SU of Telecom 1 (Yastrebov, Kiselev, Tarasov)
SPb SPU 2 (Egorov, Serov, Kapralov)
SPb SU of Telecom 3 (Orlov, Veselov, Sholokhov)
Напоминаем, что тут появились фотографии.
Ну все, пацаны, расходимся!
Четвертьфинал уже, наверное, прошел, где можно табличку увидеть? На сайте из поста я не нашел.
Плохо искали.
Спасибо.
Результаты и идеи решений некоторых задач можно также найти в твиттере.
Правильно ли я понимаю, что информация в таблице Team Limits для полуфинала (на сайте NEERC) не совсем соответствует реальности?
Если ты об этом, то у СПбГУ и ИТМО обычно дополнительная квота за проведение полуфинала.
Ведь 'Universities can be allowed additional teams for hosting subregional contest, hosting global training camps, etc'.
Ну вот и получается, что та информация не совсем точная. От MГУ отобрались 5 команд (хотя указано что, должно быть 3), от СГУ — 3 (хотя указано, что должно быть 2).
Это круто, что от сильных Вузов проходит больше команд, но то, что эти квоты "плавают" и не совпадают с офф. информацией — как-то странно.
AFAIK, квоты расширяет жюри ЧФ и NEERC уже по итогам олимпиады.
При этом важно, что при появлении "лишних" команд квота всего четвертьфинала так же увеличивается. То есть не может получиться так, что добавление "лишних" команд выкинет последних выходящих.
Добавьте пожалуйста Питерский четвертьфинал в тренировки.
Было бы неплохо, если бы организаторы просто выложили архив. Очень хочется протестировать свое решение на C с питерскими ограничениями.
Кстати, кто знает на нее решение лучше, чем за ? За указанную асимптотику — это перебор всех O(n2) шаблонов для замены, поиск их с помощью Z-функции и СНМ и дальнейшая проверка с помощью Z-функции.
У нас решение было за O(n^2) с хешами. Переберем подстроку из первой строки. Найдем все ее вхождения (непересекающиеся). Одинаковые подстроки будем обрабатывать один раз за O(количество таких подстрок). Для этого каждый раз будем считать хеш строки, которая получится, если заменить все непересекающиеся вхождения этой подстроки. Исходя из длин строк и количества вхождений, можно определить длину строки, на которую необходимо заменять текущую подстроку. Саму строку, на которую будем заменять, тоже можно определить однозначно — это подстрока второй строки, которая начинается с символа, который соответствует первому вхождению подстроки в первую строку.
Я Вашу идею понял. Значит, мы изначально перебираем длину заменяемой подстроки, потом для всех подстрок данной длины запихиваем их хеши и позиции во что-либо вроде map<hash, list> (очевидно, для достижения нужной асимптотики, нам нужно использовать HashMap, unordered_map или свою хеш-таблицу). Далее для каждой группы равных подстрок оставляем только непересекающиеся. Как уже было сказано, то, на что мы выполняем замену, определить очень просто. Мы берем и выполняем эту замену, попутно пересчитывая хэш итоговой строки, после этого сравниваем его с тем, что нам нужно получить.
Большое спасибо за объяснение.
Кстати, теперь я додумался, как оптимизировать до похожей (все-таки чуть худшей — O(n2 * α(n)) ) асимптотики свое решение с Z-функцией — не нужно несколько раз искать вхождения одинаковых подстрок.
У нас решение за честный чистый квадрат без хэшей.
Основные идеи:
А СНМ-то был и не нужен...
Который раз уже я попадаюсь в ловушку и цепляюсь за самые слабые утверждения, дающие приемлемую асимптотику, когда более сильные утверждения дают не только лучшую асимптотику, но и более простой код.
Спасибо за очередной урок.
Все материалы четвертьфинала доступны здесь.
Если бы они были там доступны, я бы это сюда не писал.
Вроде бы же все есть. Рядом с "Standings" есть ссылки на тесты, условие, решения жюри...
Сдуреть... Захожу на страницу — никаких материалов не вижу. Пару раз обновляю — опа, появились. Firefox 24.
В Тренировках: 2013-2014 ACM-ICPC, NEERC, Северный четвертьфинал.
Где можно найти презентацию с разбором задач этого контеста?
Спасибо за напоминание!
http://neerc.ifmo.ru/subregions/northern/north-2013-analysis.pdf
Скоро добавим ссылку со страницы архива.
Можете объяснить задачу Problem D. Dwarf Tower?
Чуть выше появился разбор задач, можете посмотреть.
Спасибо — но разбор короткий :)
Чуть более развёрнуто: