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

Адреса по порядку

В журнале сервера записано n обращений — по адресу IPv4 на строку. Администратору нужна сводка: каждый адрес по одному разу, в порядке возрастания, и сколько раз он встретился в журнале. Возрастание — как у чисел: адрес a.b.c.d — это 32-битное число a·2²⁴ + b·2¹⁶ + c·2⁸ + d, поэтому 10.0.0.9 идёт раньше 10.0.0.10, а 20.1.1.1 — раньше 100.1.1.1.

Адреса в тестах придуманы: несколько оживлённых сетей, из которых приходят снова и снова, и длинный хвост случайных разовых посетителей.

Вход

В первой строке n (1 ≤ n ≤ 100 000). Дальше n строк, в каждой адрес IPv4: четыре числа от 0 до 255 через точку, без ведущих нулей.

Выход

В первой строке — сколько в журнале разных адресов. Дальше по строке на адрес, в порядке возрастания: адрес и через пробел — сколько раз он встретился.

Примеры

Пример 1

Вход

9
10.0.0.9
10.0.0.10
192.168.1.1
10.0.0.9
9.255.255.255
100.1.1.1
20.1.1.1
10.0.0.10
10.0.0.9

Выход

6
9.255.255.255 1
10.0.0.9 3
10.0.0.10 2
20.1.1.1 1
100.1.1.1 1
192.168.1.1 1

Пример 2

Вход

7
8.8.8.8
8.8.4.4
1.1.1.1
1.0.0.1
8.8.8.8
77.88.8.8
77.88.8.1

Выход

6
1.0.0.1 1
1.1.1.1 1
8.8.4.4 1
8.8.8.8 2
77.88.8.1 1
77.88.8.8 1

Ограничения

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

Разбор

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

1Подсказка 1

Посмотрите на первый пример: если отсортировать строки как текст, 10.0.0.10 окажется раньше 10.0.0.9 — символ «1» меньше символа «9». Адрес надо превратить в число.

2Подсказка 2

Адрес — это и есть четыре байта 32-битного числа. Отсортировать такие числа можно четырьмя проходами поразрядной сортировки, по байту за проход, от младшего к старшему. А одинаковые адреса после сортировки стоят подряд.

3Идея

Переводим каждый адрес в число a·2²⁴ + b·2¹⁶ + c·2⁸ + d — порядок чисел совпадает с нужным порядком адресов. Числа сортируем, равные идут подряд, и сводка собирается одним проходом: считаем длину каждой серии одинаковых чисел и печатаем адрес обратно в виде a.b.c.d.

4Разбор

Эталонные решения сортируют поразрядно: четыре устойчивых прохода, каждый раскладывает числа по 256 корзинам по очередному байту, начиная с младшего. Почему от младшего — в статье: последний проход по старшему байту сохраняет порядок, наведённый прошлыми проходами, среди чисел с одинаковым старшим байтом. Годится и встроенная сортировка с ключом-кортежем (a, b, c, d) или числом: кортежи сравниваются покомпонентно, как числа, и это тот же порядок.

Можно обойтись и без сортировки всех n адресов: сначала посчитать повторы словарём, а сортировать только разные адреса. Когда журнал состоит из нескольких оживлённых сетей, разных адресов в нём намного меньше, чем строк.

4+Решение

5Сложность

Поразрядная сортировка — четыре прохода по n числам и четыре раза по 256 корзин: O(n). Со встроенной сортировкой — O(n log n); при n = 100 000 разница на глаз не видна, но на миллиардах строк сетевых журналов поразрядная сортировка по байтам — обычный приём.

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

Сортировать строки. Текстовый порядок сравнивает символы, а не числа: 100.1.1.1 окажется раньше 20.1.1.1. Первый пример сделан ровно на этом.
Склеить цифры. Ключ «все цифры подряд» (10.0.0.9 → 10009) путает адреса: 1.0.0.10 и 10.0.0.1 дают одно и то же число 10010.
Начать поразрядную сортировку со старшего байта и делать полные проходы: после последнего прохода адреса будут упорядочены только по младшему байту.

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

SRT Алгоритм Сортировка подсчётом и поразрядная Без сравнений: посчитать ключи или разложить их по цифрам — O(n + k) и O(d·n) вместо n log n. O(n + k) и O(d·(n + b)) 2 задачи