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

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

Вас приветствует пресс-служба NEERC.

Мы будем держать вас в курсе всех интересных событий, происходящих на всех соревнованиях Северо-восточного европейского региона. Более подробно мы расскажем о соревнованиях, которые пройдут в Санкт-Петербурге: Северном четвертьфинале, полуфинале NEERC, Командном чемпионате школьников Санкт-Петербурга и Всероссийской командной олимпиаде школьников по программированию.

Всю интересную информацию можно будет найти на: официальном канале в twitter, в группе ВК, на официальных сайтах соревнований NEERC и ВКОШП.

text

Новый сезон ACM ICPC начинается и в Санкт-Петербурге. Некоторые четвертьфинальные соревнования уже прошли, и результаты уже подведены:

В субботу 8 ноября 2014 года в Санкт-Петербурге в Университете ИТМО состоится Северный четвертьфинал Северо-восточного европейского региона ACM ICPC. В соревновании будут участвовать 90 команд. Информацию и расписание соревнований можно найти здесь. Хотелось бы напомнить участникам, что необходимо удостовериться, что вся ваша команда прошла регистрацию.

Кроме того, на Яндекс.Contest состоится зеркало Северного четвертьфинала, который является одним из этапов Кубка трех четвертьфиналов. Начало контеста ожидается в 12:30 по московскому времени.

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

Фотографии можно будет найти здесь, вы также можете выкладывать свои фотографии с соревнования туда.

Мы планируем провести текстовую трансляцию, для этого мы пригласили эксперта, чемпиона мира ACM ICPC 2014 в составе команды СПбГУ, Дмитрия Егорова (Dmitry_Egorov).

Официальный хэш-тег Северного четвертьфинала #NSNEERC

Удачи всем участникам,
Пресс-служба соревнования.

UPD: Текущая таблица результатов

UPD2:

Поздравляем команды, прошедшие в полуфинал:

1 SPb ITMO University 1 (Korotkevich, Vasilyev, Minaiev)

2 SPb State University 2 (Voronetskiy, Krachun, Kuzmina)

3 SPb ITMO University 3 (Podtelkin, Zban, Belonogov)

4 SPb State University 5 (Simonov, Sayfutdinov, Gordeev)

5 SPb State University 1 (Andreev, Sokolov, Pyshkin)

6 SPb State University 3 (Avdyukhin, Savchenkov, Malinovskii)

7 SPb ITMO University 2 (Yakutov, Filippov, Bardashevich)

8 SPb Academic University 2 (Stepanov, Smirnov, Podguzov)

9 SPb Academic University 1 (Sluzhaev, Akimov, Karpov)

10 SPb ITMO University 4 (Kucherenko, Garder, Kovsharov)

13 Northern (Arctic) Federal University 1 (Rodionova, Popovich, Chesnokov)

20 Petrozavodsk State University 1 (Krasnov, Starkov, Ermishin)

22 Pskov State University 1 (Shantarin, Kovalenko, Shalabod)

26 Petrozavodsk State University 3 (Alkin, Ermolin, Komlev)

27 SPb State Polytechnic University 6 (Geller, Mordberg, Svitkin)

30 Petrozavodsk State University 2 (Shapovalov, Golovachuk, Kukushkin)

38 SPb SU of Telecommunications 1 (Tarasov, Yastrebov, Kiselev)

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

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

А где текстовая трансляция? По хэш тэгу в твиттере что то не густо. Трансляция вот по этому тэгу

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

Как решать F?

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

    Не знаю, понятно ли будет то, что я написал. Наверное нет, поэтому закину сразу ещё свой Accepted код: http://pastebin.com/5i8rQNYp (в первой правке код WA18, перепутал!)

    Сначала сожмём исходный массив, чтобы не было одинаковых подряд идущих чисел (считаем, что мы их уже объединили).

    Далее для каждого встречающегося в массиве числа i посчитаем nx[i] — следующее по величине встречающееся. Ясно, что объединить число с наименьшим превосходящим его за всё время можно будет не более одного раза.

    Будет хранить булевский массив fin[n], где fin[i] == true если на этом месте заканчивается очередная группа чисел. Например, для 6 4 5 1 2 3 его нужно будет заполнить T F T F F T.

    Как заполнять? Первая идея — взять и поставить false везде, где a[i + 1] = nx[a[i]], но учитывать при этом, что для каждого числа объединять его со следующим по величине числом можно лишь единожды. Это у меня давало WA11. Валится, вроде, таким тестом: 1 2 3 4 2. 1 2 3 4 объединим, а последнюю двойку теперь никуда не засунешь.

    Заведем теперь cnt[i] — сколько раз число i встречается в сжатом массиве. Если оно равно одному, мы можем спокойно объединять единственное встречающееся число i с двух сторон. Например, 1 2 3, двойку можно объединить и с 1 и с 3. А в 1 2 3 2 двойка встречается уже два раза, и её можно объединить либо с 1, либо с 3, но не с тем и другим.

    Для каждого встречающегося числа i заведем vector (или ArrayList :3) pos[i] таких чисел, что a[pos[i][j] + 1] = nx[a[pos[i][j]]]. К этому моменту уже можно было догадаться, что проще сжать числа, чтобы они тоже стали от 1 до какого-нибудь k и избавиться от nx. Мне почему-то было лень это делать и я дорешал задачу без этого, но дальше буду писать так, как будто они сжаты.

    Теперь мы знаем вот что: для какого-то числа i, если мы возьмем из его вектора pos число j, мы можем сделать fin[j] = false, уменьшив на единичку число групп, но при этом если cnt[j + 1] > 1, то число на позиции j + 1 объединять будет нельзя, и fin[j + 1] уже точно должен будет остаться true.

    Для каждого числа i мы хотим выбрать такое число j из массива pos, чтобы цепочка объединений i с i + 1, i + 1 с i + 2 etc. получалась как можно длиннее. Это двумерная динамика. Допустим, для числа i мы знаем длину такой цепочки для каждого из чисел массива pos[i], эти длины записаны в vector d[i] соразмерным с pos[i]. Хотим посчитать для числа i — 1. Тогда если pos[i — 1] пуст, то d[i — 1][j] = 0 для всех j, иначе если cnt[i] == 1, то d[i — 1][j] = d[i][0] + 1 (если d[i][0] существует, если не существует, то d[i — 1][j] = 1), иначе это максимум из всех d[i][x] кроме той, в которой pos[i][x] == pos[i — 1][j].

    После этого надо ещё вернуть ответ.

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

J test no 7?

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

    Если дошли до финиша, просто компенсируйте ветер.

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

      так и сделал.

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

        Ну в 7 ответ — yes. Поставьте ассерты, что расстояния между точками в вашем ответе хорошие.

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

Приносим свои извинения за то, что Северный Аркитческий Федеральный Университет на закрытии был неудачно сокращен до "Northern"

Не менее удачно он стал Аркитческим xD

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

Как решать Д?(стыдно=))

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

    тут мой код, я не понимать почему он падает на ВА3, разбор прочел. Решение вроде бы как в разборе. А есть ли тесты?)

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

      Выводить надо не при первом же прохождении условия if (cc[cnt].X == n), а найти минимум для всех разумных cnt.

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

        блин так и делал, потом переписал на это, думая чтот это то что просят в разборе. Обидно что зашло вписав н == 1, хотя на контесте думал что надо выводить 0( Спасибо.

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

      ВА3 это случай н==1, когда надо выводить 1, а не 0, как некоторые делали ручками ифом(потому что positive integers)

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

can i solve this contest in gym,thank you

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

А никто не знает сколько команд от Крыма пройдет в полуфинал?)

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

is there a solution?

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

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

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

    С чекером у задачи H какие-то проблемы :-( . Почему-то у меня постоянно выводит ВА12. Решил включить тренерский режим и посмотреть, что за вердикт выводит, а тут вижу:

    #12: WRONG_ANSWER [31 ms, 0 mb]: Error: An unexpected error occurred while trying to open file Check.jar8
    

    Номер посылки 8748018.

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

    Прошу прощения, но у еще есть проблемы с чекером на задачу E. Там сейчас стоит чекер, который сравнивает вывод один к одному. а это не всегда правильно, потому что ответ может быть не единственным. Правда тесты там такие, что и с таким чекером задача сдается. Вот только почему-то в тестах у них, если нет ответа, написано "No", хотя в условии сказано, что выводить нужно "NO".

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

Стыд и позор мне OVER 9000, но тем не менее я всё ещё легитимный участник ACM ICPC

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

тренировка с задачами западного четвертьфинала будет?