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

SRM 525
Автор yarrr, 13 лет назад, По-русски

Сегодня, 16:00 MSK

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

13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
Эх, жаль не смогу написать. Только вернулся с 16-часовой поездки с полуфинала. Буду отсыпаться :)
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Сильный состав в этот раз =)
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
Блин, пытался зачеленджить в решении за O(n^6) (n до 30) и не получилось. Жаль что tc такой быстрый... :D
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Видел 2 таких решения. Побоялся челенджить, видимо не зря. 
    Теперь наоборот обидно, что зря писал массив частных сумм)
    → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    Там получается 30^6 / 8, что даже меньше 10^8

    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    Это не так и много. Учитывая, что нужно ещё разделить на 8 (по крайней мере в моём коде), получается около 100М.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      А почему надо делить на 8?
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +7 Проголосовать: не нравится
        По той же причине, что и 
        forn(i, n) forn(j, i)
        выполняет N*N/2 операций, а не N*N.
        → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Не на восемь, а на больше. Там около двадцати пяти миллионов сложений получается.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Кстати, легко проверить, что на 36 делится на самом деле.
          → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как решать 525?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Переберем 2^n способов (каждый заяц либо сначала рассказывает первую сплетню, потом вторую, либо наоборот) и промоделируем.
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    bfs с перебором по приоритету для каждого кролика проходит? А то я тормоз, не успел закодить =(
    → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Я так решал:


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

    Тогда переберём маску приоритетов (какой номер сплетни он будет рассказывать первым) и проэмулируем процесс. Итого: О(2^n * n^3).
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      У меня в 525 2^n*n^3 (n ходов по n^2 пар взаимодействий) упало, посмотрю потом, по ТЛ или набажил.

      На моих тестах меньше секунды работало.

      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А, я нагнал, у меня куб тоже: для каждого дня перебираем кролика, а затем его друзей. Писал на Джаве, зашло.
        → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Такое же решение, прошло.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится -14 Проголосовать: не нравится

          ТЛ на одном тесте.

          На одном из 127.

          Уже пропихнул, обидно.

          Из-за вот такой ерунды - отстойность моего рейтинга неизлечима:(


          → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится
      >каждый заяц
      >каждому пингвину
      Все читают по-своему. Не удивлюсь, если кто-то их белочками называл :)
      → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +28 Проголосовать: не нравится

        Я помню была задача где действующими персонажами были pedestrian и vehiclist. Угадайте как называли все первого чувака? После контеста я обсуждал задачу в аське со своими знакомыми ацщиками, и мы все, не сговариваясь называли его одинаково. А там еще тонкость какая-то была, из за неё все хватали пару минусов до акцептеда.

        → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ну вот, я неправильно условие прочитал. Думал, что за день кролик может рассказать сплетню определенного вида только одному кролику. Надо учить английский.
    → Ответить
13 лет назад, # |
← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

Идея решения 900. Можете оценить и сказать, насколько это верно? С виду - лажа лажей. Отправить не успел.


В условии даны два графа, мы хотим построить такой изоморфизм, чтобы количество циклов в его перестановке было максимально. Я утверждаю, что таких изоморфизмов O(1), точнее, около 4!. Найдем их все.

Посмотрим, что за граф дан в условии. Это один большой цикл на N вершинах и еще несколько ребер. Представим его многоугольником. Тогда в нем проведены две горизонтальные диагонали посередине и все вертикальные. Переберем во втором графе четверку вершин v1, v2, v3, v4. В том, к которому нам нужно привести, они соответствуют вершинам 1, n/2, n/2+1, n. Во-первых, должны быть ребра v1-v2, v2-v3, v3-v4, v4-v1. Во-вторых, если эти ребра выкинуть, то кратчайший путь между v1 и v2 должен быть равен n/2-1, между v3 и v4 - тоже. Восстановив путь, мы однозначно увидим порядок вершин в многоугольнике. Ну и потом изоморфизм нужно проверить.

Переберем все такие изоморфизмы. Из всех перестановок выберем лучшую.
→ Ответить