Однажды Артёму заблокировали канал на одном из видеохостингов. «Ну заблокировали и заблокировали», — подумал он и решил перезалить свои видеоролики на другие видеохостинги. Артём решил подойти к этому процессу с исследовательской точки зрения, чтобы выяснить, какой видеохостинг лучше. Для начала Артём решил, что каждый видеоролик он загрузит ровно на один видеохостинг, чтобы у его зрителей была мотивация подписываться на все видеохостинги. Ведь, если на какой-то видеохостинг подпишется сильно больше или меньше зрителей, то это может исказить статистику просмотров. Далее Артём решил, что минимальное и максимальное число загруженных им видеороликов на каждый видеохостинг должны отличаться как можно меньше. Ведь, если на если на какой-то видеохостинг будет загружено сильно больше или меньше видеороликов, то это также может исказить статистику просмотров. Артём уже собрался загружать видеоролики на видеохостинги, но заметил, что каждый видеоролик можно отнести ровно к одной теме. Разные темы могут быть интересны разным зрителям. Поэтому Артём решил, что для ещё большей равномерности нужно загрузить видеоролики так, чтобы для каждой тематики минимальное и максимальное число загруженных видеороликов этой темы на каждом видеохостинге также отличалось как можно меньше. Артём понял, что он слишком переусложнил себе задачу и без вашей помощи ему теперь не справиться. Максимум баллов за задачу - 100. Формат входных данных Первая строка содержит три натуральных числа N , M , K ( 1 ≤ N ≤ 10 5 , 1 ≤ M , K ≤ N ) — число видеороликов, тем и видеохостингов. Все они пронумерованы с единицы. Вторая строка содержит N натуральных чисел t i ( 1 ≤ t i ≤ M ) — тема i -го видеоролика. Формат выходных данных Выведите K строк. Каждая строка x должна начинаться с целого числа S — числа видеороликов, загруженных на видеохостинг с номером x . Далее идут S целых чисел — номера соответствующих видеороликов. Пример 1 Входные данные 10 4 3 1 2 2 3 3 3 4 4 4 4 Выходные данные 4 1 4 7 10 3 2 5 8 3 3 6 9
Краткий ответ: нужно объединить видеоролики каждой темы в отдельную группу и раздавать их видеохостингам по кругу, не сбрасывая указатель между темами.
Алгоритм
- Сохраним номера видеороликов для каждой темы.
- Заведём указатель
curна текущий видеохостинг. - Для каждой темы по очереди:
- берём все её видеоролики;
- отправляем их на хостинги
cur, cur + 1, cur + 2, ...по модулюK; - после каждого ролика сдвигаем
cur.
- Выводим списки роликов для каждого хостинга.
Важно: указатель cur не нужно сбрасывать после обработки темы.
Почему распределение оптимально
Пусть у некоторой темы c видеороликов.
При распределении по кругу каждый видеохостинг получит либо
\[ \left\lfloor \frac{c}{K} \right\rfloor, \]
либо
\[ \left\lceil \frac{c}{K} \right\rceil \]
роликов этой темы. Поэтому разница между максимальным и минимальным количеством равна:
- \(0\), если \(c\) делится на \(K\);
- \(1\), иначе.
Меньшую разницу получить невозможно: если число роликов не делится на число хостингов, одинаковое распределение невозможно.
Все темы обрабатываются подряд, а указатель продолжает двигаться по кругу. Значит, и для всех \(N\) роликов вместе распределение такое же:
\[ \left\lfloor \frac{N}{K} \right\rfloor \quad\text{или}\quad \left\lceil \frac{N}{K} \right\rceil \]
роликов на каждый хостинг. Следовательно, глобальное распределение также оптимально.
Пример
Для примера распределение идёт так:
- тема 1: ролик 1 → хостинг 1;
- тема 2: ролики 2, 3 → хостинги 2, 3;
- тема 3: ролики 4, 5, 6 → хостинги 1, 2, 3;
- тема 4: ролики 7, 8, 9, 10 → хостинги 1, 2, 3, 1.
Получаются строки из примера.
Реализация на C++17
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M, K;
cin >> N >> M >> K;
vector<vector<int>> byTopic(M + 1);
for (int i = 1; i <= N; ++i) {
int t;
cin >> t;
byTopic[t].push_back(i);
}
vector<vector<int>> hosting(K);
int cur = 0; // текущий хостинг, нумерация с нуля
for (int topic = 1; topic <= M; ++topic) {
for (int video : byTopic[topic]) {
hosting[cur].push_back(video);
cur = (cur + 1) % K;
}
}
for (int host = 0; host < K; ++host) {
cout << hosting[host].size();
for (int video : hosting[host]) {
cout << ' ' << video;
}
cout << '\n';
}
return 0;
}
Сложность алгоритма:
\[ O(N+M+K), \]
поскольку каждый видеоролик обрабатывается ровно один раз.
Обсуждение
3 сообщенияВиктор работает в сервисе по ремонту клавиатур. Чаще всего ремонт заключается в переключении тумблера с положения OFF в ON, из-за этого Виктор уже заскучал. Но однажды ему принесли сломанную клавиатуру с неизвестной раскладкой. Виктор подключил клавиатуру к компьютеру и зашёл в текстовый редактор. Он стал нажимать различные клавиши из-за чего на экране в текстовом редакторе стали печататься неизвестные символы. Тогда Виктор использовал специальный анализатор, который напрямую считывает код нажатой клавиши, а также произвольно пронумеровал клавиши самой клавиатуры. Виктор решил, что хоть он и не знает правильной нумерации, всё равно можно оценить работоспособность клавиатуры. Для этого Виктор придумал численный коэффициент работоспособности клавиатуры. Для вычисления этого коэффициента Виктор нажимает произвольные клавиши на клавиатуре и записывает соответствующие полученные коды от анализатора. Так как правильное сопоставление неизвестно, то сравнивать номера и коды клавиш напрямую нельзя, поэтому Виктор решил анализировать нажатия попарно. Хорошей парой нажатий Виктор называет такую пару ( ( k i , c i ) i , ( k j , c j ) j ) , в которой совпадают и номера k i = k j , и коды c i = c j клавиш. Почти хорошая пара нажатий — пара ( ( k i , c i ) i , ( k j , c j ) j ) , в которой не совпадают и номера k i ≠ k j , и коды c i ≠ c j клавиш. Плохая пара нажатий — пара ( ( k i , c i ) i , ( k j , c j ) j ) , в которой совпадают номера k i = k j , но не совпадают коды c i ≠ c j клавиш. Почти плохая пара нажатий — пара ( ( k i , c i ) i , ( k j , c j ) j ) , в которой не совпадают номера k i ≠ k j , но совпадают коды c i = c j клавиш. Пусть G — число хороших пар нажатий клавиш, P — число почти хороших пар, B — число плохих пар, а N — число почти плохих пар. Тогда коэффициент работоспособности клавиатуры равен: √ G + √ P √ B + √ N Если √ B + √ N = 0 , то клавиатура считается полностью рабочей, поэтому численное значение коэффициента не имеет смысл. Формат входных данных Первая строка содержит натуральное число N ( 2 ≤ N ≤ 10 5 ) — число нажатий. Вторая строка содержит N натуральных чисел k i ( 1 ≤ k i ≤ 10 9 ) — номера нажатых клавиш. Третья строка содержит N натуральных чисел c i ( 1 ≤ c i ≤ 10 9 ) — коды соответствующих клавиш. Формат выходных данных Выведите значение коэффициента работоспособности клавиатуры, либо -1, если клавиатура полностью рабочая. Ответ будет засчитан, если его абсолютная или относительная погрешность не будет превышать 10 − 9 .
Какой это алгоритм
Покажи пошаговую работу указателя на другом примере Представьте, что вы продаете товар на Авито - гитару, чемодан или настольную игру. Покупатель хочет знать, сколько будет стоить доставка, а маркетплейс должен посчитать это автоматически и точно. Ваша задача - научить модель по данным об объявлении (текст + характеристики + фото) предсказывать четыре величины: вес, высоту, ширину и длину товара. Чем точнее предсказания, тем корректнее стоимость доставки и тем меньше неприятных сюрпризов на пункте выдачи. Задание: Автоматический точный расчёт стоимости доставки для продавцов и покупателей Авито подразумевает, что необходимо заранее предсказывать индивидуальные весогабаритные характеристики (ВГХ) товара по его описанию и фото. Для этого постройте модель, которая для каждого объекта из тестовой выборки предсказывает четыре непрерывные величины: target_weight - вес (кг), target_height - высота (см), target_width - ширина (см), target_length - длина (см). Данные: train.parquet - обучающая выборка, test.parquet - тестовая выборка, sample_submission.csv - шаблон отправки, train.zip и test.zip - изображения товаров (ровно 1 фото на товар). Все данные можно скачать из Облака Тренировочный набор train.parquet с колонками: item_id - уникальный ID товара, order_date - дата оформления заказа, item_condition - состояние товара, item_price - цена, ₽, category_name, subcategory_name, microcat_name - иерархия категорий (ур. 1/2/3), seller_id, buyer_id - ID продавца/покупателя, title, description - заголовок и описание объявления, image_name - имя изображения, соответствует объекту в train.zip. Таргеты: real_weight (кг), real_height (см), real_width (см), real_length (см). Тестовая выборка: test.parquet - те же признаки, без таргетов. Метрика В качестве метрики качества используется Macro Log-MAE. Считаем MAE в лог-шкале по каждому таргету и усредняем: LogMAE t = 1 N ∑ N i = 1 ∣ ∣ log ( 1 + y i , t ) − log ( 1 + ^ y i , t ) ∣ ∣ , Score = 1 4 ∑ t ∈ { weight,height,length,width } LogMAE t , где y i , t - истинное значение, ^ y i , t - предсказание.
