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

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

Сегодня в 16.00 по московскому времени пройдет вторая индивидуальная олимпиада на neerc. Правила, как я понимаю, будут абсолютно такие же как и в прошлый раз.

Всем желаю удачи!

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

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

если я зарегестрировался после начала, заявку уже не подтвердят?

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

киньте ссыль на задачи плз

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

Написал на D какой-то бред с неявными графами на 60 баллов. Как решалось нормально?

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

    Я писал такое же, но оно норм работает и при больших тестах.

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

      а где результаты посмотреть можно? :)

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

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

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

    Где-то есть результаты, или это твои ожидания?

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

    Не знаю, верно ли это... Персистентный снм. Построим вначале 1 версию для одинаковых цветов. Теперь идем по матрице. Вот у нас есть 2 соседних различных цвета u и v. Находим в хеш-таблице версию, где мы последний раз объединяли эти 2 цвета, в каких-то компонентах. Теперь по этой версии делаем новую, в которой компоненты, где сейчас эти 2 цвета лежат, объединены. Обновляем версию в хеш-таблице.

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

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

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

      1) разбиваем ячейки одинакового цвета на компоненты связности

      2) между каждыми двумя ячейками с различными цветами проводим ребро. Ребро — это номера двух различных цветов и двух номеров различных компонент связности, которым принадлежат ячейки

      3) сортируем ребра по паре цветов ячеек

      4) пробегаемся по ребрам и выделяем группы с одинаковой парой цветов ячеек. В каждой группе соединяем компоненты с помощью СНМ с поддержкой весов компонент. После каждого объединения обновляем ответ если вес текущего корня больше найденного ответа

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

        не очень понятна следующая вещь, если у нас есть ребро (1;2) и (2;3) (это пары цветов, которые соединяет), то мы соединим 1 и 2, и 2 и 3, и получим, что 3 компоненты (их цвета 1 2 и 3) войдут в ответ.

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

          если есть ребро (1 2) и (2 3) то это разные группы

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

            т.е. для каждой группы, у нас свой снм?

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

              у нас один СНМ, но после каждой группы (группа — ребра с одинаковой парой цветов ячеек (1 2) == (2 1)) его надо очищать, а для этого запомним номера компонент которые мы "трогали" в текущей группе и потом за О(размера группы) возвращаем затронутым компонентам их начальные значения (p[i] = i)

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

Как С писать выше 40?

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

как решать С?

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

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

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

    Более сложную можно решить с помощью 2-SAT, эту тоже .. Но я думаю, есть более простое решение ..

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

Кнопку feedback организаторы просто так поставили или ее можно только в определенную фазу луны использовать?

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

    Перед всеросом можно и перед иоип, перед региональным этапом нет.

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

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

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

http://neerc.ifmo.ru/school/io/archive/20121215/standings-20121215-individual.html на сайте ссылки еще нет, поэтому вот(:

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

почему у многих так попадала Б? 500^3 не впихнулось?

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

    Сам не пойму

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

    Кто-нибудь добавит этот контест в тренировки? Мне кажется, что там не ТЛ, а ВА.

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

Как решать задачу Б?

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

-

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

Кто-то может написать полный разбор по задачам B, C, D?

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

Добавьте, пожалуйста, данное соревнование в тренировки.

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

Напишите, пожалуйста, разбор задач B, C, D. Если разбор лень — хотя бы просто идею.