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

Автор Aksenov239, 12 лет назад, По-английски

Hello!

Tomorrow (the 3rd of November) will held the Nothern Subregion Quarterfinal 2012 in the Northeastern European Region.

I think, it will be very interesting to watch the "battle" between teams, because in our quarterfinal participate 3 persons from the top10 in Codeforces rating. And jury made all to make this quaterfinal very interesting and unpredictable.

Also, don't forget, that you can participate in Yandex.Contest.

  • Проголосовать: нравится
  • +34
  • Проголосовать: не нравится

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

Who are participants from CF top10? Dmitry Egorov, yeputons and ... ?

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

Also two world champions!

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

    Really?But students who had participated in two ACM-ICPC world finals aren't eligible to participate again.(as far as I know)So a student who won two world champions can't take part.

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

Зеркало будет?

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

The problem statements will be only in russian language?

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

Delay for the second time :(

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

Кто-то знает, где можно будет смотреть борд онсайта?

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

Это не команду SPb SU 3 Taken случаем дисквалифицировали?

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

    Это провал года.

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

    А о чём речь можно узнать? Что за дисквалификация?

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

      Судя по твиттеру парни заныкали на машине вовремя пробного тура суффиксное дерево. Хотя между турами админы чистят рабочие машины видимо чтобы никакого prewritten code

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

        Получается, дисквал они получили за то, что админы недобросовестно выполнили свою работу?
        Хочу больше подробностей об этом инциденте. Напишите кто-нибудь, кто в курсе.

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

          Их подискваили за попытку сохранить код между пробником и основным туром в неположенном месте.

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

            А почему бы просто не запретить писать во все директории, кроме рабочей? Кто может гарантировать, что на своем компьютере на основном туре я не найду заранее подготовленный недоброжелателем файлик с олимпиадным кодом?

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

              Там все чистят. А запретить писать в мои документы не стоит потому что могут начать тупить среды и не только. В общем там какая-то дебильная ситуация получилась. Они вроде даже утверждают что сохранили по ошибке.

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

              с физическим запретом нормально не будет работать ни одна современная IDE со своей любовью писать много всего куда-то в %USERPROFILE%

              поэтому запрет существует лишь в правилах в виде вот такой строчки:

              During the practice session teams may not store any source code anywhere except working directory.

              в случае с обсуждаемой командой запрет был очевидно нарушен записью prewritten code в дебри того самого %USERPROFILE% отдельно от настроек любых IDE, что мало похоже на случайную ошибку.

              ловится ли это автоматически или вручную — вопрос, не имеющий отношения к теме.

              (все написанное есть личное мнение свидетеля этих событий; я не являюсь представителем жюри)

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

                Может быть, стоит давать более содержательные задачи на пробный тур, чтобы участникам некогда было заниматься ерундой?

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

                  Пробный тур для этого и нужен :)

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

                  Ерунда — это когда команды сдают две халявки и уходят с пробного тура. Здесь же вполне целенаправленное нарушение правил.

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

                  Свечку держал?

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

    А какие-нибудь ссылки есть?

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

Как можно было сдать задачу С за 11 минут не используя OEIS (я говорю про трансляцию контеста на Yandex.Contest)?

Судя по фразе отсюда "Правила отдельных раундов совпадают с правилами официальных четвертьфиналов", гуглить ответы нельзя, поскольку на официальных четвертьфиналах это запрещено. Или я не прав?

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

    А где в правилах написано, что нельзя использовать OEIS?

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

      Во-первых, ссылка на правила вот. Во-вторых, на онсайтах интернета просто нет, а приносить с собой всякие материалы и общаться с другими людьми запрещено по тем же правилам:

      Participants may bring and use unannotated natural language dictionaries (except electronic ones), blank sheets of paper and instruments for writing only. Contestants may not bring and use any books (except dictionaries), reference manuals, electronic dictionaries, program listings, any machine-readable information (software or data on any kind of storage), computing devices (handhelds, portable PCs, notebooks, calculators), mobile phones or any other communication devices.
      
      During the round, participants are only allowed to communicate with members of their team, members of the Executive Committee of the Jury and the Technical Committee.
      
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится -13 Проголосовать: не нравится

        Но то, что интернета там нет, не означает, что им запрещено пользоваться, не так ли? :)

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

          Конечно не означает. Правда, запрещено пользоваться computing devices (handhelds, portable PCs, notebooks, calculators), mobile phones or any other communication devices.

          Но, если Вы умеете выходить в интернет без всего этого, то, пожалуйста, пользуйтесь.

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

            Чип в мозг с вайфаем разрешен?

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

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

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

    Разумеется, большинство решений с OK там — константные массивы. А чего ещё ожидать от такой задачи? Если давать на онлайн-контест такой баян, большинство участников не справится с соблазном загуглить это за 15 секунд.

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

      Ну давали-то ее изначально не на онлайн контест. Авторы знали, что у участников не будет инета, так что почему бы не дать? Я когда писал онлайн, специально не копипастил с OEIS, чтобы быть на равне с теми, кто пишет без интернета. Тем более, что контест проводился по правилам онсайта. Видимо, другие участники так не думают.

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

        После 100500 OpenCup'ов, на которых куча команд гуглила задачи, веры в абсолютную честность большинства участников не очень много :) К авторам конечно претензий мало (разве что, эта задача — баян, а нетривиальные баяны сильно хуже тривиальных). Я только хотел сказать, что ничего неожиданного в такой ботве на онлайн-контесте нет.

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

    А в Армении сдают задачу на 1:00. Это при том, что включить компьютер, залогиниться в систему, набрать в блокноте A+B и отослать занимает в лучшем случае 1:20 — 1:30.

    В Узбекистане же это отнимает 1:54, что тоже не похоже на честную игру: задача там все-таки не A+B, и надо было немножко подумать.

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

      Я говорю про конкретную задачу, которая без готовых ответов совсем не очевидная. Это сильно запутывает, когда задачу, которая по сложности в контесте как минимум седьмая (по крайней мере, мне так кажется), сдают на 11 минуте второй по счету. И после этого ты начинаешь над ней думать, а она так просто не решается.

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

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

        Мои примеры вообще доказывают нарушения регламента в официальных контестах и не имеют отношения к задаче C.

        С которой, в общем-то, понятно, кто как ее решал и на какие сайты при этом заходил :) Можно было, например, открыть официальный монитор и убедиться в этом.
        Собственно, мы тоже зашли куда надо под конец контеста; если бы играли на онсайте, реальное наше место — 21-ое с 7 задачами и 964 минутами штрафа.

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

      Да, мы (в Армении) начали 5 минут пораньше, но не думаю, что этот факт каким то образом повлиял на общий монитор.

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

Мне кажется, или действительно результаты команды SPb SU 4 (Egorov, Kunyavskiy, Suvorov) появляются с какой-то задержкой. Задача С сдана на 215мин, а в таблице появилась определенно позже. Только что появилось ?6 по J, хотя контест уж давно кончился. Может они как-то отдельно от других решают?

UPD. Выяснил. У них были какие-то проблемы, им чуток контест продлили.

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

    У нас у компьютера были проблемы с памятью и при попытке скомпилировать решение комп перезагружался. В результате нас пересадили на другое место, компенсировали 15 минут. Отсюда и задержка.

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

Как решать Н ?

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

    Расскажу про самую сложную часть задачи — нахождение пар "специализированных" медсестер, не имеющих возможности одновременно уйти в отпуск.

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

    P.S. Я сегодня на собственной шкуре узнал, что можно выиграть четвертьфинал, и при этом быть ужасно недовольным своим выступлением. G, H, I — те три задачи, которые были нами придуманы, и при этом ни одна из них не была до конца реализована...

    UPD. Кто расскажет, как решается I с питерскими ограничениями?

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

      Я решал так: Вычислим значение формулы для всех 212 наборов значений переменных. Будем делать это обычным рекурсивным разбором выражения, только ответом будет не одно число (0 или 1), а битовая маска из 212 битов (кстати, для маски очень просто делать все логические операции, которые есть в условии (~ x, x&y, x|y, ~ x|y, ~(x^y))).

      Теперь допустим, что наборов значений переменных, где формула принимает истинное значение (cnt), не больше половины. Тогда для каждого такого набора заведём вершину в первом слое и пустим в неё по одному ребру из A, B, ..., L, ставя отрицание там, где соответствующая переменная равна 0. И добавим ещё 11 рёбер из 0-й вершины.

      Теперь в вершину второго слоя пустим cnt рёбер из 0 с отрицанием.

      Для случая cnt > 211 в первый слой ставим вершины, на которых значение формулы — 0. А в вершину второго слоя пускаем рёбра из вершин первого слоя с отрицаниями. И ещё (212 - cnt - 1) ребро из 0.

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

      На contest.yandex.ru такое решение укладывается в 1 секунду на всех тестах.

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

а размораживать когда будут?

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

There's official video translation at http://www.ifmo.ru/online/online.htm

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

Ой. Сейчас прочитал условие L и понял его неправильно (подумал, что количество операций '+' и '-' не превышает 10000). Написал решение за квадрат и оно зашло. Так и предполагалось?

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

    Когда я включил трансляцию под конец разбора, там обсуждали дерамиду.

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

    Нет, предполагалось, что должно заходить что угодно быстрее квадрата, но не квадрат. Я вот почти на 2 часа увяз в дебаге корневой, в результате только при помощи стресса отловил все баги.

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

      n*log(n) с большой константой не входил. Поделили константу на 30 — прошло.

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

        n*log(n) в этой задаче — это около полумиллиона, я честно говоря плохо себе представляю что надо такое написать, чтобы константа была около тысячи. Почти наверняка имела место неверная реализация или неправильно оцененная асимптотика.

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

          У меня тоже tnlog(n) (t — количество типов, 26) не зашло. Я слишком много раз делал операции с декартовым деревом (например, чтобы узнать ответ на запрос, я подразбивал дерево на три, чтобы среднее ровно соответствовало запрашиваемому интервалу).

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

            А разве узнать ответ на запрос можно быстрее, чем разбив его на три? Не подскажете, как?)

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

          у нас тоже не заходило одно декартовое дерево. Правда мы написали свой рандом и мелкие оптимизации... но там при каждом сплите количество вершин могло увеличиться на одну. Но мы в афиге были когда нам это пришлось оптимизить.

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

        Ну стоит уточнить что большая константа это 26, т.е. хранили сумму для каждой буквы. По сути каждый раз делалось 26*log n * примерно 3 операции с Декартовым деревом, но всё равно выходит не так уж и много. А n*log n с одним декартовым деревом и битмасками зашёл за 0.04, так что всё ок.

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

Where can I find the Official Final Standing?

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

В задаче K могут встречаться нулевые площади:(

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

Oh, it was a hard and amazing contest. Congratulations for the winners.

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

Офтоп.
Со snarknews.info:
"**Поздравляем команду MIT Unpredictable (Илья Разенштейн, Рати Гелашвили, Sepideh MahAbadi) с победой в Northeastern North America Regional Contest и выходом в финал ACM ICPC 2013!**".
Меня почему-то улыбнуло...

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

Меня улыбнуло тоже. Присоединяюсь к позлравлениям!

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

Are the top-ers ( Dmitry_Egorov , yeputons , tourist ) on the same team ?

UPD: Now I know why I get downvotes . I didn't take a look at Standings.

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

Как надо было решать G, J и C?

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

    Задача J.
    Мы так делали: заметим (написав перебор за 5 минут), что для n >= 7 решение всегда существует. Для n < 7 считаем перебором, иначе прекалькаем (прямо в исходник) ответы для n = 7, а ответы для n > 7 получаются добавлением в конец перестановки чего-то типа n, n-1, n-2, ... 8.
    Еще надо быть осторожным с тем, что четвертая функция может из-за этого преобразования поменяться, так что надо выбрать правильный ответ для n = 7, который будет прекалькаться в исходник :)

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

Кто-нибудь может сказать тесты для H ? Моя программа получает WA6, но она работает верна на всех моих тестах.

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

Does anyone know if there will be an online version of the coming NEERC regional (not subregional)?

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

    I think no. There was no online version in the past. But they always publish tests and solutions, so it definitely will be uploaded to Codeforces gyms 1-2 days after the contest.