Размер блока
Перед синхронизацией файла нужно выбрать размер блока B. Файл длиной n байт режется на блоки по B байт, последний блок может быть короче. За каждый блок платят s байт — столько весят его контрольные суммы. Кроме того, известно, какие байты файла изменились, и каждый блок, в котором есть хотя бы один изменённый байт, придётся передать целиком — столько байт, сколько в нём есть.
Итак, цена размера B — это s·(число блоков) плюс суммарная длина блоков с изменениями. Найдите размер B от 1 до n с наименьшей ценой; если таких несколько — наименьший. Три теста — места настоящих правок главы базового курса этого сайта: байты новой версии, которые вставлены или заменены.
Вход
В первой строке — длина файла n, цена сумм одного блока s и число изменённых байтов k (1 ≤ n ≤ 105, 1 ≤ s ≤ 1000, 0 ≤ k ≤ n). Во второй — k различных номеров изменённых байтов в порядке возрастания, от 0 до n − 1 (при k = 0 строка пустая).
Выход
Два числа: лучший размер блока и его цена.
В первом примере при B = 12 блоков два, это 8 байт сумм, и изменения есть только в первом блоке — ещё 12 байт, всего 20. При B = 4 изменённые байты 3, 4 и 11 портят три блока из пяти: 20 + 12 = 32. Во втором примере выгодно отрезать изменённый последний байт в отдельный короткий блок: при B = 9 цена 2·3 + 1 = 7.
Примеры
Пример 1
20 4 3 3 4 11
12 20
Пример 2
10 3 1 9
9 7
Ограничения
- Время · Python
- 8000 мс
- Время · Go
- 2000 мс
- Память
- 256 МБ
- Проверка
- 11 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
В статье лучший размер оценён формулой √(n·s/k). Почему здесь её не хватает, а перебрать все B от 1 до n кажется дорого: для каждого надо узнать, какие блоки испорчены. Сколько вообще блоков при размере B?
2Идея
Блоков ⌈n/B⌉, а испорченных — не больше, чем блоков. Если для каждого B перебирать только испорченные блоки, перепрыгивая от одного к следующему, работа по всем B составит не больше n/1 + n/2 + … + n/n = n·Hn ≈ n ln n шагов — гармонический ряд. Для прыжков нужен массив «следующий изменённый байт начиная с позиции x».
3Разбор
Заполним nxt[x] — номер первого изменённого байта не левее x, или n, если таких нет; это один проход справа налево. Для размера B начинаем с x = nxt[0]. Байт x лежит в блоке, который начинается в x − x mod B и кончается в min(n, начало + B). Добавляем длину этого блока к цене и прыгаем на nxt[конец] — к первому изменению после него. Цена — s·⌈n/B⌉ плюс сумма длин; среди всех B берём наименьшую цену, при равенстве — первый размер.
Почему не формула. Модель статьи считает, что каждая правка портит ровно один блок и все правки разбросаны. На деле правки идут кучками: на правке стиля (третий тест) изменилась тысяча с лишним байт в нескольких десятках мест, и лучший размер — 183 байта; на неразрывных пробелах (четвёртый тест) — 520. Формула верно указывает порядок величины, но точный ответ даёт только перебор. Крайние случаи тоже поучительны: если суммы дороги (восьмой тест), выгоднее один блок на весь файл; если изменился только последний байт (десятый), лучше отрезать его в короткий хвост.
3+Решение
4Сложность
O(n log n) времени: для каждого B — не больше min(k, ⌈n/B⌉) прыжков. O(n) памяти на массив прыжков.
5Типичные ошибки
- Последний блок — тоже B байт. Он короче, и передавать его дешевле. Второй пример это ловит.
- Пройти по всем изменённым байтам для каждого B. Это O(n·k): в седьмом тесте изменён каждый байт, и шагов получается десять миллиардов.
- Перебрать только B рядом с формулой. Ответ бывает далеко от неё — как в восьмом и десятом тестах.
Алгоритмы задачи
O(n + m): сумма окна сдвигается за O(1), сильная сумма — только при совпадении слабой
2 задачи
TEC
Приём
Префиксные суммы
Сумма любого отрезка за O(1) после одного прохода; двумерный вариант считает сумму любого прямоугольника картинки.
O(n) на построение, O(1) на запрос
2 задачи