Разбор задач квалификации: Engine

1769A — Узкая дорога

Будем определять положения самокатов по очереди в том порядке, в котором они указаны во вводе. Если aᵢ — это исходное расстояние от самоката i до пункта Б, то пусть bᵢ — это расстояние от самоката i до пункта Б через одну секунду. Тогда b₁ = a₁ − 1, и bᵢ = max(aᵢ − i, bᵢ₋₁ + 1) для i ≥ 2. Действительно, так как самокат i движется со скоростью i метров в секунду, то через одну секунду он сдвинется на i метров по направлению к пункту Б, если только он не упрётся в предыдущий самокат номер i − 1 — тогда новое расстояние составит bᵢ₋₁ + 1 метров.

Пример решения на Python:

n = int(input())
b = -1

for i in range(1, n + 1):
  a = int(input())
  b = max(a - i, b + 1)
  print(b)

1769B2 — Копирование файлов II

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

Пример решения первой версии на Python:

n = int(input())

a = list(map(int, input().split()))
s = sum(a)
p = 0
res = [0]
for i in range(n):
  for j in range(1, a[i] + 1):
    p += 1
    v1 = 100 * j // a[i]
    v2 = 100 * p // s
    if v1 == v2 and res[-1] != v1:
      res.append(v1)
print(*res, sep = '\n')

Во второй версии перебор всех байтов недостаточно эффективен. Вместо этого переберём значения от 11 до 100100 для каждого файла и определим, существует ли такой момент в процессе копирования этого файла, что оба прогресс-бара показывают данное значение.

Для этого нужно решить систему из двух уравнений:

Здесь x — искомое число байт (момент копирования), v — целевое значение в процентах, pᵢ = a₁ + a₂ + … + aᵢ₋₁, а s = a₁ + a₂ + … + aₙ.

Преобразуем уравнения в неравенства:

Преобразуем далее, используя то, что 𝑥x должно быть целым числом:

Наконец, вычислим оба значения в правых частях неравенств и сравним между собой, чтобы узнать, существует ли подходящее для нас x. Для вычисления ⌈a/b⌉ можно использовать формулу (a + b − 1) div ⁡b, где div — целочисленное деление.

Также вместо решения неравенств в явном виде можно было воспользоваться бинарным поиском.

Пример решения второй версии на Python:

n = int(input())
a = list(map(int, input().split()))
s = sum(a)
res = [0]
for v in range(1, 101):
  p = 0
  for i in range(n):
    low  = max((v * a[i] + 99) // 100,           (v * s + 99) // 100 - p)
    high = min(((v + 1) * a[i] + 99) // 100 - 1, ((v + 1) * s + 99) // 100 - 1 - p)
    if low <= high:
      res.append(v)
      break
    p += a[i]
print(*res, sep = '\n')

1769C2 — Подкрутка II

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

Сложность решения составит O((aₙ − a₁) ⋅ n).

Пример решения первой версии на Python:

for _ in range(int(input())):
  n = int(input())
  a = list(map(int, input().split()))
  ans = 0
  for left in range(a[0], a[-1] + 1):
    right = left
    for x in a:
      if x == right or x + 1 == right:
        right += 1
    ans = max(ans, right - left)
  print(ans)

Есть несколько вариантов решения второй версии задачи. Представим решение при помощи динамического программирования. Пусть f(i, j) равно длине максимального отрезка дней, заканчивающегося коммитом номер i, если сам этот коммит был сдвинут на j дней вперёд (1 ≤ i ≤ n; 0 ≤ j ≤ 1). Чтобы вычислить f(i, j), переберём сдвиг предыдущего коммита k (0 ≤ k ≤ 1) и вычислим разность между новыми днями коммитов: d = (aᵢ + j) − (aᵢ₋₁ + k). Если значение разности d лежит в диапазоне от 0 до 1, значит, отрезок, заканчивавшийся коммитом номер i − 1, сдвинутым на k дней вперёд, может продолжиться при данных условиях, и новая длина отрезка составит f(i − 1, k) + d дней.

Ответом на задачу будет являться максимум по всем найденным значениям f(i, j).

Сложность решения составит O(n).

Пример решения второй версии на Python:

for _ in range(int(input())):
  n = int(input())
  a = list(map(int, input().split()))
  f = [[1] * 2 for i in range(n)]
  ans = 1
  for i in range(1, n):
    for j in range(2):
      for k in range(2):
        diff = (a[i] + j) - (a[i - 1] + k)
        if 0 <= diff <= 1:
          f[i][j] = max(f[i][j], f[i - 1][k] + diff)
      ans = max(ans, f[i][j])
  print(ans)

1769D3 —Игра в Девятку III

Первая версия задачи представляет собой игру с нулевой суммой и полной информацией. Позиция в игре задаётся множеством выложенных на стол карт и тем, чей сейчас ход (множество карт в руке каждого игрока вычисляется из этой информации однозначным образом). Все возможные позиции образуют ориентированный граф, где из каждой позиции проведены дуги во все позиции, в которые текущий игрок может перейти за один ход. Кроме того, если текущий игрок не может сделать ни одного хода, то из позиции есть ровно одна дуга — в позицию с тем же множеством выложенных карт и ходом другого игрока. Заметим, что в ситуации, когда у обоих игроков есть карты в руке, хотя бы один из них всегда может сделать ход, а также то, что число выложенных на стол карт постоянно увеличивается — значит, граф является ацикличным.

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

Определять выигрышность позиций можно либо в порядке обратной топологической сортировки графа, либо же лениво, при помощи рекурсии с запоминанием.

Осталось оценить размер графа. Заметим, что в каждой масти в любой момент времени либо не выложено ни одной карты, либо же выложенные карты образуют отрезок, который начинается с шестёрки, семёрки, восьмёрки или девятки, а заканчивается девяткой, десяткой, валетом, дамой, королём или тузом. Значит, в каждой масти есть 1 + 4 ⋅ 6 = 25 возможных множеств выложенных карт, а всего позиций тогда не более 254 ⋅ 2 = 781 250 — следовательно, наш граф не слишком велик, и можно позволить себе рассмотреть все его состояния.

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

Вместо одного бита — выигрышная позиция или проигрышная — будем теперь хранить целое число. Если текущий игрок выигрывает, то значение будет равняться числу карт в руке соперника в конце игры. Если же игрок проигрывает, то значение будет равняться числу карт в его руке в конце игры, но со знаком «минус». Тогда получится, что каждый игрок стремится к максимизации этого значения для себя.

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

Как теперь вычислить величину важности первого хода? Найдём результат игры r₁ в позиции, где карт на столе нет и ходит Алиса, и результат игры r₂ в позиции, где карт на столе нет и ходит Боб. Тогда величина важности первого хода равна |r₁ − (−r₂)| = |r₁ + r₂|.

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

Перейдём к третьей версии задачи. Найти 26 раскладов с разными величинами случайной стратегией довольно сложно. Заметим, что для случайных раскладов искомая величина обычно весьма мала. Как же найти расклад с большой величиной?

Обратим внимание на такой расклад: в двух мастях у Алисы есть все карты, кроме девятки, а в двух других мастях — наоборот, только девятка. Расклад симметричен, и ходить первым в таком раскладе крайне невыгодно — у того игрока, который ходит первым, в конце игры останется 15 карт в руке. Следовательно, величина важности первого хода для этого расклада равна 30.

Теперь вместо того, чтобы генерировать полностью случайные расклады, будем вносить небольшое число случайных изменений в расклад из предыдущего абзаца — например, менять одну-две-три случайные карты между начальными руками игроков. Таким образом можно найти расклады, в которых величина важности первого хода велика, но меньше 30.

В действительности существует 27 различных значений важности первого хода: все значения от 0 до 24, а также 26 и 30.