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

Открытый чемпионат УрГУ 2010 - Онлайн версия
Автор Egor, 14 лет назад, По-русски
9 октября в 11:00 MSD на сайте Timus состоится онлайн версия Открытого чемпионата УрГУ 2010. Нету абсолютной уверенности, но мне кажется там будут те задачи, что были на этапе Открытого кубка. Всем удачи!
  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Хороший контест! Может кто нибудь рассказать как делалась I?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Хотя кажется уже понял) ( за nlogn), только не ясно зачем условие про xyxyx
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Понял сам, расскажи другим :)
      → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      без условия про xyxyx кол-во операций необходимых для получения строки может быть до N(N = длина строки). С этим же условием кол-во операций получается порядка O(Log(N))

      Решать надо с конца, т.е. выполняются обратные операции.
      Нужно делать операцию double порядке O(Log(N)). А front и back использовать, чтобы можно было провести очередную double.
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Так можно же, вроде, динамикой найти минимальное число операций. Без использования xyxyx.
        → Ответить
        • 14 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
          можно) но можно используя и не писать ни какой динамики)
          если я не ошибаюсь, то можно любую такую строку сделать за не более, чем (Log2(N) + 1) * 5
          → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            А можете прояснить, откуда следует факт про количество операций?
            → Ответить
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Строго не доказывал) Почеркался на бумажке и получается так :)
              → Ответить
14 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
А как F (Великая команда) делать?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Необходимо, чтобы i-ый человек дружил со следующим диапазоном людей [i + 1, n - i + 1].
    Для n=6 результат такой:
    9
    1 2
    1 3
    1 4
    1 5
    1 6
    2 3
    2 4
    2 5
    3 4
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Авторское решение - все пары чисел такие, что |i - j| <= n / 2.
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Я только D,F решил и J не успел сдать =(
Кто-нибудь может сделать разбор задач? 
На контестах ни разу больше половины задач не решал((
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А я тока CDFH )) (и I после контеста но не сдавал так что может и неверно) В G почему то WA31 все время.

С) - динамика нужно посчитать для каждого n и k вероятность того что мы сделаем параллельных k запусков на отрезке из n не запущенных ракет. Переход за O(n) . В итоге O(n^3)

H) Рассмотрим орграф который задает эта матрица. Тогда операция описанная в условии это просто перенумеровка вершин в этом орграфе. Получается нужно найти такой порядок вершин чтобы в первую вершину не входило ребер вообще, во вторую вершину могли входить только ребра из первой вершины и.т.д. Это можно сделать, например топологичесокой сортировкой (очевидно что если в графе есть цикл то ответ -1). В итоге получим нужную перестановку, потом просто разбить ее на <= n транспозиций и выдать как ответ.

I) Рассмтрим все последовательности длины <= n которые можно получить из 0 или 1 за 1,2,..log(n) операций double. Получим O(logn) строк для каждой из них можно через КМП найти все вхождения в нашей финальной строке за O(nlogn). Дальше динамика - нужно разбить нашу строку на строки описанные выше причем так чтобы сначала их длинны не убывали а потом не возрастали . Это Можно сделать за nlogn
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Не мог бы кто нибудь более подробно объяснить динамику для задачи C ?

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

      у нас получилось через две решить, первая

      dm1[n][k] - вероятность того, что мы запустим n подряд идущих ракет не более чем за k залпов. 

      dm2[n][k] - вероятность того, что мы запустим n подряд идущих ракет ровно за k залпов. 

      Одно состояние каждой динамики пересчитывается за линию, т.е.  переберем ракету, которая взлетит,  с позиции от 2 до n - 1, и не забыть посчитать вероятности для крайних ракет . Кстати у нас не прошла  рекурсия, пришлось прекалк сдавать либо, снизу вверх считать.

      Upd. dm1[n][k] = Сумма dm2[n][i] по i = 1..k

      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Спасибо, но хотелось бы узнать по подробнее про подсчёт самих вероятностей. Как получаются формулы перехода в динамике.
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          http://ideone.com/63Bt5
          ну вот поразбирайся только тут dm1 и dm2 наоборот как я писал
          → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Я использовал только вторую динамику.
        → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
A) К каждому магу прикрепим атрибуты a (прибытие), b (последний момент, когда он ещё у Цирюльникуса), с (сколько раз ещё надо побрить, вначале 2), n (номер мага). Добавим всех магов в очередь с приоритетом, где приоритет описывается функцией

bool operator < (const mag &m) const {
    return a > m.a || (a == m.a && (b > m.b || (b == m.b && c < m.c)));
}

Рассмотрим по оереди моменты времени 0, 1, ..., 1000. Для каждого момента попробуем из очереди взять не более k элементов и каждый обработать следующим образом: увеличить a на 1, уменьшить c на 1 (и запоминаем, в какой момент времени побрили определённого мага); если c стал 0, значит, мага побрили полностью; если c больше 0 и всё ещё a < b, вставляем обратно в очередь; если a = b и c > 0, то этого мага второй раз побрить уже никак не получится, выводим "No", завершаем работу. Если после 1000 итерирований мы ещё не вывалились, значит все побриты, выводим "Yes" и весь заранее запомненный список.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Это не правильно.  Хотя бы не достаточно проверять моменты времени от 0 до 1000. Нужно хотя бы от 0 до 1199.
    И как я понял сначала рассматриваются элементы с большим приоритетом?
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Хм, да, я почему-то решил, что любые a и b не вылезают за отметку 1000. Тесты, однако, прошло :/
      Например, если есть маги (2, 4, 1, 1), (3, 4, 2, 3) , (3, 4, 1, 2) (по форме (a, b, c, n)), то в таком порядке, слева направо, они и будут взяты из очереди.
      → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я брал отрезки с меньшим b, а при равенстве b - с большим c.
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Решение потоком прозрачнее =)
    → Ответить
    • 14 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      И, видимо, единственно верное
      http://acm.timus.ru/forum/thread.aspx?space=1&num=1774&id=25330&upd=634229362011113750
      → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
K) Будем сравнивать последовательные столбцы входной таблицы. То есть сначала столбец из двоек сравниваем со столбцом из троек, затем столбец из троек со столбцом из четвёрок и т.д. Каждая такая пара столбцов определяет некоторую перестановку мастей. Разобъём эту перестановку на циклы. Для каждого цикла длины больше 1 прибавим к ответу его длину плюс один. Например, для перестановки (1, 3) (2, 4) к ответу прибавится 6, а для перестановки (1, 2, 3) (4) к ответу прибавится 4. Accepted.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
G) Как известно, должны выполняться равенства

k[0] = x[0] и k[i] + k[i  + 1] = x[i  + 1] (сумма в Z2)

Фактически, мы получаем систему уравнений на k[i] для таких i, что x[i + 1] != '?'.
Те i, для которых x[i + 1] = '?', мы просто выпустим из рассмотрения.

Итак, у нас есть набор соотношений вида k[i] + k[i + 1] = c.

Пройдёмся по списку этих соотношений слева направо.

Если оба k[i] и k[i + 1] известны, то просто проверяем это равенство (и если оно не выполнено. то выводим "Impossible"). Если из k[i] и k[i + 1] неизвестно ровно одно, скажем, k[i + 1], то находим его из данного соотношения, и с этого момента значение k[i + 1] тоже считается известным. Если же неизвестны оба k[i] и k[i + 1], то ничего не делаем. 

Как только мы пройдём весь список соотношений, развернёмся и пробежимся по нему обратно, проделывая по ходу то же самое.

Теперь, если у нас остались ещё не опеределённые переменные k[i], то выводим "Ambiguity", иначе, восстанавливая x[i] по всё той же формуле x[i + 1] = k[i] + k[i + 1], выводим ответ.

Интересно, кто как ещё решал эту задачу. 


→ Ответить
  • 14 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    Я использовал факт, что  (g(k) ^ k)== (k >> 1), где g(k) - k - элемент кода грея (k от 0)
    Получалась не сложная линейная динамика) Т.е. если i-бит в числе k равно 1, то (i-1)-биты числа k и k-ого числа грей противоположные, иначе одинаковые. Отсюда и вытекает динамика :)
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А как решать B?
→ Ответить
  • 14 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    фиксируем две кегли ( учитывая направление ), находим k-ое расстояние от этой прямой до остальных точек находяшихся справа от этой прямой, в итоге решение за куб. Бин поиск там вроде как непроходит по времени.
    → Ответить
    • 14 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      Решение за O(N^3 * log N) проходит, только надо повжимать, как сказали на разборе.
      UPD. Не надо ничего вжимать =) Заходит с большим запасом - 0.365. Но логарифм лишний - можно обойтись встроенным nth_element, который работает за линию - это 0.265.
      → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В H у меня решение - вообще идти от последней строки к первой, и всякий раз на место текущей строки ставить одним свопом любую из подходящих (среди предыдущих) строк.

Доказательство - во-первых, что решив задачу для последней строки, ничего не нарушится для неё потом. Во-вторых - почему для получения последней строки нет смысла рассматривать какие-то сложные цепочки операций, а только одним свопом - это я понимаю скорее интуитивно, порисовав на бумажке :)


K - решал динамикой по состоянию - позиции в каждой из колод (т.е. 13^4). Ключевое - считать, что все остальные карты (которые мы извлекали из этих 4 колод) всегда сложены оптимально (т.е. все куски, которые можно объединить в одну колоду, уже объединены). Но решение выходит неприятное по реализации, много тонкостей.

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

Расскажу наши решения)
А - то, что сказано выше - я приделал каждому магу время финиша и сколько еще раз его надо побрить) Потом шел по времени и обрабатывал их жадно в порядке появления - если время окончания неравно, то перым бреется тот, у кого оно меньше, если равно, то тот, кому надо бриться больше раз)
В - не успел додебажить) Мы сперва писали сеточку - получили ВА 35) потом придумали нормальное решение, но уже не успели - сжимаем все курги в точки, перебираем все пары точек, на них строим прямую - она даст угол наклона - потом сортим все точки по этому углу и находим К-ую от нашей прямой - и релаксируем ответ. В принципе сортить не обязательно - Кая порядковая статистика сделает сложность О(n^3)
C - Писал не я, но решение - ДП, которое было описано выше
D - Легкая задача - просто моделируем то, что написано, предположив/доказав, что нам потребуется мало шагов до нахождения ответа
E - вообще не знаю как
F - abs( i - j ) <= n/2 - вроде так
G - по факту k[i-1] xor k[i] xor x[i] = 0 - из этого я сделал ДП по i и маске битов. Значения 0 - нельзя получить, 1 - можно одним способом (запомним маску откуда ), 2 - несколькими способами) Отсюда в конце найдем ответ
H - Я написал топосорт по матрице - то есть как сказали в разборе - это граф и надо сделать топосорт. Искал нулевой столбец ( вершину с 0 степенбю ) и ставил ее вперед и тд.
I - Писал решение описаное выше - 5 операций на шаге)
J - Влоб - писал бин поиск - и находил для каждого шага ответ.
К - Идем по картам снизу вверх - смотрим 2 профиля - на них ищем перестановку и смотрим число циклов длины > 1. Для каждого цикла увеличим ответ на длину цикла + 1

Как то так мы и решали)

→ Ответить