CF 102407J - Убийственная математика

CF 102407J - \u0423\u0431\u0438\u0439\u0441\u0442\u0432\u0435\u043d\u043d\u0430\u044f \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0430

Rating: -
Tags: -
Solve time: 2m 50s
Verified: yes

Solution

Problem Understanding

На экране находятся два целых числа a и b, причём a <= b. За один ход можно выбрать одно из них и заменить выбранное число либо на округлённое вверх геометрическое среднее ceil(sqrt(a*b)), либо на округлённое вниз квадратичное среднее floor(sqrt((a²+b²)/2)). После каждого хода оба числа снова рассматриваются как обычная пара.

Нужно найти минимальное количество таких ходов, после которого числа станут одинаковыми. Если они уже равны, ответ равен нулю.

Главная структура задачи появляется из поведения обоих средних. Для a < b геометрическое среднее лежит строго между a и b, а квадратичное среднее тоже лежит между ними до округления. После округления квадратичное среднее иногда может совпасть с меньшим числом. Например, для (1, 2) оно равно floor(sqrt(5/2)) = 1. В таком случае замена меньшего числа на квадратичное среднее вообще ничего не меняет, и такой ход никогда не нужен в оптимальном решении.

Официальные ограничения дают 1 <= a <= b <= 2000. Это означает, что всего возможных неупорядоченных состояний (a, b) не больше примерно двух миллионов. Полный перебор всех последовательностей действий невозможен, поскольку на каждом уровне есть до четырёх вариантов. При максимальной разнице 1999 число последовательностей теоретически растёт как 4^1999. При этом квадрат от 2000 уже вполне небольшой для динамического программирования, поэтому задача явно допускает рассмотрение всех пар. Официальное ограничение по времени составляет 2 секунды, а памяти 512 МБ.

Есть несколько границ, на которых неаккуратное решение легко ошибается. Для входа 5 5 правильный ответ равен 0, потому что обезвреживание уже произошло. Решение, которое всегда делает хотя бы один переход, ошибётся.

Для входа 1 2 правильный ответ равен 1. Геометрическое среднее равно ceil(sqrt(2)) = 2, поэтому можно сразу получить (2, 2). Однако квадратичное среднее равно floor(sqrt(5/2)) = 1. Если без проверки считать этот переход уменьшающим разницу, получится самопереход (1, 2) -> (1, 2), который нельзя использовать как обычное состояние динамики.

Для входа 1 3 правильный ответ равен 2. Например, сначала геометрическим средним заменяем 1 на 2, получаем (2, 3), затем квадратичным средним заменяем 3 на 2, получаем (2, 2). Наивная формула, которая использует только один тип среднего, может получить неверный ответ.

Наконец, округление нельзя выполнять через неосторожные операции с вещественными числами. Нам нужны именно ceil(sqrt(x)) и floor(sqrt(y)). При ограничениях задачи можно работать с целыми корнями, используя isqrt, что полностью исключает погрешность округления.

Approaches

Самый прямой вариант состоит в переборе всех последовательностей ходов. Из состояния (a, b) можно получить до четырёх новых состояний: заменить первое число геометрическим или квадратичным средним, либо заменить второе число одним из этих средних. Можно запускать BFS, поскольку каждый ход имеет стоимость один, и первый раз, когда мы достигнем (x, x), получим оптимальный ответ.

Такой BFS уже гораздо лучше полного перебора последовательностей, потому что одинаковые состояния можно объединять. Однако если рассматривать его как общий граф поиска без использования специального свойства переходов, верхняя граница всё равно составляет около двух миллионов состояний и до восьми миллионов переходов. Это уже допустимо на C++, что подтверждается принятыми решениями с такими порядками памяти и времени, но для Python лучше использовать более сильную структуру задачи. В частности, в архиве есть принятые реализации C++ с десятками мегабайт памяти и временем порядка 46 мс.

Ключевое наблюдение состоит в том, что нам вообще не нужен общий поиск кратчайшего пути. Рассмотрим разницу d = b - a. Если a < b, любое полезное изменение одного из чисел перемещает его внутрь отрезка [a, b]. Значит, после полезного хода новая разница строго меньше старой. Единственное исключение, когда квадратичное среднее после округления совпадает с выбранным меньшим числом, даёт самопереход и не может улучшить ответ.

Получается ациклический граф состояний. Все переходы из (a, b) ведут к состояниям с меньшей разницей. Значит, можно посчитать dp[a][b] по возрастанию b - a. Когда мы вычисляем состояние с разницей d, ответы всех его полезных соседей уже готовы.

Для состояния (a, b) обозначим

g = ceil(sqrt(a*b))

q = floor(sqrt((a²+b²)/2)).

Тогда возможны состояния (g, b), (q, b), (a, g) и (a, q), если соответствующая замена действительно меняет пару. Поэтому

dp[a][b] = 1 + min(dp[g][b], dp[q][b], dp[a][g], dp[a][q])

с исключением самопереходов. Для a = b значение равно 0.

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

Approach	Time Complexity	Space Complexity	Verdict
Перебор последовательностей	`O(4^N)` в худшем случае	`O(N)` для глубины	Too slow
BFS по всем состояниям	`O(N²)`	`O(N²)`	Accepted на C++, но лишняя работа
DP по разнице	`O(N²)`	`O(N²)`	Accepted

Здесь N = 2000. Для Python плотное хранение dp в массиве 16-битных беззнаковых чисел позволяет уложиться в память с большим запасом.

Algorithm Walkthrough

Создадим таблицу dp, где dp[a, b] означает минимальное число ходов из состояния с числами a и b, предполагая a <= b. Для всех состояний (x, x) сразу положим dp[x, x] = 0, потому что они уже являются конечными.
Будем рассматривать пары в порядке возрастания разницы d = b - a. Сначала обрабатываются пары с разницей 1, затем с разницей 2, и так далее до 1999.

Это правильный порядок, потому что любой полезный переход из пары с разными числами уменьшает разницу. Значит, когда мы считаем dp[a][b], ответы всех возможных следующих состояний уже вычислены. 3. Для текущих a и b вычислим геометрическое среднее с округлением вверх. Сначала берём r = isqrt(a*b). Если r² < a*b, увеличиваем r на один. Получаем точное значение g = ceil(sqrt(a*b)). 4. Вычислим квадратичное среднее с округлением вниз как

q = isqrt((a² + b²) // 2).

Здесь целочисленное деление внутри isqrt безопасно. Для целого S выполняется floor(sqrt(S / 2)) = floor(sqrt(floor(S / 2))). 5. Рассмотрим четыре возможных изменения. Если заменить a на g, получим (g, b). Если заменить b на g, получим (a, g). Аналогично, квадратичное среднее даёт (q, b) и (a, q).

Переход, который не меняет пару, пропускаем. Например, для (1, 2) имеем q = 1, и замена первого числа на q оставляет (1, 2) без изменений. 6. Среди всех полезных переходов возьмём минимальное значение dp следующего состояния и прибавим один ход. Это и есть dp[a][b]. 7. После обработки всех разностей ответом будет dp[a][b] для исходной пары.

Why it works

Инвариант алгоритма состоит в том, что перед вычислением dp[a][b] значения всех состояний, достижимых одним полезным ходом из (a, b), уже известны. Для a < b оба математических средних не выходят за пределы [a, b]. Геометрическое среднее после округления вверх строго больше a и строго меньше b, если числа различны. Квадратичное среднее после округления вниз может совпасть с a, но тогда замена меньшего числа является самопереходом и не может входить в оптимальный путь. Все остальные переходы уменьшают b-a.

Следовательно, любой оптимальный путь из (a, b) сначала делает один из рассматриваемых переходов, а затем продолжает оптимально из соответствующего меньшего состояния. Формула динамики перебирает все такие первые ходы и выбирает лучший. Базовый случай a=b имеет ответ 0, поэтому индукция по разнице доказывает правильность всех значений dp.

Python Solution

import sys
from math import isqrt
from array import array

input = sys.stdin.readline

MAX_N = 2000
SIZE = MAX_N + 1
INF = 65535

def solve(a, b):
    # dp[x * SIZE + y] stores the answer for (x, y).
    # uint16 is enough because the difference is at most 1999.
    dp = array('H', [0]) * (SIZE * SIZE)

    for diff in range(1, SIZE):
        for x in range(1, SIZE - diff):
            y = x + diff
            base = x * SIZE + y

            product = x * y
            g = isqrt(product)
            if g * g < product:
                g += 1

            q = isqrt((x * x + y * y) // 2)

            best = INF

            # Replace x by the geometric mean.
            if g != x:
                best = min(best, dp[g * SIZE + y] + 1)

            # Replace y by the geometric mean.
            if g != y:
                best = min(best, dp[x * SIZE + g] + 1)

            # Replace x by the quadratic mean.
            if q != x:
                best = min(best, dp[q * SIZE + y] + 1)

            # Replace y by the quadratic mean.
            if q != y:
                best = min(best, dp[x * SIZE + q] + 1)

            dp[base] = best

    return dp[a * SIZE + b]

def main():
    a, b = map(int, input().split())
    print(solve(a, b))

if __name__ == "__main__":
    main()

В таблице используется один плоский массив вместо списка списков. Состояние (x, y) хранится по индексу x * SIZE + y. Это немного ускоряет обращения и особенно заметно уменьшает память, поскольку array('H') использует ровно 2 байта на значение. Максимальный ответ не превышает 1999, так что 16 бит более чем достаточно.

Цикл по diff начинается с единицы. Все состояния с нулевой разницей уже имеют значение 0, поскольку их числа равны. Внутренний цикл перебирает все x, для которых y = x + diff не превышает 2000.

Для геометрического среднего нельзя просто взять isqrt(product) и использовать его как ответ, потому что требуется округление вверх. Проверка g * g < product исправляет именно этот случай. Если произведение является точным квадратом, корень не увеличивается.

Для квадратичного среднего используется (x*x + y*y) // 2 перед isqrt. Все числа здесь очень малы: даже при x = y = 2000 сумма квадратов равна 8 000 000, поэтому переполнения в Python нет вообще. В C++ для таких ограничений также достаточно обычного 32-битного целого, хотя использование 64-битного типа остаётся хорошей привычкой.

Проверки g != x, g != y, q != x и q != y нужны именно для исключения операций, которые оставляют состояние неизменным. Самый показательный пример, (1, 2), где квадратичное среднее равно 1. При этом переход 2 -> 1 совершенно корректен и даёт (1, 1), поэтому проверять нужно не только само значение среднего, а то, какое число заменяется.

Worked Examples

Sample 1

Для входа 2 4 рассмотрим состояния в порядке увеличения разницы.

State	Difference	`g`	`q`	Best next state	`dp`
`(3, 3)`	`0`			already equal	`0`
`(2, 3)`	`1`	`3`	`2`	`(3, 3)`	`1`
`(3, 4)`	`1`	`4`	`3`	`(3, 3)`	`1`
`(2, 4)`	`2`	`3`	`3`	`(2, 3)` or `(3, 4)`	`2`

Для (2, 4) оба средних после округления дают 3. Если заменить 2, получится (3, 4), а если заменить 4, получится (2, 3). Оба этих состояния требуют ещё одного хода. Значит, исходное состояние требует двух ходов.

Получается путь (2, 4) -> (3, 4) -> (3, 3), что совпадает с минимальным ответом 2.

Sample 2

Для входа 12 16 сначала появляются состояния с меньшей разницей. Особенно полезна цепочка, проходящая через (14, 16).

State	Difference	`g`	`q`	Best next state	`dp`
`(14, 14)`	`0`			already equal	`0`
`(14, 15)`	`1`	`15`	`14`	`(15, 15)`	`1`
`(15, 16)`	`1`	`16`	`15`	`(16, 16)`	`1`
`(14, 16)`	`2`	`15`	`15`	`(15, 16)`	`2`
`(12, 16)`	`4`	`14`	`14`	`(14, 16)`	`3`

Для (12, 16) оба разрешённых среднего дают 14. Если заменить 12, получим (14, 16), для которого ответ равен 2. Если заменить 16, получим (12, 14), которое также требует трёх ходов от исходного состояния после добавления первого действия. В результате dp[12][16] = 3.

Один оптимальный путь имеет вид (12, 16) -> (14, 16) -> (15, 16) -> (16, 16). Другой путь может проходить через (12, 14). Таблица показывает главный инвариант: каждое вычисленное состояние опирается только на уже обработанные состояния с меньшей разницей.

Complexity Analysis

Measure	Complexity	Explanation
Time	`O(N²)`	Рассматривается `O(N²)` пар, для каждой вычисляются два целых квадратных корня и до четырёх переходов
Space	`O(N²)`	Таблица содержит `(N+1)²` значений `dp`

При N = 2000 это около двух миллионов состояний и около восьми миллионов потенциальных переходов. Плотное хранение dp занимает примерно 8 МБ, а все промежуточные арифметические значения для Python являются небольшими целыми числами. Такой порядок работы соответствует квадратному ограничению по максимальному числу 2000, в отличие от экспоненциального перебора последовательностей. Официальный лимит памяти составляет 512 МБ.

Test Cases

import sys
import io
from math import isqrt
from array import array

MAX_N = 2000
SIZE = MAX_N + 1
INF = 65535

def solve(a, b):
    dp = array('H', [0]) * (SIZE * SIZE)

    for diff in range(1, SIZE):
        for x in range(1, SIZE - diff):
            y = x + diff

            product = x * y
            g = isqrt(product)
            if g * g < product:
                g += 1

            q = isqrt((x * x + y * y) // 2)

            best = INF

            if g != x:
                best = min(best, dp[g * SIZE + y] + 1)

            if g != y:
                best = min(best, dp[x * SIZE + g] + 1)

            if q != x:
                best = min(best, dp[q * SIZE + y] + 1)

            if q != y:
                best = min(best, dp[x * SIZE + q] + 1)

            dp[x * SIZE + y] = best

    return dp[a * SIZE + b]

def run(inp: str) -> str:
    old_stdin = sys.stdin
    try:
        sys.stdin = io.StringIO(inp)
        a, b = map(int, sys.stdin.readline().split())
        return str(solve(a, b)) + "\n"
    finally:
        sys.stdin = old_stdin

# Provided samples
assert run("2 4\n") == "2\n", "sample 1"
assert run("12 16\n") == "3\n", "sample 2"

# Minimum-size and already equal
assert run("1 1\n") == "0\n", "minimum equal pair"

# Quadratic mean can equal the smaller value,
# while the geometric mean immediately solves the state.
assert run("1 2\n") == "1\n", "quadratic self-transition"

# Requires two different operations.
assert run("1 3\n") == "2\n", "small boundary case"

# The two values are adjacent near the maximum bound.
assert run("1999 2000\n") == "1\n", "maximum boundary"

# Maximum allowed equal value.
assert run("2000 2000\n") == "0\n", "maximum equal pair"

Test input	Expected output	What it validates
`1 1`	`0`	Минимальные значения и уже достигнутое равенство
`1 2`	`1`	Случай, когда квадратичное среднее совпадает с меньшим числом
`1 3`	`2`	Минимальная цепочка из двух разных состояний
`1999 2000`	`1`	Граница максимальных значений и округление геометрического среднего
`2000 2000`	`0`	Максимальная пара, уже находящаяся в конечном состоянии

Edge Cases

Для (5, 5) алгоритм вообще не входит в цикл динамики для положительной разницы. Элемент dp[5 * SIZE + 5] изначально равен 0, поскольку равные пары являются базовыми состояниями. Ответ для входа 5 5 равен 0. Это защищает от ошибки, при которой программа сначала выполняет бессмысленный ход, хотя условие уже выполнено.

Для (1, 2) геометрическое среднее равно ceil(sqrt(2)) = 2, а квадратичное среднее равно floor(sqrt(5/2)) = 1. При обработке пары (1, 2) алгоритм рассматривает замену первого числа на 1 как самопереход и игнорирует её. Замена второго числа на 1 при этом остаётся допустимой и даёт (1, 1). Ещё один вариант, замена первого числа на 2, даёт (2, 2). Поэтому dp[1][2] = 1.

Для (1, 3) геометрическое среднее равно 2, а квадратичное среднее равно 2, поэтому после первого полезного хода можно получить (2, 3) или (1, 2). Оба состояния имеют ответ 1, поскольку из (2, 3) геометрическое среднее даёт 3, а из (1, 2) геометрическое среднее даёт 2. Значит, dp[1][3] = 2.

Для (1999, 2000) геометрическое среднее с округлением вверх равно 2000, поскольку sqrt(1999 * 2000) меньше 2000 и больше 1999. Замена меньшего числа сразу даёт (2000, 2000), поэтому ответ равен 1. Этот случай одновременно проверяет верхнюю границу входа и правильность именно потолочного округления.

Для (2000, 2000) разность равна нулю, поэтому никаких вычислений средних не требуется. Таблица уже содержит ответ 0, и алгоритм возвращает его напрямую. Это показывает, почему базовые состояния должны быть определены до обработки пар с положительной разницей.