Словарь двух томов
Лингвист сравнивает язык первого и последнего томов «Войны и мира». Он выписал слова, которые встречаются в обоих томах, и упорядочил их дважды: по частоте в первом томе и по частоте в четвёртом (при равной частоте — по алфавиту). Если бы язык не изменился, списки совпали бы. Мерой расхождения он выбрал число пар слов, которые в двух списках стоят в разном порядке: в первом списке слово u выше слова v, а во втором — ниже. Помогите ему посчитать.
Два теста — настоящие частотные списки романа: первый том против четвёртого и первый против второго.
Вход
В первой строке n (1 ≤ n ≤ 200 000) — число слов. Во второй строке — n различных слов в порядке первого списка, в третьей — те же слова в порядке второго. Слова состоят из строчных русских или латинских букв, длина слова — до 20 букв.
Выход
Одно число — количество пар слов, порядок которых в двух списках различается.
Примеры
Пример 1
4 мир война князь пьер война мир пьер князь
2
Пример 2
5 a b c d e e d c b a
10
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Пронумеруйте слова по первому списку: первое слово — 0, второе — 1 и так далее. Перепишите второй список этими номерами. Что значит «пара стоит в разном порядке» для получившейся последовательности чисел?
2Подсказка 2
3Подсказка 3
При слиянии берём элемент из правой половины. С какими элементами левой половины он образует инверсию — и сколько их осталось?
4Идея
После перенумерации ответ — число инверсий в последовательности номеров второго списка. Каждая инверсия — пара, у которой оба элемента в левой половине, оба в правой или один слева, другой справа. Первые два вида посчитает рекурсия, а третий — само слияние. Когда из правой половины уходит элемент right[j], он меньше всех ещё не взятых элементов левой половины (иначе взяли бы их), а в исходной последовательности стоял правее каждого из них. Значит, он образует инверсию ровно с len(left) − i элементами, и каждую пару «через середину» мы посчитаем ровно один раз — в тот момент, когда меньший из двоих уходит в результат.
5Разбор
Словарь «слово → место в первом списке» строится за один проход. Дальше — обычная сортировка слиянием с одним добавленным счётчиком: при каждом взятии справа прибавляем число оставшихся слева. Сортировка заодно упорядочивает последовательность, но её результат нам не нужен — нужен только счётчик.
Ответ на настоящих данных: из 3145 слов, частых в обоих томах, по-разному упорядочены 1 295 773 пары — примерно четверть из почти пяти миллионов. В статистике эту величину переводят в коэффициент ранговой корреляции Кендалла: τ = 1 − 4D / (n(n − 1)), где D — число расходящихся пар. У первого и четвёртого томов τ ≈ 0,48: словари заметно похожи, но далеко не совпадают.
5+Решение
6Сложность
Перенумерация O(n) со словарём, сортировка слиянием со счётчиком O(n log n): для 200 000 слов — около трёх с половиной миллионов сравнений вместо двадцати миллиардов у перебора пар.
7Типичные ошибки
- Перебор пар. Верно, но на больших тестах — квадрат и превышение времени.
- 32-битный счётчик. Ответ доходит до n(n − 1)/2 ≈ 2·10¹⁰: в пятом тесте второй список — первый задом наперёд. В Python и Go (
intтам 64-битный) это не страшно, в C++ или Java нуженlong longилиlong. - Инверсии по алфавиту. Если считать инверсии второго списка, сравнивая сами слова, ответ получится про алфавитный порядок, а не про первый список. Сравнивать нужно места в первом списке.