Сортировки: музыкальный стриминг

Девять задач про сортировки на сюжете музыкального стриминга: от сортировки вставками до линейных сортировок. Решения сдаются на sort-me.org на GNU C++20, у каждой задачи свои баллы.

Генератор

В задачах D–F и I массив не подаётся на вход, а генерируется по параметрам. Общая часть кода (она уже есть в заготовках этих задач):

#include <cstdint>
 
// Состояние генератора псевдослучайных чисел из условия.
struct Generator {
  uint32_t a;
  uint32_t b;
  uint32_t cur;  // Начальное значение 0.
};
 
// 24-битное число: от 0 до 2^24 - 1. Вычисления идут с переполнением
// по модулю 2^32.
uint32_t Next24(Generator* generator) {
  generator->cur = generator->cur * generator->a + generator->b;
  return generator->cur >> 8;
}
 
// 32-битное число на основе двух 24-битных: от 0 до 2^32 - 1.
uint32_t Next32(Generator* generator) {
  uint32_t x = Next24(generator);
  uint32_t y = Next24(generator);
  return (x << 8) ^ y;
}

Задача D использует только Next24, остальные — Next32.

A. [3-5] Первые треки

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

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

Входные данные

• Первая строка: целое число $n$ ($1 \le n \le 100$), количество треков.
• Вторая строка: $n$ целых чисел от 1 до 100, количество лайков у каждого трека.

Выходные данные

Одно целое число: количество сравнений, произведённых сортировкой вставками.

Пример 1

5
2 2 1 1 2

7

Пример 2

1
3

0

Пример 3

8
8 8 7 1 1 2 8 2

20

Примечание. Сортировка вставками для каждого элемента ищет линейным поиском позицию, куда его вставить. Для первого примера:

Всего $0 + 1 + 2 + 3 + 1 = 7$ сравнений.

Заготовка

Ввод и вывод уже написаны, остаётся реализовать функцию.

#include <cstdint>
#include <iostream>
 
// Возвращает количество сравнений, которые сделает сортировка вставками.
int64_t CountComparisons(const int* likes, int n) {
  // TODO
  return 0;
}
 
int main() {
  int n;
  std::cin >> n;
  int* likes = new int[n];
  for (int i = 0; i < n; ++i) {
    std::cin >> likes[i];
  }
  std::cout << CountComparisons(likes, n) << "\n";
  delete[] likes;
  return 0;
}

B. Обвал чартов

После тихого старта ваш стриминг внезапно попал в рекомендации, и за ночь в систему прилетело 100 000 новых треков. Сервера шумят, как старый кулер в коворкинге, а маркетолог уже анонсировал: «Обновлённый чарт выйдет ровно в полдень».

Вместо чарта сейчас хаос из битов, каверов и латино-попа. Нужно реализовать быструю сортировку (QuickSort) и выдать обновлённый чарт, прежде чем пользователи решат, что система зависла: отсортировать треки по количеству прослушиваний.

Входные данные

• Первая строка: целое число $n$ ($1 \le n \le 100000$), количество треков.
• Вторая строка: $n$ целых чисел, по модулю не больше $10^9$, количество прослушиваний у каждого трека.

Выходные данные

$n$ чисел: количества прослушиваний, отсортированные в порядке неубывания.

Лимит памяти: 64 МБ.

Пример

10
1 8 2 1 4 7 3 2 3 6

1 1 2 2 3 3 4 6 7 8

Заготовка

Ввод и вывод уже написаны, остаётся реализовать функцию.

#include <iostream>
 
// Сортирует plays[left..right] по неубыванию быстрой сортировкой.
// Готовыми функциями сортировки пользоваться нельзя.
void QuickSort(int* plays, int left, int right) {
  // TODO
}
 
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
 
  int n;
  std::cin >> n;
  int* plays = new int[n];
  for (int i = 0; i < n; ++i) {
    std::cin >> plays[i];
  }
  QuickSort(plays, 0, n - 1);
  for (int i = 0; i < n; ++i) {
    std::cout << plays[i] << " ";
  }
  std::cout << "\n";
  delete[] plays;
  return 0;
}

C. Поп vs хип-хоп

Платформа взлетела и мгновенно погрузилась в жанровый хаос. Попсовики требуют по пять новых синглов в неделю, хип-хоп-фанаты штурмуют комментарии с «верните как было», а продакт пишет в чат: «Лента выглядит как случайная мешанина. Вчерашние хиты улетают в конец, а пустышки взлетают в топ. Нужен порядок. Срочно».

Аналитики оценивают треки по двум метрикам:

• популярность — сколько прослушиваний трек набирает прямо сейчас;
• стабильность — сколько дней он держится в топах без просадки.

Ленту нужно выстроить заново:

1. сначала идут самые непопулярные треки;
2. при одинаковой популярности — менее стабильные;
3. при полном совпадении показателей сохраняется исходный порядок.

Выведите номера треков в том порядке, в котором они окажутся после такой сортировки.

Входные данные

• Первая строка: целое число $n$ ($1 \le n \le 10^5$), количество треков.
• Далее $n$ строк по два целых числа $a_i$, $b_i$ ($1 \le a_i, b_i \le 10^9$): популярность и стабильность трека.

Выходные данные

$n$ чисел: номера треков в порядке после сортировки (нумерация с 1).

Пример

9
3 2
1 1
2 1
2 2
3 2
1 2
1 2
3 2
2 3

2 6 7 3 4 9 1 5 8

Заготовка

Ввод и вывод уже написаны, остаётся реализовать функцию.

#include <iostream>
 
struct Track {
  int popularity;
  int stability;
  int index;  // Номер трека, нумерация с 1.
};
 
// Упорядочивает треки: сначала менее популярные, затем менее стабильные.
// При полном совпадении показателей сохраняется исходный порядок.
void SortTracks(Track* tracks, int n) {
  // TODO
}
 
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
 
  int n;
  std::cin >> n;
  Track* tracks = new Track[n];
  for (int i = 0; i < n; ++i) {
    std::cin >> tracks[i].popularity >> tracks[i].stability;
    tracks[i].index = i + 1;
  }
  SortTracks(tracks, n);
  for (int i = 0; i < n; ++i) {
    std::cout << tracks[i].index << " ";
  }
  std::cout << "\n";
  delete[] tracks;
  return 0;
}

D. Хаос в плейлисте

Чарт собран (задача B), порядок «популярность → стабильность» наведён (задача C), и команда выкатила персональные плейлисты. Ожидание: взять готовый чарт за основу, аккуратно подмешать вкусы пользователя и получить плейлисты, которые все полюбят. Реальность: свежий хит идёт после архивного трека, лайтовый ло-фай вклинивается между двумя хитами, а любимый трек пользователя проваливается ниже случайного ремикса.

Прежде чем крутить ручки алгоритма, нужно понять, насколько всё испорчено. Для этого нужно вычислить индекс беспорядка, то есть количество инверсий в плейлисте.

Плейлист — массив целых чисел $a$ (ключей ранжирования треков) в порядке проигрывания. Инверсия — пара индексов $(i, j)$, $i < j$, для которой $a[i] > a[j]$.

Входные данные

• Первая строка: $n$ и $m$, где $1 \le n \le 10^6$, $1 \le m \le 2^{24}$.
• Вторая строка: $a$ и $b$, где $1 \le a, b \le 10^9$.

Массив не подаётся напрямую, он генерируется на лету по параметрам $n, m, a, b$ (в заготовке ниже это уже сделано).

Выходные данные

Одно целое число: количество инверсий в массиве. Используйте 64-битный тип.

Пример

20 5
19 18

63

Для этих данных генератор выдаст массив 0 1 1 4 2 2 1 0 4 2 4 0 3 1 3 4 3 3 3 0.

Заготовка

Ввод и вывод уже написаны, остаётся реализовать функцию.

#include <cstdint>
#include <iostream>
 
// Состояние генератора псевдослучайных чисел из условия.
struct Generator {
  uint32_t a;
  uint32_t b;
  uint32_t cur;  // Начальное значение 0.
};
 
// 24-битное число: от 0 до 2^24 - 1. Вычисления идут с переполнением
// по модулю 2^32.
uint32_t Next24(Generator* generator) {
  generator->cur = generator->cur * generator->a + generator->b;
  return generator->cur >> 8;
}
 
// 32-битное число на основе двух 24-битных: от 0 до 2^32 - 1.
uint32_t Next32(Generator* generator) {
  uint32_t x = Next24(generator);
  uint32_t y = Next24(generator);
  return (x << 8) ^ y;
}
 
// Возвращает количество пар i < j, для которых values[i] > values[j].
int64_t CountInversions(uint32_t* values, int n) {
  // TODO
  return 0;
}
 
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
 
  int n;
  uint32_t m, a, b;
  std::cin >> n >> m >> a >> b;
  uint32_t* values = new uint32_t[n];
  Generator generator = {a, b, 0};
  for (int i = 0; i < n; ++i) {
    values[i] = Next24(&generator) % m;
  }
  std::cout << CountInversions(values, n) << "\n";
  delete[] values;
  return 0;
}

E. [3-5] Срез чарта

Продакт сменил курс: «Все гонятся за топ-1. А мы покажем срез всего чарта: трек, который занимает ровно $k$-е место по прослушиваниям при сортировке по неубыванию».

Проблема в том, что массив прослушиваний разросся до десяти миллионов треков, а маркетолог пообещал спонсорам выдавать $k$-й трек за миллисекунды во время прямого эфира. Пересортировать всё ради одного элемента значит похоронить базу в прямом эфире, поэтому $k$-й трек нужно вытащить хитрее, оптимизировав под задачу один из алгоритмов, рассмотренных на лекции.

Сгенерируйте массив прослушиваний длины $n$ и выведите значение, которое оказалось бы на $k$-й позиции при сортировке по неубыванию.

Входные данные

• Первая строка: $n$ и $k$, где $1 \le k \le n \le 10^7$.
• Вторая строка: $a$ и $b$, где $1 \le a, b \le 10^9$.

Массив генерируется по параметрам $n, a, b$ (в заготовке ниже это уже сделано).

Выходные данные

Одно число: количество прослушиваний трека, который оказался бы на $k$-й позиции в отсортированном по неубыванию чарте.

Пример

6 3
239 13

197852696

Сгенерированный массив: 12, 130926, 3941054950, 2013898548, 197852696, 2753287507.

Заготовка

Ввод и вывод уже написаны, остаётся реализовать функцию.

#include <cstdint>
#include <iostream>
 
// Состояние генератора псевдослучайных чисел из условия.
struct Generator {
  uint32_t a;
  uint32_t b;
  uint32_t cur;  // Начальное значение 0.
};
 
// 24-битное число: от 0 до 2^24 - 1. Вычисления идут с переполнением
// по модулю 2^32.
uint32_t Next24(Generator* generator) {
  generator->cur = generator->cur * generator->a + generator->b;
  return generator->cur >> 8;
}
 
// 32-битное число на основе двух 24-битных: от 0 до 2^32 - 1.
uint32_t Next32(Generator* generator) {
  uint32_t x = Next24(generator);
  uint32_t y = Next24(generator);
  return (x << 8) ^ y;
}
 
// Возвращает k-й по порядку элемент (k с 1) отсортированного по неубыванию
// массива. Полная сортировка не уложится в лимит времени.
uint32_t FindKthSmallest(uint32_t* values, int n, int k) {
  // TODO
  return 0;
}
 
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
 
  int n, k;
  uint32_t a, b;
  std::cin >> n >> k >> a >> b;
  uint32_t* values = new uint32_t[n];
  Generator generator = {a, b, 0};
  for (int i = 0; i < n; ++i) {
    values[i] = Next32(&generator);
  }
  std::cout << FindKthSmallest(values, n, k) << "\n";
  delete[] values;
  return 0;
}

F. [1-2] One Server to Rule Them All

После «среза чарта» (задача E) пользователи начали устраивать вечеринки синхронного прослушивания. Потоки летят от Владивостока до Калининграда, кластер греется как чайник, а пинг скачет как BPM у диджея на энергетиках. Продакт собрал экстренный созвон: «Ставим один гигантский сервер в одном месте. Чтобы всем было одинаково неудобно, но максимально честно».

Нужно выбрать такую точку, чтобы суммарное расстояние от неё до всех слушателей было минимальным. Сгенерируйте координаты $x_1, \dots, x_n$ слушателей (на прямой) и найдите точку $X$, которая минимизирует сумму расстояний:

$S = \min_X \sum_{i=1}^{n} |x_i - X|$

Перебор $X$ не подходит: волна хайпа пройдёт мимо. Оптимизируйте под задачу один из алгоритмов, рассмотренных на лекции.

Входные данные

• Первая строка: $n$, число слушателей, $1 \le n \le 10^7$.
• Вторая строка: $a$ и $b$, параметры генератора, $1 \le a, b \le 10^9$.

Координаты генерируются на лету (в заготовке ниже это уже сделано).

Выходные данные

Одно число: минимальное суммарное расстояние от центрального сервера до всех слушателей $S$. Считайте в 64-битном типе.

Пример

6
239 13

8510257371

Сгенерированный массив: 12, 130926, 3941054950, 2013898548, 197852696, 2753287507.

Заготовка

Ввод и вывод уже написаны, остаётся реализовать функцию.

#include <cstdint>
#include <iostream>
 
// Состояние генератора псевдослучайных чисел из условия.
struct Generator {
  uint32_t a;
  uint32_t b;
  uint32_t cur;  // Начальное значение 0.
};
 
// 24-битное число: от 0 до 2^24 - 1. Вычисления идут с переполнением
// по модулю 2^32.
uint32_t Next24(Generator* generator) {
  generator->cur = generator->cur * generator->a + generator->b;
  return generator->cur >> 8;
}
 
// 32-битное число на основе двух 24-битных: от 0 до 2^32 - 1.
uint32_t Next32(Generator* generator) {
  uint32_t x = Next24(generator);
  uint32_t y = Next24(generator);
  return (x << 8) ^ y;
}
 
// Возвращает минимум суммы |x_i - X| по всем точкам X.
uint64_t MinTotalDistance(uint32_t* coordinates, int n) {
  // TODO
  return 0;
}
 
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
 
  int n;
  uint32_t a, b;
  std::cin >> n >> a >> b;
  uint32_t* coordinates = new uint32_t[n];
  Generator generator = {a, b, 0};
  for (int i = 0; i < n; ++i) {
    coordinates[i] = Next32(&generator);
  }
  std::cout << MinTotalDistance(coordinates, n) << "\n";
  delete[] coordinates;
  return 0;
}

G. One slot, or one opportunity...

Вы внедрили «срез чарта» (задача E) и построили гигантский сервер (задача F), и платформа заработала без лагов. Побочный эффект: сотни новых релизов каждую секунду, и каждый автор уверен, что именно его трек спасёт музыкальную индустрию. У трека всего один шанс занять своё место в чарте.

Чарт хранится отсортированным по неубыванию рейтингов: слабые релизы слева, хиты справа. Если пересортировывать его после каждого трека, сервер сгорит, поэтому каждый новый трек должен сразу занять своё место, не ломая порядок. Если рейтинг совпадает с уже стоящими, новичок становится справа от них, чтобы не рушить привычную ленту.

Обработайте поток из $n$ новых треков. После каждой вставки выведите индекс (с нуля), на который встанет новый трек в текущем отсортированном чарте. Если возможных позиций несколько, выберите самую правую.

Входные данные

• Первая строка: $n$, количество последовательно добавляемых треков, $1 \le n \le 100000$.
• Вторая строка: $n$ целых чисел $r_i$, рейтинги треков, $1 \le r_i \le 100$.

Выходные данные

$n$ чисел: позиции, на которые становятся треки.

Пример

9
2 2 2 3 2 3 4 3 1

0 1 2 3 3 5 6 6 0

Примечание. У задачи есть скрытый бонус: рейтинги лежат в узком диапазоне, от 1 до 100, поэтому не придётся каждый раз двигать тысячи треков ради одного нового. Вспомните, какой из алгоритмов с лекций создан именно для таких случаев, когда возможных значений мало, а скорость нужна максимальная.

Заготовка

Ввод и вывод уже написаны, остаётся реализовать функцию.

#include <iostream>
 
// Вставляет трек с рейтингом rating в chart[0..*size - 1] так, чтобы чарт
// остался отсортирован по неубыванию, увеличивает *size на единицу и
// возвращает индекс (с нуля), на который трек встал.
// Среди равных рейтингов трек идёт самым правым.
int InsertTrack(int* chart, int* size, int rating) {
  // TODO
  return 0;
}
 
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
 
  int n;
  std::cin >> n;
  int* chart = new int[n];
  int size = 0;
  for (int i = 0; i < n; ++i) {
    int rating;
    std::cin >> rating;
    std::cout << InsertTrack(chart, &size, rating) << " ";
  }
  std::cout << "\n";
  delete[] chart;
  return 0;
}

H. [1-2] Хедлайнеры

У каждого трека теперь две метрики (задача C):

• популярность — насколько громко он звучит прямо сейчас;
• стабильность — насколько долго он держится в чарте.

Каталог раздулся до сотен тысяч позиций, и пользователи тонут в выборе. Маркетинг требует: «Соберите витрину. Оставьте минимальный список хедлайнеров, таких что каждый трек на платформе перекрывается хотя бы одним из них, и по популярности, и по стабильности».

Есть $n$ треков с парами чисел $(x_i, y_i)$: $x_i$ — популярность, $y_i$ — стабильность. Трек $a$ перекрывает трек $b$, если $x_a \ge x_b$ и $y_a \ge y_b$. Нужно найти минимальное множество треков $S$ такое, что для каждого исходного трека $p$ существует $s \in S$, перекрывающий его. Это и будет список хедлайнеров.

Входные данные

• Первая строка: $n$, $1 \le n \le 500000$.
• Далее $n$ строк: $x_i$ и $y_i$, $-10^9 \le x_i, y_i \le 10^9$.

Треки нумеруются с 1.

Выходные данные

• Первая строка: $k$, количество хедлайнеров.
• Вторая строка: $k$ индексов треков, которые должны войти в витрину. Если ответов несколько, выведите любой.

Пример

5
1 -1
0 0
-1 3
1 1
1 1

2
3 5

Заготовка

Ввод и вывод уже написаны, остаётся реализовать функцию.

#include <iostream>
 
struct Track {
  int popularity;
  int stability;
};
 
// Записывает в headliners номера (с 1) минимального набора треков, которые
// вместе перекрывают все остальные: x_a >= x_b и y_a >= y_b.
// Возвращает размер набора.
int FindHeadliners(const Track* tracks, int n, int* headliners) {
  // TODO
  return 0;
}
 
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
 
  int n;
  std::cin >> n;
  Track* tracks = new Track[n];
  int* headliners = new int[n];
  for (int i = 0; i < n; ++i) {
    std::cin >> tracks[i].popularity >> tracks[i].stability;
  }
  int count = FindHeadliners(tracks, n, headliners);
  std::cout << count << "\n";
  for (int i = 0; i < count; ++i) {
    std::cout << headliners[i] << " ";
  }
  std::cout << "\n";
  delete[] tracks;
  delete[] headliners;
  return 0;
}

I. [✯] Пересортировка судного дня

Всё пропало. Чарт, который вы строили месяцами, сгорел быстрее, чем свежий релиз от рэпера из общаги:

• дежурный перезапустил прод, забыв выключить «режим тестовых данных»;
• база с рейтингами упала на staging и поднялась на маркетинговом дашборде;
• кто-то зашёл под root и поставил ORDER BY RANDOM() «чтобы глянуть».

На главной теперь архивные дудки из 2012 года в топе и трек вашего продакта «Сортировка моей жизни» под номером один. Продакт греет руки об сервер и шепчет: «Нужно собрать чарт заново, все треки, в порядке рейтинга, и к утру».

Обычная сортировка за $O(n \log n)$ не выдержит. Нужно вспомнить кусок лекции про сортировки линейного времени.

В каждом из $t$ тестов дан массив из $n$ случайных чисел $x_i$ ($0 \le x_i < 2^{32}$). Нужно:

1. отсортировать массив по неубыванию;
2. вычислить сумму $\sum_{i=1}^{n} x_i \cdot i$, где $i$ — позиция числа в отсортированном массиве (нумерация с 1).

Эта сумма — как KPI продакта: чем выше трек, тем сильнее его вес.

Входные данные

• Первая строка: $t$ и $n$, количество тестов и длина массива в каждом, $1 \le t \le 200$, $1 \le n \le 50000$.
• Вторая строка: $a$ и $b$, параметры генератора, $1 \le a, b \le 10^9$. Генерация уже есть в заготовке ниже.

Выходные данные

Для каждого теста одно число на отдельной строке: $\sum_{i=1}^{n} x_i \cdot i$.

Пример

1 6
239 13

46062181379

Сгенерированный массив: 12, 130926, 3941054950, 2013898548, 197852696, 2753287507.

Заготовка

Ввод и вывод уже написаны, остаётся реализовать функцию.

#include <cstdint>
#include <iostream>
 
// Состояние генератора псевдослучайных чисел из условия.
struct Generator {
  uint32_t a;
  uint32_t b;
  uint32_t cur;  // Начальное значение 0.
};
 
// 24-битное число: от 0 до 2^24 - 1. Вычисления идут с переполнением
// по модулю 2^32.
uint32_t Next24(Generator* generator) {
  generator->cur = generator->cur * generator->a + generator->b;
  return generator->cur >> 8;
}
 
// 32-битное число на основе двух 24-битных: от 0 до 2^32 - 1.
uint32_t Next32(Generator* generator) {
  uint32_t x = Next24(generator);
  uint32_t y = Next24(generator);
  return (x << 8) ^ y;
}
 
// Сортирует values по неубыванию сортировкой за линейное время и возвращает
// сумму x_i * i, где i — позиция в отсортированном массиве (с 1).
uint64_t SortAndWeigh(uint32_t* values, int n) {
  // TODO
  return 0;
}
 
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
 
  int tests, n;
  uint32_t a, b;
  std::cin >> tests >> n >> a >> b;
  uint32_t* values = new uint32_t[n];
  Generator generator = {a, b, 0};
  while (tests-- > 0) {
    for (int i = 0; i < n; ++i) {
      values[i] = Next32(&generator);
    }
    std::cout << SortAndWeigh(values, n) << "\n";
  }
  delete[] values;
  return 0;
}

• Язык решений — GNU C++20.
• Лимит 1 секунда и 256 МБ, в задаче B — 64 МБ.
• Каждая задача оценивается автоматически по тестам на sort-me.org.

Решения отправляются на sort-me.org: откройте задачу, прикрепите файл с кодом и нажмите «Отправить». Дедлайн указан в таймере контеста.