Привет, Codeforces!
В этом посте я бы хотел рассказать про решение двух типов задач, с почти одинаковым решением. К сожалению я не знаю, насколько эта идея распространена. Впервые я ее придумал на региональном этапе 2021/22 года по информатике для определенной подгруппы. А на днях заметил в задаче с Google Kick Start и 1637E - Лучшая пара, поэтому решил написать данный пост.
Задача 1
Формулировка: Дано число $$$0 \leq K < 10^5$$$ и два отсортированных по возрастанию массива $$$a_1, a_2, \ldots, a_n \ (a_i \leq 10^9)$$$ и $$$b_1, b_2, \ldots, b_n \ (b_i \leq 10^9)$$$. Были выписаны $$$n^2$$$ дробей вида $$$\frac{a_i}{b_j}, 1 \leq i \leq n, 1 \leq j \leq n$$$. После этого все эти дроби были отсортированы по возрастанию. Нужно вывести значение K-ой по возрастанию дроби.
Идея: Казалось бы, генерируется $$$n^2 \leq 10^{10}$$$ чисел, и нельзя получить отсортированный массив за разумное время. Однако, если посмотреть на ограничение по $$$K$$$ можно понять, что нас интересуют не все $$$n^2$$$ чисел, а только $$$K$$$ наименьших. Тогда давайте поддерживать минимальное число и из него переходить в следующее.
Решение: Для удобства развернем массив $$$b$$$, чтобы он стал отсортирован по убыванию и обозначим за $$$(i, j)$$$ дробь $$$\frac{a_i}{b_j}$$$. Несложно заметить, что $$$(i, j) \leq (i + 1, j)$$$ и $$$(i, j) \leq (i, j + 1)$$$. Отсюда ясно, что $$$(0, 0)$$$ будет первым элементом в отсортированном массиве. Утверждение заключается в том, что если мы рассмотрели $$$(i, j)$$$ как минимальную дробь, то в "кандидаты" на новый минимум добавляется две дроби $$$(i + 1, j)$$$ и $$$(i, j + 1)$$$. Это кажется интуитивно понятным, однако чуть ниже попытка доказать, почему это так. Задача свелась к тому, чтобы поддерживать кандидатов и брать лучшего из них.
Кодset<pair<int, int>> candidates;
void add(int i, int j) {
if (i >= n || j >= n) return;
candidates.insert({i, j}); //ВАЖНО, чтобы код сравнивал не пары i, j а дроби a[i]/b[j]
}
...
candidates.insert({0, 0});
for (int i = 0; i < k; ++i) {
auto [x, y] = *candidates.begin();
candidates.erase(candidates.begin());
add(x + 1, y);
add(x, y + 1);
auto [x, y] = *candidates.begin();
int g = __gcd(a[x], b[y]);
x = a[x] / g;
y = b[y] / g;
cout << x << '/' << y;
Доказательство про 2 кандидатовМожно представить взвешенный ориентированный граф на $$$n^2$$$ вершин где ребро $$$(i, j) \rightarrow (k, l)$$$ существует если $$$(i, j) \leq (k, l)$$$, а вес ребра $$$w= (k, l) - (i, j)$$$. Тогда если на данном графе запустить дейкстру, то он обойдет дроби в отсортированном порядке. Тогда переход из вершины $$$(i, j)$$$ в вершину $$$(i+ 1, j)$$$ будет не хуже любого перехода из вершины $$$(i, j)$$$ в вершину $$$(i+ k, j), 0 < k$$$
Доказательство асимптотикиКаждый раз, когда мы получаем i-ый элемент в отсортированном массиве, мы удаляем из кандидатов 1 элемент и добавляем не более 2х новых. Получаем, что время работы $$$O(k*logk)$$$
Задача 2
Формулировка: 1637E - Лучшая пара
Идея: Заметим, что различных $$$cnt_x$$$ не более $$$\sqrt{n}$$$. Создадим массив $$$A$$$, который в индексе $$$i$$$ хранит отсортированный по убыванию вектор $$$x$$$ таких, что $$$cnt_x = i$$$. Тогда переберем $$$cnt_x, cnt_y$$$. Так как один из множителей мы зафиксировали, нам нужно максимизировать $$$x+y$$$.
Для удобства обозначим $$$a = A[cnt_x]$$$, $$$b = A[cnt_y]$$$. Позицией будем называть $$$(i, j)$$$. Нужно выбрать такую позицию, что $$$(a_i, b_j)$$$ не является запрещенной парой. Используя наблюдения, которые были высказаны выше, замечаем, что:
- Лучший ответ в "позиции" $$$(0, 0)$$$
- Если нас не устраивает $$$(i, j)$$$ мы переходим в $$$(i + 1, j)$$$ или $$$(i, j + 1)$$$
Это та же задача 1, но теперь мы делаем не фиксированное количество раз, а пока лучшая пара является запрещенной. Мое решение на это задачу: 146149856
Доказательство асимптотикиКаждый раз, когда мы получаем, что оптимальная пара является плохой, мы удаляем из кандидатов 1 элемент и добавляем не более 2х новых. Так как каждая плохая пара может встретиться только в одной паре $$$(cnt_x, cnt_y)$$$, каждую плохую пару мы обработаем не более одного раза. Получаем, что время работы $$$O(m * logn + n)$$$
Задача 3
Формулировка: Вам поступило $$$N$$$ заказов напитков от друзей. Напиток задается битовой строкой $$$s_i$$$ длины $$$P$$$. Если вы купите напиток $$$S$$$ то $$$i-ый$$$ друг будет недоволен столько раз, сколько существует индексов $$$j$$$, что $$$S_j \neq s_{i, j}$$$. Однако по экономическим соображениям в магазин, в котором вы покупаете напиток, есть $$$M$$$ напитков, которые купить нельзя.
Дано: $$$1 \leq N \leq 100, 1 \leq P \leq 100, 0 \leq M \leq min(100, 2^P - 1)$$$. Вам нужно выбрать такую строку $$$S$$$, что суммарное недовольство всех друзей будет минимальным.
Оригинальные условия на английскомThe milk tea in China is very delicious. There are many binary ("either-or") options for customizing a milk tea order, such as:
"with ice" OR "no ice" "with sugar" OR "no sugar" "with bubbles" OR "no bubbles" "with pudding" OR "no pudding" and so on. A customer's preferences for their milk tea can be represented as a binary string. For example, using the four properties above (in the order they are given), the string 1100 means "with ice, with sugar, no bubbles, no pudding".
Today, Shakti is on duty to buy each of his N friends a milk tea, at a shop that offers P binary options. But after collecting everyone's preferences, Shakti found that the order was getting too complicated, so Shakti has decided to buy the same type of milk tea for everyone. Shakti knows that for every friend, for every preference that is not satisfied, they will complain once. For example, if two of the friends have preferences for types 101 and 010, and Shakti chooses type 001, then the first friend will complain once and the second friend will complain twice, for a total of three complaints.
Moreover, there are M different forbidden types of milk tea that the shop will not make, and Shakti cannot choose any of those forbidden types.
What is the smallest number of complaints that Shakti can get? $$$1 \leq N \leq 100, 1 \leq P \leq 100, 0 \leq M \leq min(100, 2^P - 1)$$$.
Идея: Аналогично задаче 2 у нас есть запрещенные множества и среди остальных нужно выбрать лучшее (в данном случае функция от множества это количество недовольств). Начальное значение определить не сложно: для каждого бита независимо смотрим, выгоднее поставить 0 или 1. Далее мы пытаемся изменить ровно один бит. Логика такая же, как и в задаче 2, но теперь не 2 перехода, а $$$P$$$. Сложность $$$O(PMlog(PM))$$$.
Код#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
/*
⣿⣿⣷⡁⢆⠈⠕⢕⢂⢕⢂⢕⢂⢔⢂⢕⢄⠂⣂⠂⠆⢂⢕⢂⢕⢂⢕⢂⢕⢂
⣿⣿⣿⡷⠊⡢⡹⣦⡑⢂⢕⢂⢕⢂⢕⢂⠕⠔⠌⠝⠛⠶⠶⢶⣦⣄⢂⢕⢂⢕
⣿⣿⠏⣠⣾⣦⡐⢌⢿⣷⣦⣅⡑⠕⠡⠐⢿⠿⣛⠟⠛⠛⠛⠛⠡⢷⡈⢂⢕⢂
⠟⣡⣾⣿⣿⣿⣿⣦⣑⠝⢿⣿⣿⣿⣿⣿⡵⢁⣤⣶⣶⣿⢿⢿⢿⡟⢻⣤⢑⢂
⣾⣿⣿⡿⢟⣛⣻⣿⣿⣿⣦⣬⣙⣻⣿⣿⣷⣿⣿⢟⢝⢕⢕⢕⢕⢽⣿⣿⣷⣔
⣿⣿⠵⠚⠉⢀⣀⣀⣈⣿⣿⣿⣿⣿⣿⣿⣿⣿⣗⢕⢕⢕⢕⢕⢕⣽⣿⣿⣿⣿
⢷⣂⣠⣴⣾⡿⡿⡻⡻⣿⣿⣴⣿⣿⣿⣿⣿⣿⣷⣵⣵⣵⣷⣿⣿⣿⣿⣿⣿⡿
⢌⠻⣿⡿⡫⡪⡪⡪⡪⣺⣿⣿⣿⣿⣿⠿⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃
⠣⡁⠹⡪⡪⡪⡪⣪⣾⣿⣿⣿⣿⠋⠐⢉⢍⢄⢌⠻⣿⣿⣿⣿⣿⣿⣿⣿⠏⠈
⡣⡘⢄⠙⣾⣾⣾⣿⣿⣿⣿⣿⣿⡀⢐⢕⢕⢕⢕⢕⡘⣿⣿⣿⣿⣿⣿⠏⠠⠈
⠌⢊⢂⢣⠹⣿⣿⣿⣿⣿⣿⣿⣿⣧⢐⢕⢕⢕⢕⢕⢅⣿⣿⣿⣿⡿⢋⢜⠠⠈
⠄⠁⠕⢝⡢⠈⠻⣿⣿⣿⣿⣿⣿⣿⣷⣕⣑⣑⣑⣵⣿⣿⣿⡿⢋⢔⢕⣿⠠⠈
⠨⡂⡀⢑⢕⡅⠂⠄⠉⠛⠻⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⡿⢋⢔⢕⢕⣿⣿⠠⠈
⠄⠪⣂⠁⢕⠆⠄⠂⠄⠁⡀⠂⡀⠄⢈⠉⢍⢛⢛⢛⢋⢔⢕⢕⢕⣽⣿⣿⠠⠈
*/
#define all(a) a.begin(), a.end()
#define FNAME ""
#define int ll
typedef pair<int, int> pii;
#define _ << ' ' <<
#define vec vector
const bool DEBUG = true;
#ifndef HOME
#define err \
if (0) cerr
#else
#define err \
if (DEBUG) cerr
#endif
#ifdef int
const int INF = 2e16;
#else
const int INF = 2e9;
#endif
mt19937 gen(time(0));
//END
set<pii> st;
const int MAXN = 1e5;
vec<int> t[MAXN];
int lst = 0;
vec<int> cnt;
int n;
void add(vec<int> &v) {
t[lst] = v;
int tmp = 0;
int sz = v.size();
for (int i = 0; i < sz; ++i) {
if (v[i]) {
tmp += n - cnt[i];
} else {
tmp += cnt[i];
}
}
st.insert({tmp, lst});
lst++;
}
void solve() {
//code here
int m, p;
cin >> n >> m >> p;
cnt.assign(p, 0);
lst = 0;
st.clear();
for (int i = 0; i < n; ++i) {
string s;
cin >> s;
for (int j = 0; j < p; ++j) {
int x = s[j] - '0';
cnt[j] += x;
}
}
set<vec<int>> usd;
for (int i = 0; i < m; ++i) {
vec<int> v(p);
for (int j = 0; j < p; ++j) {
char x;
cin >> x;
if (x == '1') v[j] = 1;
}
usd.insert(v);
}
vec<int> init(p);
for (int i = 0; i < p; ++i) {
if (cnt[i] > n - cnt[i]) {
init[i] = 1;
}
}
add(init);
set<vec<int>> myusd;
while (!st.empty()) {
auto [x, i] = *st.begin();
st.erase(st.begin());
vec<int> v = t[i];
if (usd.count(v) == 0) {
cout << x;
return;
}
myusd.insert(v);
for (int i = 0; i < p; ++i) {
v[i] ^= 1;
if (myusd.count(v) == 0) {
add(v);
}
v[i] ^= 1;
}
}
// assert(0);
//
}
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
//freopen("input.txt", "w", stdout);
#else
if (FNAME != "") {
freopen(FNAME ".in", "r", stdin);
freopen(FNAME ".out", "w", stdout);
}
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int tt = 1;
cin >> tt;
for (int req = 0; req < tt; ++req) {
unsigned start = clock();
cout << "Case #" << req + 1 << ": ";
solve();
cout << '\n';
unsigned end = clock();
cerr << "WorkTime: " << (end - start) / (double) CLOCKS_PER_SEC << '\n';
}
}
Надеюсь данная идея поможет кому-то в решении задач.
Удачи и высокого рейтинга!
For more on this topic (finding the k maximum/minimum items in a large search space), you can check out USACO guide fracturing search and Algorithms Live about fracturing search