Блог пользователя niyaznigmatul

Автор niyaznigmatul, 9 лет назад, По-русски

Всем привет от пресс-службы NEERC.

text

Мы рады заявить, что новый сезон 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)
  • Проголосовать: нравится
  • +116
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем niyaznigmatul (предыдущая версия, новая версия, сравнить).

»
9 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

А после ЧФ будут выложены посылки всех команд со всех площадок, где завтра он будет проходить?
Было крайне полезно в том году, когда так сделали после полуфинала :)

»
9 лет назад, # |
  Проголосовать: нравится +51 Проголосовать: не нравится

Таким образом, Уральский четвертьфинал в этом году будет проведен на задачах Питерского ЧФ? При этом 1 ноября запланирован GP of Ekaterinburg. Было бы интересно узнать, с чем связано такое решение ;)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +38 Проголосовать: не нравится

    Опенкап как птз — туда можно давать наркоманские контесты)

    А на чф нельзя, не те пройдут, а потом... ну да, результаты неадекватны.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +31 Проголосовать: не нравится

      Опять палиндромы? '(

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Миша не готовит, вроде) Но он вполне мог предложить какую-нибудь задачу)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Ну кстати: чемпионат УрГУ (авторы настояли) готовит команда, которая сама играет четвертьфинал.

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Всем удачи!

Не тупить;)

А болеем за Питер... за ИТМО...

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    За ИТМО надо болеть на финале. До этого момента просто наблюдать. Впрочем, и на финале не надо, надо за СПбГУ)

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

      Наблюдаем за ИТМО и СПбГУ)

      Болеем за происходящее в ИТМО...

      Шестёрка лидеров прекрасна ;)

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +33 Проголосовать: не нравится

      Похоже, надо наблюдать и за АУ)

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

А где можно посмотреть монитор?

»
9 лет назад, # |
  Проголосовать: нравится -57 Проголосовать: не нравится

За три с половиной часа команда Ural FU: Dandelion (Daniliuk, Merkurev, Sivukhin) решила все задачи восточного четвертьфинала, сделав лишь одну неверную отправку в самом начале контеста. Восточный четвертьфинал точно проходит на задачах Северного? Если да, то так себе в этом году обстоят дела с четвертьфиналами...

  • »
    »
    9 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

    Ну вот, проспойлерил тем, кто будет писать его в час :(

    UPD А у тебя инсайд-инфа какая-то что ли? У меня не получилось найти монитор восточного чф.

    UPD Да уж, огромный минус организаторам чф за такую халатность. Остаётся надеяться, что никто этим не воспользовался, и на результаты это не повлияет.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

      Плохо старался. Как, кстати, и организаторы, если они вообще пытались хоть как-то скрыть свой монитор.

      • »
        »
        »
        »
        9 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится -14 Проголосовать: не нравится

        Даже порядок задач не поменяли. Хотя, обычно в Питере буква задачи соответствует первой букве названия. Сдают A, L. Следующая будет E, потом B, H

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится +27 Проголосовать: не нравится

          Господи, убейся.

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Значит, кому-то повезет и тот будет читать и затем решать в правильном порядке, не отвлекаясь на чтение гробов =)

          • »
            »
            »
            »
            »
            »
            9 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится

            Плохо то что об этой утечке части команд могло быть известно ещё до начала контеста, а это ставит команды уже не совсем в равное положение.

            • »
              »
              »
              »
              »
              »
              »
              9 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

              Хехе, там надо всего-то айдишник в URL поперебивать.

              (но это работает, только если априори знаешь, что организаторы не стараются скрыть монитор)

              • »
                »
                »
                »
                »
                »
                »
                »
                9 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Это можно сделать пз банального любопытства. Я кидал этот линк в начале контеста, но попросили убрать.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      http://acm.urfu.ru/qf/2015/timetable.html

      Это линк на расписание. Интересно вот что: 10:30 — 15:30 Основной тур И это по времени Ёбурга. То есть задачи в любом случае стали известны до начала контеста.

      • »
        »
        »
        »
        9 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

        К сожалению, может ли мне кто-нибудь объяснить следующее. Тренера же могут видеть задачи на четвертьфинале, тогда что им мешало сфотографировать на Урале и отправить задачи в СПб до начала тура?

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      [Spoiler]

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +32 Проголосовать: не нравится

    Просто мы сильная команда и у нас удачно пошёл контест. Не было такого варианта?

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится

      Вообще, нет.) Из этого совсем ничего не следует. Например, в прошлом году чемпионы мира закрылись на 277 минуте, а 3 года назад не закрылись вообще. Просто, в этом году мы действительно расхалявили контест.) А зачем его усложнять, если по сути нужно определить кто будет четвёртой командой от сильного университета или второй от какого-то среднего? Это как раз интереснее выяснять на более простых задачах.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +28 Проголосовать: не нравится

        Да, и всё верно сделали.

        Но pkhaustov как-то и не сказал о том, что в нашем же мониторе у второго места 9 задач, а у четвертого (до заморозки) — 8.

        И как-то читается это как "чуваки откуда-то с донного региона каким-то чудом сделали тотал на Питерском ЧФ".

        А задачи нам очень понравились. Думаю, совсем не очевидно было, что кто-нибудь вообще закроется. Контест идейно сложный.

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Ваш монитор просили сюда не спойлерить. Отличные сегодня задачи. В уровень участников как раз. То что тоталы есть, притом до заморозки — так на ЧФ в этом нет ничего плохого.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Такой халявный контест получился, тотал на тотале просто.

»
9 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

В топ-10 паритет между ИТМО и СПбГУ, но дальше у СПбГУ жуткий провал, конечно. Вот сейчас с 11 по 30 места девять команд ИТМО и только одна(!) — СПбГУ =(

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Смотрю вот таблички других регионов, там K очень активно сдают. Там куб заходит?

В прошлом году вроде тоже было такое, что в каких-то регионах сдавали очень сложные задачи.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

    В других регионах обычно дают "облегченные" задачи. Обычно это заключается в том, что некоторые задачи дают с меньшими ограничениями. Задача K была из этого числа.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    У нас в К ограничение было n ≤ 300. А как решать для n ≤ 2000?

»
9 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

how to solve G and I?

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Черт побери! Как решать D?

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится
    1. Раскладываем N на произведение некоторого числа A на максимальную степень тройки.
    2. Теперь нам нужно отнять от A максимальную степень двойки так, чтобы частное вновь стало делиться на 3 (чтобы степень тройки на след. итерации увеличилась).
    3. Добавляем к ответу произведение степени тройки и степени двойки.
    4. N = ( A — степень_двойки ) * степень_тройки. Если N = 0, то выходим, иначе возвращаемся на шаг 1.
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      Можно ещё проще. Если n нечётное — вычитаем максимальную степень 3. Если чётное, делим на 2 и добавляем множитель 2 ко всем числам. Так продолжаем пока n>0.

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

За минуту до конца заслал G, но упала потому что в трёх местах потерял минус (где добавляем элемент в очередь с приоритетами).

P.S. Почему эта задача очень похожа на задачу K с Московского ЧФ... Особенно она похожа тем, что для меня (а может и не только для меня) эта задача очень простая на 40 минут, но при этом её решило мало команд (по крайней мере до заморозки).

»
9 лет назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

Регион все-таки Казахстанский а не Казахский (такое же отличие как и между русским и Российским).

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

А также в субботу на тех же задачах, что и в Санкт-Петербурге, пройдут четвертьфиналы в Азербайджанском, Армянском, Восточном, Казахском, Таврическом и Узбекском подрегионах.

Только чур не подсказывать =)

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    Да, точно, 8 ноября же воскресенье, а не суббота. Непорядок.

»
9 лет назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

А когда появится разморозка?

»
9 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

У кого-то зашёл питон в F? На codeforces макстест за 500мс, TL 8 на yandex.contest. Кто виноват, я или яндекс.контест? :)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Див1-задачи были только в Northern Subregional ?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Как решить В,С?

  • »
    »
    9 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    "B" Как вариант закрасить какое-нибудь большое поле (например 5 x 5000) наполовину белым цветом наполовину чёрным итого получится по одной чёрной и белой компоненте. А потом просто (можно например через один столбец в какой-то строке) в белой компоненте ставить чёрные точки, а в чёрной — белые, тем самым увеличивая до нужного количества число чёрных и белых компонент. ограничения позволяют без труда это сделать. "C" самому интересно узнать :)

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      5*50000 нельзя ввиду "There should be no more than 100 000 tiles in the panel." Но достаточно поля и 3*30000. В одной половине полосы, в другой — одна компонента 3*х с дырками 1*1 другого цвета (которого больше компонент надо).

      Объяснять как решается С дольше чем глянуть код, там буквально 10 строк и всё понятно.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Вот моё решение B ссылка . У меня ответ будет в массиве 2х(M+N). А решение С здесь. Время работы решение O(a.Length + b.Length + 26).

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Возник такой вопрос, если взять например 2 слова: abс и bcd, то программа выдаёт 7 различных слов, хотя по факту abcd можно получить 3мя разными способами...

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        Ну так 3мя и можно. Один "посчитаем", два других вычтем. Всё правильно.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Решение по G:

Две очереди с приоритетами: возрастающая и убывающая. С помощью первой очереди мы будем строить лексикографически минимальную топологическую сортировку. Во второй очереди будем хранить те вершины, которые мы отложили на "потом". Допустим, в первой очереди у нас есть несколько вершин. Чтобы добиться максимального ответа нам стоит вывести наибольшую из них. Для этого необходимо отложить на потом все остальные вершины, уменьшая при этом k на единицу для каждой вершины (в текущий момент мы не знаем какое ребро будем добавлять, но точно знаем что добавим его). Так же, возможен случай, когда в первой очереди осталась одна вершина, но она меньше, чем самая большая вершина во второй очереди. Тогда нам следует отложить вершину из первой очереди на потом (уменьшив k) и добавить к ответу вершину из второй очереди. При добавлении к ответу любой вершины из второй очереди нужно так же добавлять ребро между последней вершиной в ответе и добавляемой вершиной.

Решение за O( ( n + m ) log( n ) + k log( k ) ).

Код

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +29 Проголосовать: не нравится

Дедушка Мороз! Разморозь, плиз, Kazakhstan Subregional Contest Standings

»
9 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Как решать F и I?

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Когда будет доступен разбор задач и другие материалы?

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Где можно посмотреть всех участников полуфинала? И сколько команд проходит в финал?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Рано говорить о полуфинале, потому что не все четвертьфиналы еще состоялись.

    А число -- сколько команд проходят в финал, может легко измениться даже после полуфинала, точного значения никто не знает.