Однажды Артёму заблокировали канал на одном из видеохостингов. «Ну заблокировали и заблокировали», — подумал он и решил перезалить свои видеоролики на другие видеохостинги. Артём…

Ниже предлагаю пошаговый алгоритм решения задачи и объяснение, как получить требуемое разбиение видео по hosting-площадкам с учетом двух критериев баланса: по количеству на каждом хосте и по распределению тем внутри каждого хоста.

Задача в сжатом виде:

• Есть N видеороликов, у каждого свой темы t_i (1..M).
• Нужно распределить все видео по K хостингам так, чтобы:
  • числа видео на хостингах различались минимально (идеально: на каждом хосте получалось бы либо floor(N/K), либо ceil(N/K) видео);
  • для каждой темы распределение по хостингам было как можно более равномерным (для каждой темы counts по хостингам различались минимально).

Алгоритм (практичный и реализуемый за O(N log K))

1. Подготовка целевого размера хостов

• Пусть base = N div K, extra = N mod K.
• Для хоста h (1 ≤ h ≤ K) задаём целевой размер: sizes[h] = base + (h ≤ extra ? 1 : 0).
• Остаток по каждому хосту rem[h] = sizes[h].
• Это гарантирует, что диапазон между максимально заполненным и минимально заполненным хостом не превышает 1.

2. Группировка видео по теме

• Создаём список видеороликов для каждой темы j = 1..M: videos_of_topic[j].
• Заполняем их по входящим данным t_i.

3. Распределение по темам с балансировкой

• Для каждой темы j от 1 до M:
  • Пусть vids = videos_of_topic[j], их количество c = |vids|.
  • Если c = 0, пропускаем тему.
  • Для этого Thema будем распределять её видеоролики по хостам таким образом, чтобы число видеороликов данной темы на каждом хосте было как можно ближе друг к другу, не превышая доступный остаток на хостах.
  • Вводим локальные счётчики для темы j: curCnt[h] — сколько видеороликов темы j уже назначено на хост h. Инициализируем их нулями.
  • Вводим минимальную кэш-очередь (min-heap) из хостов, у которых ещё есть место (rem[h] > 0). Элемент кучи для хоста h содержит пару (curCnt[h], h).
  • Для каждого видео из vids (в любом порядке, например, по их порядку в входе):
    • Достаём из кучи хост h с минимальным curCnt[h]. Чтобы выбрать корректного хоста, поддерживаем проверку валидности (в кучу могут попадать устаревшие пары).
    • Назначаем текущее видео на хост h: add video_id в список хостa h; уменьшаем rem[h]--, увеличиваем curCnt[h]++.
    • Если rem[h] > 0, заново кладём в кучу обновлённую пару (curCnt[h], h).
  • Таким образом, для данной темы распределение по хостам будет максимально сбалансированным с учётом текущей свободной ёмкости.

4. Проверка и выход

• После обработки всех тем у каждого хоста будет ровно sizes[h] видео, разница между максимумом и минимумом не более 1.
• Выводим K строк, для каждого хоста h сначала S = количество его видео, затем перечисляем номера этих видео.

Сложность

• Время: O(N log K) — каждое видео обслуживается операцией в минимальной куче по K элементам.
• Память: O(N) для хранения принадлежности видео к хостам и сами списки.

Псевдокод (практически готов к реализации)

• Вход: N, M, K

• t[1..N]

• groups[j] = пустой список для j = 1..M

• для i = 1..N: groups[t[i]].append(i)

• base = N div K, extra = N mod K

• sizes[h] = base + (h <= extra ? 1 : 0) для h = 1..K

• rem[h] = sizes[h]

• answer[h] = пустой список

• для j = 1..M: vids = groups[j] если vids пусто: продолжить curCnt[h] = 0 для всех h создание пустой min-heap H для h = 1..K: если rem[h] > 0: push (0, h) в H

  p = 0 while p < len(vids): пока H не пуст и (rem[H.top.h] == 0 или H.top.cnt != curCnt[H.top.h]): pop из H если H пуст: break (чаще не произойдёт) (cnt, h) = pop из H video_id = vids[p] answer[h].append(video_id) rem[h]-- curCnt[h]++ p++ если rem[h] > 0: push (curCnt[h], h) в H

• Вывод: для h = 1..K print len(answer[h]) и далее номера видео из answer[h] через пробел

Пояснения к примеру

• В примере N=10, K=3, M=4. base=3, extra=1 → sizes = [4,3,3].
• Алгоритм распределяет видео так, чтобы:
  • на хост 1 было 4 видео, на хостах 2 и 3 — по 3;
  • для каждой темы баланс по хостам близок к равному распределению;
  • итоговое распределение похоже на пример:: хост 1: видеоролики [1, 4, 7, 10] хост 2: [2, 5, 8] хост 3: [3, 6, 9] Это удовлетворяет условиям задачи: минимальная разница между количеством на хостах и сбалансированное распределение по темам.

Дополнительные варианты и примечания

• Точки зрения на разбиение могут немного различаться в зависимости от выбора порядка обработки тем и поведения кучи при равенстве ключей. Все такие варианты остаются корректными и удовлетворяют требования.
• Можно реализовать аналогично и без кучи, если у K небольшое значение, но для больших K предпочтительнее использовать кучу для эффективного выбора минимального curCnt[h] среди доступных хостов.

Если хочешь, могу привести готовый код на Python или C++, чтобы просто скопировать и запустить.