Всем привет от пресс-службы NEERC.
Мы рады заявить, что новый сезон ACM ICPC уже наступил и некоторые подрегионы провели свои четвертьфинальные соревнования. А в восточном подрегионе даже потребовалась квалификация на четвертьфинал, на которую зарегистрировалось 396 команд, а послали хотя бы одно решение во время соревнования 379 команд. Квалификация проводилась на четырнадцати площадках, и на четвертьфинал отобрались 97 команд. Восточный четвертьфинал пройдет 24 октября на задачах Северного четвертьфинала.
Результаты прошедших соревнований:
- Квалификация восточного четвертьфинала
- Центральный четвертьфинал
- Московский четвертьфинал
- Южный четвертьфинал
Четвертьфинал Северного подрегиона состоится в субботу, 24 октября, в Санкт-Петербурге в главном здании Университета ИТМО. Сегодня прошел инструктаж волонтеров, и ведется работа по переоборудованию аудиторий в холлы для соревнований и на кафедру компьютерных технологий уже запрещено заходить участникам завтрашнего четвертьфинала. За выход на юбилейный двадцатый полуфинал Северо-восточного европейского региона (NEERC) посоревнуются 96 команд из 23 университетов. Четыре последних года команда, побеждавшая на этом четвертьфинале, становилась абсолютным чемпионом ACM ICPC World Finals, поэтому соревнование будет интересным. Мне кажется, что главными фаворитами являются команды:
- Университет ИТМО 2 (Иван Belonogov Белоногов, Илья izban Збань, Владислав vlad107 Подтелкин)
- Университет ИТМО 1 (Адам subscriber Бардашевич, Владимир enot110 Смыкалов, Антон antonkov Ковшаров)
- СПбГУ 1 (Игорь -XraY- Пышкин, Алексей Copymaster Гордеев, Станислав ershov.stanislav Ершов)
А каковы ваши ставки? :)
В этом году также проводится ставший уже традиционным Кубок трех четвертьфиналов. Северный четвертьфинал, наряду с Московским и Западным, является этапом этого кубка. Начало тура 24 октября в 13:00 по московскому времени.
А также в субботу на тех же задачах, что и в Санкт-Петербурге, пройдут четвертьфиналы в Азербайджанском, Армянском, Восточном, Казахстанском, Таврическом и Узбекистанском подрегионах.
Я, Борис Минаев (qwerty787788), Геннадий Короткевич (tourist) и Павел Кунявский (PavelKunyavskiy) проведем текстовую трансляцию в твиттере. Следите и пишите по хештегу #NSNEERC.
Подписывайтесь на страницу VK и аккаунт в Instagram. Там можно будет найти фотографии и интересную информацию.
Всем хороших выходных,
Нияз Нигматуллин,
Представитель пресс-службы соревнований
UPD: Текущие результаты
UPD2: Список команд, вышедших в полуфинал:
- SPb ITMO University 1 (Kovsharov, Bardashevich, Smykalov)
- SPb State University 1 (Ershov, Pyshkin, Gordeev)
- SPb State University 3 (Simonov, Logunov, Ryazanov)
- SPb ITMO University 3 (Budin, Latyshev, Yakutov)
- SPb ITMO University 2 (Belonogov, Podtelkin, Zban)
- SPb Academic University 1 (Bogomolov, Podguzov, Smirnov)
- SPb State University 2 (Savchenkov, Makarov, Sayranov)
- SPb ITMO University 4 (Kisialiou, Berinchik, Korchagin)
- SPb State University 4 (Gulikov, Malinovskii, Kulikov)
- SPb Academic University 7 (Moskvitin, Smirnov, Plyushchenko)
- Northern (Arctic) Federal University 1 (Popovich, Chesnokov, Dodin)
- Petrozavodsk State University 1 (Ermishin, Starkov, Pyatin)
- Petrozavodsk State University 2 (Ermolin, Titov, Alkin)
- SPb State Polytechnic University 1 (Svitkin, Vinokhodov, Tretiakov)
- Pskov State University 1 (Shalabod, Shantarin, Dmitriev)
- Northern (Arctic) Federal University 2 (Guriev, Urusovskiy, Rudniy)
Автокомментарий: текст был обновлен пользователем niyaznigmatul (предыдущая версия, новая версия, сравнить).
А после ЧФ будут выложены посылки всех команд со всех площадок, где завтра он будет проходить?
Было крайне полезно в том году, когда так сделали после полуфинала :)
Жалко, что не со всех площадок выложили посылки (
Таким образом, Уральский четвертьфинал в этом году будет проведен на задачах Питерского ЧФ? При этом 1 ноября запланирован GP of Ekaterinburg. Было бы интересно узнать, с чем связано такое решение ;)
Опенкап как птз — туда можно давать наркоманские контесты)
А на чф нельзя, не те пройдут, а потом... ну да, результаты неадекватны.
Опять палиндромы? '(
Миша не готовит, вроде) Но он вполне мог предложить какую-нибудь задачу)
Ну кстати: чемпионат УрГУ (авторы настояли) готовит команда, которая сама играет четвертьфинал.
Всем удачи!
Не тупить;)
А болеем за Питер... за ИТМО...
За ИТМО надо болеть на финале. До этого момента просто наблюдать. Впрочем, и на финале не надо, надо за СПбГУ)
Наблюдаем за ИТМО и СПбГУ)
Болеем за происходящее в ИТМО...
Шестёрка лидеров прекрасна ;)
Похоже, надо наблюдать и за АУ)
А где можно посмотреть монитор?
тут
А Kazakhstan Subregion?
Узбекистан?
http://neerc.ifmo.ru/information/index.html
За три с половиной часа команда Ural FU: Dandelion (Daniliuk, Merkurev, Sivukhin) решила все задачи восточного четвертьфинала, сделав лишь одну неверную отправку в самом начале контеста. Восточный четвертьфинал точно проходит на задачах Северного? Если да, то так себе в этом году обстоят дела с четвертьфиналами...
Ну вот, проспойлерил тем, кто будет писать его в час :(
UPD А у тебя инсайд-инфа какая-то что ли? У меня не получилось найти монитор восточного чф.
UPD Да уж, огромный минус организаторам чф за такую халатность. Остаётся надеяться, что никто этим не воспользовался, и на результаты это не повлияет.
Плохо старался. Как, кстати, и организаторы, если они вообще пытались хоть как-то скрыть свой монитор.
Даже порядок задач не поменяли. Хотя, обычно в Питере буква задачи соответствует первой букве названия. Сдают A, L. Следующая будет E, потом B, H
Господи, убейся.
Капустов, перестань
Значит, кому-то повезет и тот будет читать и затем решать в правильном порядке, не отвлекаясь на чтение гробов =)
Плохо то что об этой утечке части команд могло быть известно ещё до начала контеста, а это ставит команды уже не совсем в равное положение.
Хехе, там надо всего-то айдишник в URL поперебивать.
(но это работает, только если априори знаешь, что организаторы не стараются скрыть монитор)
Это можно сделать пз банального любопытства. Я кидал этот линк в начале контеста, но попросили убрать.
http://acm.urfu.ru/qf/2015/timetable.html
Это линк на расписание. Интересно вот что: 10:30 — 15:30 Основной тур И это по времени Ёбурга. То есть задачи в любом случае стали известны до начала контеста.
К сожалению, может ли мне кто-нибудь объяснить следующее. Тренера же могут видеть задачи на четвертьфинале, тогда что им мешало сфотографировать на Урале и отправить задачи в СПб до начала тура?
[Spoiler]
Просто мы сильная команда и у нас удачно пошёл контест. Не было такого варианта?
Вообще, нет.) Из этого совсем ничего не следует. Например, в прошлом году чемпионы мира закрылись на 277 минуте, а 3 года назад не закрылись вообще. Просто, в этом году мы действительно расхалявили контест.) А зачем его усложнять, если по сути нужно определить кто будет четвёртой командой от сильного университета или второй от какого-то среднего? Это как раз интереснее выяснять на более простых задачах.
Да, и всё верно сделали.
Но pkhaustov как-то и не сказал о том, что в нашем же мониторе у второго места 9 задач, а у четвертого (до заморозки) — 8.
И как-то читается это как "чуваки откуда-то с донного региона каким-то чудом сделали тотал на Питерском ЧФ".
А задачи нам очень понравились. Думаю, совсем не очевидно было, что кто-нибудь вообще закроется. Контест идейно сложный.
Ваш монитор просили сюда не спойлерить. Отличные сегодня задачи. В уровень участников как раз. То что тоталы есть, притом до заморозки — так на ЧФ в этом нет ничего плохого.
Такой халявный контест получился, тотал на тотале просто.
В топ-10 паритет между ИТМО и СПбГУ, но дальше у СПбГУ жуткий провал, конечно. Вот сейчас с 11 по 30 места девять команд ИТМО и только одна(!) — СПбГУ =(
Наблюдаем) Какой (вот сейчас) топ-8 и топ-12!
Смотрю вот таблички других регионов, там K очень активно сдают. Там куб заходит?
В прошлом году вроде тоже было такое, что в каких-то регионах сдавали очень сложные задачи.
В других регионах обычно дают "облегченные" задачи. Обычно это заключается в том, что некоторые задачи дают с меньшими ограничениями. Задача K была из этого числа.
У нас в К ограничение было n ≤ 300. А как решать для n ≤ 2000?
how to solve G and I?
Черт побери! Как решать D?
Можно ещё проще. Если n нечётное — вычитаем максимальную степень 3. Если чётное, делим на 2 и добавляем множитель 2 ко всем числам. Так продолжаем пока n>0.
За минуту до конца заслал G, но упала потому что в трёх местах потерял минус (где добавляем элемент в очередь с приоритетами).
P.S. Почему эта задача очень похожа на задачу K с Московского ЧФ... Особенно она похожа тем, что для меня (а может и не только для меня) эта задача очень простая на 40 минут, но при этом её решило мало команд (по крайней мере до заморозки).
Регион все-таки Казахстанский а не Казахский (такое же отличие как и между русским и Российским).
Аналогично — Узбекистанский.
Только чур не подсказывать =)
Да, точно, 8 ноября же воскресенье, а не суббота. Непорядок.
А когда появится разморозка?
У кого-то зашёл питон в F? На codeforces макстест за 500мс, TL 8 на yandex.contest. Кто виноват, я или яндекс.контест? :)
Зашёл. После шаманства со степенью полинома
Див1-задачи были только в Northern Subregional ?
В Армении в К ограничение было n ≤ 2000.
.
У нас в Узбекистане были n ≤ 300.
Ещё в Eastern Subregional. Кстати, там команда Уральского (победившая) имеет время даже несколько лучше чем ИТМО-1.
.
Как решить В,С?
"B" Как вариант закрасить какое-нибудь большое поле (например 5 x 5000) наполовину белым цветом наполовину чёрным итого получится по одной чёрной и белой компоненте. А потом просто (можно например через один столбец в какой-то строке) в белой компоненте ставить чёрные точки, а в чёрной — белые, тем самым увеличивая до нужного количества число чёрных и белых компонент. ограничения позволяют без труда это сделать. "C" самому интересно узнать :)
5*50000 нельзя ввиду "There should be no more than 100 000 tiles in the panel." Но достаточно поля и 3*30000. В одной половине полосы, в другой — одна компонента 3*х с дырками 1*1 другого цвета (которого больше компонент надо).
Объяснять как решается С дольше чем глянуть код, там буквально 10 строк и всё понятно.
Вот моё решение B ссылка . У меня ответ будет в массиве 2х(M+N). А решение С здесь. Время работы решение O(a.Length + b.Length + 26).
Возник такой вопрос, если взять например 2 слова: abс и bcd, то программа выдаёт 7 различных слов, хотя по факту abcd можно получить 3мя разными способами...
Ну так 3мя и можно. Один "посчитаем", два других вычтем. Всё правильно.
Решение по G:
Две очереди с приоритетами: возрастающая и убывающая. С помощью первой очереди мы будем строить лексикографически минимальную топологическую сортировку. Во второй очереди будем хранить те вершины, которые мы отложили на "потом". Допустим, в первой очереди у нас есть несколько вершин. Чтобы добиться максимального ответа нам стоит вывести наибольшую из них. Для этого необходимо отложить на потом все остальные вершины, уменьшая при этом k на единицу для каждой вершины (в текущий момент мы не знаем какое ребро будем добавлять, но точно знаем что добавим его). Так же, возможен случай, когда в первой очереди осталась одна вершина, но она меньше, чем самая большая вершина во второй очереди. Тогда нам следует отложить вершину из первой очереди на потом (уменьшив k) и добавить к ответу вершину из второй очереди. При добавлении к ответу любой вершины из второй очереди нужно так же добавлять ребро между последней вершиной в ответе и добавляемой вершиной.
Решение за
O( ( n + m ) log( n ) + k log( k ) ).Код
Дедушка Мороз! Разморозь, плиз, Kazakhstan Subregional Contest Standings
Как решать F и I?
Когда будет доступен разбор задач и другие материалы?
Уже выложили тут http://neerc.ifmo.ru/subregions/northern.html
Теперь в Тренировках: 2015-2016 ACM-ICPC, NEERC, Северный четвертьфинал.
Где можно посмотреть всех участников полуфинала? И сколько команд проходит в финал?
Рано говорить о полуфинале, потому что не все четвертьфиналы еще состоялись.
А число -- сколько команд проходят в финал, может легко измениться даже после полуфинала, точного значения никто не знает.