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

TopCoder SRM 496
Автор Egor, 13 лет назад, По-русски
Будет через пол часа
Одному мне письмо с напоминалкой не пришло?
  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Мне пришло. Вчера в 14:35:49.
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
31 января 2011 г. 11:41
TopCoder(R) Single Round Match 496 is scheduled for Tuesday, February 1, 2011 at 7:00 UTC -5 hours.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Мне тоже приходило.
→ Ответить
13 лет назад, # |
← Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

Ну и комната попалась... kuniavski, Gassa, Adamax (не пришел), elizarov...

А задачи Div. 1 вроде проще, чем обычно. Хотя всё равно интересно как вторую решать. Да и третью.

UPD: Кстати из комнаты не пришел только один участник, что радует.

UPD 2: Так как решать Div. 1 - 500 и 950?

UPD 3: Кажется первое непадение из Div. 1 -- 211 место.

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    500:
    Решал брутфорсом
    Перебирал все возможные значения скорости, строил двудольный граф, где в одной доле - старые координаты, во второй - новые
    Для каждой компоненты связности перебором считал число способов разместиться, далее перемножал результаты для всех компонент и прибавлял к ответу
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится
      Каждая компонента связности будет "змейкой", так что количество вариантов можно посчитать и по формуле
      → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    500 - фиксируем модуль расстояния, преодоленного шариками. Тогда у нас все распадается на некоторое количество независимых подсистем и в каждой подсистеме вариантов - число шаров в подсистеме + 1. Перемножаем, получаем ответ для данного времени. Подсистема - это когда у нас есть несколько шариков на первой картинки, для каждого из которых 2 варианта на 2й и при этом каждый, кроме крайних, из этих вариантов является вариантом для 2 шариков с 1й картинки
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Насчет 950 - если мне кто-то объяснит, почему мое решение работает - будет круто
    Писал в последний момент, за 2 минуты до конца дописал, оно сразу прошло семплы и, что самое удивительное, в итоге прошло систесты
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    В последнее время много обсуждений идёт что большинству участников в первом дивизионе дальше Easy идти не получается, вот и пытаемся немного сбалансировать. Вроде бы на этот раз получилось. Правда я сначала хотел ставить ставшую в итоге д2-хардом задачу на д1-изи, но Иван забраковал :)
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
я что то не понял чего там хотят (див 2 задача на 1000), странно как то
количество строк длиной N таких чтобы подстроки длиной M были палиндромами и чтобы их было не меньше K? 
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    У строки длинны N рассматриваются все подстроки длинны M, если из этих подстрок не меньше  K - палиндромы, то строка (длинны N) - палиндромополная. Нужно найти к-во палиндромополных строк длинны N, состоящих из латинских заглавных букв.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится
      а как ее решать? :)
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        ее решили три человека и все три китайцы.
        → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится
        Проходит перебором масок
        http://pastebin.com/6dJUapNe
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Можно ли решение словами? Смотрел код - не понял.
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится

            Можно и не масками. Пускай у нас используется m различных символов для нашей строки (не нарушая общности первый встерчающийся будет номером 1, второй 2 и т.д. (всего не более 11 символов будет)).

            Рассмотрим все возможные строки которые состоят из указанных символов с указанным порядком вхождения и проверим подходит ли она под условие палиндромности. Если подходит тогда ей соотвествует P26m строк из больших букв, причем различным строкам будут соответсвовать различные строки из исходных.

            Все строки генерируются и считается число палиндромов за O(N!), а при N = 11 этого более чем достатчно, чтобы вложиться в 2 секунды.

            → Ответить
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Можно найти все разбиения строки из N элементов, используя, например, схему Эрлиха. При N=11 разбиений будет 678570, http://oeis.org/A000110. Затем можно действовать, как написано выше - проверять палиндромность и, если подходит, умножать на P26m, где m - количество подмножеств в разбиении. 
              → Ответить
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Ага, это у меня на домене просто почта перестала ходить. Сейчас посмотрим, в чем дело
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А как посмотреть тест на котором меня почеленджили?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Примерно минут через 20-40 вся инфа появится на сайте.
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Что-то пока не появилась инфа пока, но должна будет появиться.
    → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    http://www.topcoder.com/stat?c=room_stats&rd=14425&rm=307129

    1) Please select a room: ищем свою комнату (можно в арене посмотреть в какой был)

    2) Кликаем на  у себя.

    3) Problem Information for %username% - Problems - Class Name - Выбираем. Снизу смотрим.

    → Ответить
13 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
Невероятно!
Отправил div1-500 за 3 сек до конца и AC!
Вот это поперло.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Поздравляю!)
    А я наконец-то на ТопКодере получил два АС'а!=)
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Слава, почему твое решение по 950 работает? :о)

 

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    1) Если отсортировать все строки лексикографически, получим минимум по всем гамильтоновым путям
    2) Если положить все строки в бор, сыновей любой вершины можно переставлять произвольно

    Чтобы получить нужные начало и конец, нужно "разорвать" вершину - lcp начала и конца, поправка на это у меня и вычисляется в последних двух строчках
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Спасибо. Красивое решение.
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      а можно как-нибудь доказать первый пункт? для меня он почему-то неочевиден
      → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        Очевидно, можно искать максимальный гамильтонов путь для графа с ребрами, равными lcp^2(s_i, s_j) вместо того, что написано в условии. Ну а в таком графе мы для каждой вершины в пути берем два (или одно) самых больших ребра, так что путь максимален.
        Мне скорее непонятно, как формально трюк с разрывом в середине и добавлением ребра между максимальной и минимальной строками объяснять.

        ===
        Ох, да, чушь написал. См. ниже.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится
          "Ну а в таком графе мы для каждой вершины в пути берем два (или одно) самых больших ребра, так что путь максимален."

          Это неправда. Например, если у нас есть "a", "bba", "bbb", "bbc", то "bba" соединяется ведь с "a" и "bbb", а не с "bbb" и "bbc".

          ===

          В целом второй пункт легко обосновывается, если в первом пункте доказать, что это не только оптимальный гамильтонов путь, но и оптимальный гамильтонов цикл. Тогда мы посредством перестановок сыновей ставим 0 и 1 рядом в цикле, а отсюда сразу следует, что если разорвать ребро между ними, то получится оптимальная гамильтонова цепочка.

          Для доказательства первого пункта в принципе нужно доказать, что (в гамильтоновом цикле или пути), если у вершины бора есть несколько сыновей, то обязательно все слова внутри каждого из соответствующих поддеревьев посещать "за один заход". Это несложно доказать от противного.
          → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кто-нибудь знает как найти количество совершенных паросочетаний в двудольном графе? А то я в 500ке до этого дошёл а как посчитать не знаю.
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
    По 500-ой есть решение без этого, смотри выше. Вообще я где-то такую задачу видел. Сейчас попытаюсь вспомнить решение. Если вспомню напишу.

    UPD :Не видел, там было найти все ребра которые могут лежать в совершенном паросочетании.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я чёт не очень понял почему перебор должен быстро работать. И что за "змейка" и как в ней считать ответ.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Пусть все шарики упорядочены по возрастанию
        Если i шарик можно переместить в положения x1, x2, тогда не существует такого шарика j, который можно переместить в те же положения (т.к. x[i] = (x1 + x2) / 2 - однозначно).
        Следовательно, при j > i, j может попадать либо в x2, либо не попадать в x1, x2 вообще. Аналогично при j < i. Отсюда получается, что каждая компонента связности - "змейка", и простой перебор на ней будет работать (думаю, что за O(l^2), но могу ошибаться)
        → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Мне кажется это NP-полная задача в общем случае.
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Это #P-полная задача (еще хуже чем NP-полная:)) называется перманент.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Точнее 0-1 перманент. Она #P полна как и перманент
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Скажите пожалуйста, а такое решение по 950-ой не должно работать или я накосячил в реализации?

1. Посортируем все строки.
2. Две наши разбивают множество строк на 5 частей. - сами строки, то что меду ними и то что по сторонам от них.
3. Для каждой части взяли крайние точки.
4. Построили на этих точках такой граф - для не соседних - их lcp в квадрате, для соседних - сумма квадратов lcp по всем последовательным между ними.
5. Нашли в этом графе максимальный по сумме гамильнов путь.
6. Ответ - 2 суммы квадратов длин строк - квадраты длин наших строк - путь который мы нашли.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
что такое #P-полная задача?
→ Ответить