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

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

16 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится
Мне пришло. Вчера в 14:35:49.
16 лет назад, скрыть # |
← 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.
16 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится
Мне тоже приходило.
16 лет назад, скрыть # |
← Rev. 5  
Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

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

  • 16 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +3 Проголосовать: не нравится
    500:
    Решал брутфорсом
    Перебирал все возможные значения скорости, строил двудольный граф, где в одной доле - старые координаты, во второй - новые
    Для каждой компоненты связности перебором считал число способов разместиться, далее перемножал результаты для всех компонент и прибавлял к ответу
  • 16 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +6 Проголосовать: не нравится
    500 - фиксируем модуль расстояния, преодоленного шариками. Тогда у нас все распадается на некоторое количество независимых подсистем и в каждой подсистеме вариантов - число шаров в подсистеме + 1. Перемножаем, получаем ответ для данного времени. Подсистема - это когда у нас есть несколько шариков на первой картинки, для каждого из которых 2 варианта на 2й и при этом каждый, кроме крайних, из этих вариантов является вариантом для 2 шариков с 1й картинки
  • 16 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Насчет 950 - если мне кто-то объяснит, почему мое решение работает - будет круто
    Писал в последний момент, за 2 минуты до конца дописал, оно сразу прошло семплы и, что самое удивительное, в итоге прошло систесты
  • 16 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    В последнее время много обсуждений идёт что большинству участников в первом дивизионе дальше Easy идти не получается, вот и пытаемся немного сбалансировать. Вроде бы на этот раз получилось. Правда я сначала хотел ставить ставшую в итоге д2-хардом задачу на д1-изи, но Иван забраковал :)
16 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
я что то не понял чего там хотят (див 2 задача на 1000), странно как то
количество строк длиной N таких чтобы подстроки длиной M были палиндромами и чтобы их было не меньше K? 
  • 16 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +2 Проголосовать: не нравится
    У строки длинны N рассматриваются все подстроки длинны M, если из этих подстрок не меньше  K - палиндромы, то строка (длинны N) - палиндромополная. Нужно найти к-во палиндромополных строк длинны N, состоящих из латинских заглавных букв.
16 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится
Ага, это у меня на домене просто почта перестала ходить. Сейчас посмотрим, в чем дело
16 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
А как посмотреть тест на котором меня почеленджили?
16 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится
Невероятно!
Отправил div1-500 за 3 сек до конца и AC!
Вот это поперло.
16 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

 

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

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

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

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

          ===

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

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

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

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