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

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

Пару месяцев назад мы провели очередную межвузовскую командную олимпиаду. Тренировка по задачам этого контеста состоится в воскресенье, 7 июня, в 13.00 по Московскому времени.

Авторами задач данного соревнования являлись Sinner, dalex, Slamur, также неоценимую помощь в подготовке оказали craus, Shlakoblock и I_love_natalia.

Зайти в контест вы сможете на этой странице: Тренировки Codeforces

Список предыдущих наших контестов:

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

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

Спойлер к одной из задач:

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

    Баян с прошлогоднего NEERC.

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

    Ну да, там дано куча чисел, разделенных пробелами и переводами строк, надо вывести максимум и минимум, тут и без условия все понятно.

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

      Problem M. Minimum

      (извиняюсь за некропостинг, тему всё равно до меня подняли)

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

I have some question(I am new in CF & it is my first GYM contest):

  1. Can anyone participate(Div.1/Div.2)?
  2. Is rating change?
  3. Is there any registration process?

Sorry for my poor English. Thanks in advance.

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

    It will be gym contest, so:

    1. Anyone can participate.
    2. It will be unrated.
    3. Registration will be opened during all contest.
»
9 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Reminder: the contest starts soon, the registration is opened.

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

Что в B нужно было забыть, чтобы не пройти 7 тест?

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

What is the idea for L ?

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

    K + 1 rings can be moved in 2K + 1 turns:

    • move K rings on K additional towers
    • move last ring on needed tower
    • move K rings from additional to needed tower

    So you can use next algo to move N rings:

    • move recursively N — (K + 1) rings on medium tower
    • move (K + 1) rings on needed tower in 2K + 1 turns
    • move recursively N — (K + 1) rings from medium to needed tower

    F(N) = F(N — K — 1) + (2K + 1) + F(N — K — 1)
    F(N) = 2F(N — K — 1) + (2K + 1)

    If you enumerate groups of (K + 1) rings, this fotmula will be:

    G(i) = 2G(i-1) + (2K + 1)
    G(0) = if (M = N mod (K + 1)) == 0 then 0 else (2(M — 1) + 1)

    It can be solved with matrix exponentation or even with deriving of formula.

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

Как F решать?

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

    Фиксируем тройку участников, строим граф: три вершины соответствующие нашим участникам, из них в сток ребра пропускной способностью равной их производительности. Затем пробегаем по всем задачам и делим на типы, тип — это 3х битовая маска, соответствующая кто из наших участников способен решить эту задачу, из этих вершин проводим ребра в соответствующие вершины участников. Пускаем поток.

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

      Можно понять, что выгодно делать так:

      1. Если участник один может решить задачу, то пусть он её решает

      2. Если задачу могут решить все трое, то рассмотрим такие в самом конце

      3. Теперь есть граф-треугольник, идём по всем парам участников и смотрим: если другой человек в паре не сможет в одиночку добить все задачи на этом ребре, то помогаем ему

      4. Просто идём по всем парам и решаем, что решается

      5. Каждый решает задачи, которые могут решить все трое, пока может

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

        А что с треугольником на сторонах которого написаны 2ки, а на вершинах 4,1,1. Если "помочь" какой-то из единичек добивать ребро смежное с 4кой, то ничего хорошего не выйдет? То есть 4ка должна взять оба ребра смежные с ней, а единички общими усилиями все ребро между ними.

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

Интересное решение по D:

для n = 1 или n = 2: FAIL.

для n != 4 и n != 6: значения от 1 до 3*n по порядку заполняем в массивы по следующему правилу: 1, 2, 3, 2, 3, 1, 3, 1, 2, 1, 2, 3, ...

для n = 4: полный перебор всех вариантов.

для n = 6: ответ на тест дан в условии к задаче.

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

    Вообще это баян с кодчефа, но там была более общая задача — было не обязательно три кости

    Насчет случая с 6 — обычное решение работает и для него. Поэтому частный случай только с четверкой.

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

      Странно, я сколько пересчитывал на листочке, для 6 не работало... Видимо устал и посчитать до 19 сложнее, чем кажется.

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

        Увидев число 19, могу предположить, что это 36 / 2 + 1, значит скорее всего вы проводили пересчет влоб. Можно проще — так как мы всё зациклил, то число в i позиции однозначно больше всех других чисел из других граней на позициях меньше i, а следовательно нужно пересчитывать только для соответствующих элементов кости. То есть для n=6 нужно проверить только 6 пар чисел, из которых по приведенной схеме 4 будут в нужном направлении, две нет. Все оставшиеся пары разбиваются поровну, а значит эта схема подходит под условие.

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

    Я пробовал альтернативное решение по Д — будем делать random_shuffle(), пока все не станет классно :) Мне почему-то показалось, что там исходы более-менее независимы и вероятность попасть на правильное разбиение довольно высокая. На самом деле это совсем не так.

    В запуске для 1000 работало 0.15, но на 13 тесте поймало ТЛ. Сейчас попробовал с другими сидами rand(), стало только хуже и падает раньше.

    Пришлось докручивать конструктив.

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

      Расскажи пожалуйста L. А то мы видимо не смогли за весь контест понять условие

      Тест 9. (5, 1) — 13. Никакое наше понимание не дает ответа на вопрос, как это возможно

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

        k дополнительных стержней позволяют перекладывать блоки из L ≤ k + 1 последовательных дисков за 2L - 1 шагов : переложим все диски из блока кроме последнего на доп. стержни за L - 1 шаг, последний диск из блока на нужное место за 1 шаг, поставим диски с доп. стержней обратно за L - 1 шаг.

        Разбиваем так на блоки, самым маленьким блоком должен быть самый верхний, его перекладывали больше всего (остальные блоки будут по k + 1 дисков).

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

        Есть три обычных стержня (A,B,C) и один маленький, на которое только одно кольцо влезает (D).

        За 13 ходов можно сделать вот так (с A на C): A-D, A-C, A-B, C-B, D-B, A-D, A-C, D-C, B-D, B-A, B-C, A-C, D-C.

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

      Рандом шаффл я с I_love_natalia таки упихнул с приличным запасом за день до контеста. Основная идея: меняем случайные элементы местами, пока разность между минимальной и максимальной суммами костей больше какой-либо константы, например, 10. После этого проверяем за линию эту перестановку и всё по новой.

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

        Это уже умный шаффл :)

        Как вообще ведет себя число подходящих разбиений c ростом N? Вероятность "угадать", выбирая вообще случайные разбиения — уменьшается пропорционально какому-то полиному от N? Эмпирическим путем у меня получилось, что вероятность уменьшается примерно пропорционально росту N, но все же медленее.

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

как решить задачу Е ?
я пробовал деревом отрезков в котором держу минимальный показатель, и минимальный индекс где он встречаеться. Для первых К человек просто раскидывал их в касы, ну а потом для каждого следующего человека обновлял минимальный показатель...
не знаю на сколько понятно обьяснил как я решал... и простите за ошибки)
UPDATE всё таки доделал с деревом отрезков... опять накосячил из тупости.... спасибо тем кто ответил)

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

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

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

    добавляем все кассы в сет. На каждом шаге достаем минимум, пересчитываем, кладем обратно.

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

I was asked to write quick one-line hints for all problems. They are in the first revision.

There are also some typos but it's difficult to edit and make another spoiler, so I'll leave it as is.

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

У меня такой вопрос, будет ли выложен где-нибудь разбор по задачам этого контеста?

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

Any hint on question K please??

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

Can someone who has solved problem A post the 13th test-case here. I am getting WA and I can't figure out my mistake. Thanks. This is my code http://ideone.com/hPM1Ud Problem A

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

Не могу пройти 5 тест в B :((

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

    5-ый тест по B: 8 31 14. Ответ — 4 нажатия.

    Учтите, что оптимальными способами добраться до нужной клетки являются не только способ напрямую из стартовой клетки и способ с промежуточным посещением последней клетки.

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

Problem C can also be found in Algorithm Design by Kleinberg and Tardos (here)