Задачник Базовый курс EN

Сколько строк поменялось

сравнение версий контроль версий кратчайший путь жадность

Система контроля версий хранит историю файла и для каждого коммита показывает, сколько строк удалено и сколько вставлено. Её автор хочет знать наименьшее возможное число: сколько строк минимум нужно удалить из старой версии и вставить в неё, чтобы получилась новая. Строку целиком можно только удалить или вставить; исправленная строка — это одно удаление и одна вставка.

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

Вход

В первой строке — числа N и M (0 ≤ N, M ≤ 100 000): сколько строк в старой и в новой версии. Дальше N строк старой версии и M строк новой, по порядку. Строки могут быть пустыми и содержать любые знаки, кроме перевода строки; две строки равны, если совпадают знак в знак. Ответ не больше 500.

Выход

Одно число — наименьшее суммарное число удалённых и вставленных строк.

Примеры

Пример 1

Вход

3 4
Мороз и солнце; день чудесный!
Еще ты дремлешь, друг прелестный —
Пора, красавица, проснись:
Мороз и солнце; день чудесный!
Ещё ты дремлешь, друг прелестный —
Пора, красавица, проснись:

Выход

Пример 2

Вход

7 6
A
B
C
A
B
B
A
C
B
A
B
A
C

Выход

Ограничения

Время · Python: 4000 мс
Время · Go: 1000 мс
Память: 256 МБ
Проверка: 11 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Если строки нельзя менять, а только удалять и вставлять, то ответ связан с наибольшей общей подпоследовательностью строк: что не вошло в неё, удаляется из одной версии или вставляется из другой. Но таблица N × M — это десять миллиардов клеток.

2Подсказка 2

Ответ не больше 500 — значит, путь в сетке правок почти всё время идёт по диагонали. Ищите не по клеткам, а по числу правок: сначала всё, куда можно дойти бесплатно, потом с одной правкой, с двумя…

3Подсказка 3

Все пути с d правками кончаются на диагоналях k = x − y от −d до d. На каждой достаточно помнить самую дальнюю точку.

4Идея

Алгоритм Майерса: для d = 0, 1, 2, … и каждой диагонали k от −d до d через два берём самую дальнюю точку — шаг вниз с диагонали k + 1 или вправо с k − 1, — и идём по диагонали, пока строки совпадают. Первое d, при котором точка дошла до (N, M), и есть ответ. Восстанавливать сам diff не нужно, поэтому хватает одного массива на 2(N + M) + 3 числа.

5Разбор

Строки сначала заменяем номерами: одинаковые строки — одинаковые номера. Сравнение чисел дешевле сравнения строк, а строки в тестах бывают длинными, как абзацы HTML в главе курса из пятого теста. Дальше — цикл из статьи о diff Майерса, только без сохранения волн.

Ответы на настоящих правках совпадают с тем, что показывает git: 86 строк в виджете курса о четвёртом измерении, 56 — в плане учебника математики, 6 — в главе о хешировании, 18 — в загрузке курсов валют.

5+Решение

6Сложность

O((N + M) · D) в худшем случае и порядка N + M + D² на тестах этой задачи: при D ≤ 500 вычислений на диагоналях около ста двадцати пяти тысяч, плюс змейки. Таблица — O(N · M) при любом ответе: на седьмом тесте это десять миллиардов клеток.

7Типичные ошибки

Таблица редакционного расстояния. Верна, но квадратична, и памяти даже на две строки таблицы хватит, а времени — нет.
Замена за единицу. По условию исправленная строка — это удаление и вставка, то есть две правки. Расстояние Левенштейна по строкам даст меньше.
Разбиение по пробелам. Строки могут быть пустыми и содержать пробелы: input().split() склеит и потеряет их. Читайте по переводам строк.
Пустые версии. N или M бывает нулём; тогда ответ — длина другой версии, и цикл должен это пережить.

Алгоритмы задачи

STR Алгоритм Diff Майерса Кратчайший сценарий удалений и вставок строк за O((N + M) · D): волны по числу правок. Так работает git diff. O((N + M) · D) 1 задача STR Алгоритм Редакционное расстояние Наименьшее число вставок, удалений и замен между двумя строками — таблица m × n и выравнивание по ней. O(m · n) 2 задачи DP Алгоритм Наибольшая общая подпоследовательность Самая длинная цепочка, общая двум последовательностям: таблица m × n, путь назад, Хиршберг. O(m · n) 2 задачи