355A - Вася и цифровой корень

Если d = 0, то существует всего одно число, что , поэтому, если k = 1, то ответ — 0, иначе — No solution.

Если d > 0, то подоходящим числом, к примеру, являтся d × 10^k - 1.

Асимптотика решения: O(1) + O(k) на вывод решения.

355B - Вася и общественный транспорт

Если мы купим билет четвертого типа, то больше ничего покупать не надо, по-этому ответ — min(c₄, ответ из билетов первых трех типов).

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

Решая задачу только для автобусов, если мы купим билет третьего типа, то больше покупать ничего не надо, по-этому ответ равен min(c₃, ответ из билетов первых двух типов).

Без билетов третьего типа можно решать задачу независимо для каждого автобуса. Таким образом, если мы купим билет второго типа, то потратим c₂ бурлей, если же купим a_i билетов первого типа, то потратим (a_i × c₁) бурлей. Таким образом, ответ для автобуса i — min(c₂, a_i × c₁).

Собрав все вместе несложно получить следующее решение:

  function f(x, k) {
    res = 0;
    for i = 1 .. k
      res = res + min(c2, x[i] * c1);

    return min(c3, res);
  }

  ans = min(c4, f(a, n) + f(b, m));

Асимптотика решения: O(n + m).

354A - Вася и робот

Переберем, сколько раз мы будем использовать операцию слева. Путь мы используем ее k раз, тогда понятно, что операциями слева мы заберем k первых предметов, а оставшиеся (n - k) предметов заберем справа. Тогда робот затратит sumLeft[k]·l + sumRight[n - k]·r энергии плюс некоторый штраф за одинаковые операции. Чтобы минимизировать этот штраф операции необходимо выполнять в порядке LRLRL ... RLRLLLLL ..., начиная с тех операций, которых больше. К примеру, если k = 7, n - k = 4, то выполнять операции надо в последовательности LRLRLRLRL LL. Таким образом нам надо будет заплатить штраф два раза (7 - 4 - 1).

sumLeft[i] — сумма первых i весов, sumRight[i] — сумма последних i весов.

Псевдокод решения:

  ans = inf;
  for i = 0 .. n {
    curr = firstSum[i] * l + lastSum[n-i] * r;
    if ( i > n - i ) curr = curr + (2i - n - 1) * Ql;
    if ( i < n - i ) curr = curr + (n - 2i - 1) * Qr;

    ans = min(ans, curr);
  }

Асимптотика решения: O(n).

354B - Игра со строками

Будем говорить, что клетка (r, c) соответствует строке s, если существует корректный путь, заканчивающийся в клетке (r, c), которому соответствует строка s.

Найдем для строки s множество соответствующий ей клеток, назовем это множество состоянием. Одно состояние может соответствовать множеству разных строк. Перебрать все возможные строки мы не можем, так как их количество — слишком большое, однако перебрать все состояния мы можем. Несложно понять, что все клетки соответствующие одной строке находятся на одной диагонали, таким образом количество различных состояний равно 2¹ + 2² + ... + 2^n - 1 + 2ⁿ + 2^n - 1 + ... + 2² + 2¹ = O(2ⁿ). В реализации состояние можно охарактеризовать номером диагонали (от 1 до 2n - 1) и битовой маской клеток, которые в него входят (2ⁿ).

Из каждого состояния мы можем перейти в 26 различных состояний (на самом деле меньше), причем все возможные переходы зависят именно от состояния, а не от самой строки. На изображении — пример перехода: из состояния, которое выделено синем цветом по букве a мы перейдем в состояние, выделенное желтым цветом.

Теперь, подсчитаем для каждого состояния величину (кол-во букв A  -  кол-во букв B) в строке, начиная с этого состояния. Если в данный момент ходит первый игрок (на четной диагонали), то это значение надо максимизировать, если второй (на нечетной диагонали) — минимизировать. Реализовать это несложно в виде рекурсии с мемоизацией.

Победителя можно определить по значению состояния, соответствующему клетке (1, 1).

Асимптотика: O(2ⁿ × (n + alpha)), где alpha — размер алфавита.

354C - Вася и красивые массивы

В задаче было необходимо найти максимальное d, такое, что a_i ≥ d,  a_i mod d ≤ k.

Пусть m = min(a_i), из условия следует, что d ≤ m. Рассмотрим два случая:

. В данном случае переберем ответ от k + 1 до m, проверить, подходит ли число d в качестве ответа можно следующим образом:

Нам необходимо проверить, что a_i mod d ≤ k при фиксированном d, что равносильно , где . Так как все упомянутые интервалы [x·d..x·d + k] не пересекаются, то достаточно проверить, что , где cnt[l..r] — количество чисел a_i в интервале [l..r].

Итоговая асимптотика решения: O(maxA log maxA), доказательство основывается на сумме гармонического ряда.

354D - Передача пирамиды

Данная задача решается динамическим программированием. Рассмотрим для начала решение за O(n³).

Пусть dp[i][j] — ответ для выделенной синим цветом на изображении части (минимальная стоимость передачи всех ячеек, которые находятся в синей области). Тогда в dp[n][0] будет содержатся ответ на задачу.

Как пересчитывать такую динамику? Понятно, что в самом левом столбце (внутри синей части) мы выберем в качестве вершины подпирамиды максимум одну ячейку. Если мы выберем две, то одна из данных подпирамид будет полностью содержать другую внутри (как синяя подпирамида содержит оранжевую). Теперь, переберем за O(n) ту клеточку, которая будет вершиной подпирамиды и получим следующий переход:

Для упрощения формул будем считать, что .

0 ≤ k ≤ i, где k — высота, на которой мы выберем вершину или 0, если в данном столбце не будет выбрана подпирамида, а sumUp[i][p] — количество помеченных клеточек в i-том столбце, на высоте начиная с p, их нам придется передавать по одной операциями первого типа.

Можно сократить одну степень, пересчитывая динамику так:

0 ≤ k ≤ i;

для всех j > 0.

Доказательство того, что это корректно довольно просто и оставляется читателю. :)

Также можно заметить, что нам не выгодно брать подпирамиду с высотой больше, чем , так как за нее мы заплатим  > 3k, однако, если передавать все клеточки по одной мы заплатим всего 3k. Таким образом второе измерение (j) в динамике можно сократить до .

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

Асимптотика решения: .

354E - Счастливое представление числа

Авторское решение, намного сложнее предложенного участниками во время контеста:

Для начала напишем ДП за O(N * lucky_count(N)), где lucky_count(N) — количество счастливых чисел до N, lucky_count(10ⁿ) = 3ⁿ. Видно, что для всех достаточно больших N решение существует. На самом деле для всех N > 523.

Теперь, скажем для чисел  ≤ 10000 у нас есть решение, найденное ДПой. Решим задачу для больших чисел:

Следующая и ключевая идея — разделить задачу на две части. N = N1 + N2. Выберем N1 и N2 так, чтобы для них можно было легко найти ответ, а также, найдя 2 решения, было возможно их объеденить в одно. Пусть N1 = N mod 4000, N2 = N - N1. Однако, тут может появиться проблемма с тем, что для N1 нет решения, тогда сделаем N1 = N1 + 4000, N2 = N2 - 4000.

Теперь решение гарантированно существует и для N1 и для N2, причем в решении для числа N1 мы будем использовать только числа из не более, чем 3 цифр ( < 1000). Доказательство довольно просто: если N1 < 4000 — то очевидно; иначе — если в решении используется число вида (4000 + some_lucky_number), то заменим его на просто some_lucky_number и получим решение для (N1 - 4000), однако его не существует!

Решение для N1 мы нашли при помощи ДП, теперь нам нужно найти решение для N2. Если оно будет использовать только числа вида (some_lucky_number × 1000), то мы сможем легко объеденить его с решением для N1, по-этому будем искать именно такое решение. Тут мы будем использовать тот факт, что N2 делится на 4. Для простоты поделим N2 на 1000, а в конце просто умножим все Ans2(i) на ту же 1000. Пусть P = N2 / 4. Теперь будем конструктивно строить решение. Рассмотрим, к пример, P = 95: идем по цифрам этого числа, последняя цифра — 5, означает, что мы хотим в пяти числах ответа на последнюю позицию (в десятичной записи) поставить цифру 4, хорошо — ставим и в последнем, шестом, числе оставляем на последней позиции 0. Идем дальше, цифра 9 — у нас нету девяти чисел, но мы можем семь четверок заменить на четыре семерки, тогда нам на вторые позиции надо поставить (9 - 7) четверок и 4 семерки, в сумме в 6 чисел, как раз то, что надо.

Таким образом, если очередная цифра d ≤ 6, то просто в первые d чисел ответа ставим цифру 4 на очередную позицию, если же d > 6, то в 4 числа ставим цифру 7 и в d - 7 чисел ставим цифру 4. Во всех остальных числах оставляем на данной позиции 0.

Если Ans1(i) — ответ для числа N1, Ans2(i) — для числа N2, то ответом для числа N будет просто Ans(i) = Ans1(i) + Ans2(i).

Асимптотика решения на одно число: O(logN).

Во время контеста многие участники сдали следующее решение:

dp[i][j] — можем ли мы расставив цифры на последние i позиций чисел ответа так, чтобы получить верные последние i цифр в сумме и перенос на следующий разряд был равен j. Тогда решение существует, если dp[19][0] = true, чтобы восстановить ответ просто для каждого состояния запоминаем, из какого состояния мы в него пришли. База — dp[0][0] = true. Переход — перебераем, сколько мы поставим четверок и сколько семерок в i-тый разряд.