Hello, Codeforces!
Really sorryText may have a lot of mistakes, but i really tried very hard to make my post understandable.
In this post I would like to talk about solving two types of problems, with almost the same solution. Unfortunately, I do not know how popular this idea is. For the first time I came up with it at the regional stage of 2021/22 in informatics for a certain subtask. And few days ago I noticed the idea in a problem from Google Kick Start and 1637E - Best Pair, so I decided to write this post.
Problem 1
Definition: Given an integer $$$0 \leq K < 10^5$$$ and 2 sorted in ascending order arrays $$$a_1, a_2, \ldots, a_n \ (a_i \leq 10^9)$$$ and $$$b_1, b_2, \ldots, b_n \ (b_i \leq 10^9)$$$. Were written $$$n^2$$$ fractions of the form $$$\frac{a_i}{b_j}, 1 \leq i \leq n, 1 \leq j \leq n$$$. After that, all these fractions were sorted in ascending order. You need to print the value of the $$$k$$$-th ascending fraction.
Idea: It would seem to be generated $$$n^2 \leq 10^{10}$$$ and you cant calculate all this fractions for a reasonable time. However, if you look at the $$$K$$$ constraint it can be understood that we are not interested in all $$$n^2$$$ fractions, but in first $$$K$$$. Then let's maintain the minimum number and move from it to the next.
Solution: For convenience reverse $$$b$$$ array, so that it becomes sorted in descending order and denote by $$$(i, j)$$$ fraction $$$\frac{a_i}{b_j}$$$. Not hard to notice, that $$$(i, j) \leq (i + 1, j)$$$ and $$$(i, j) \leq (i, j + 1)$$$. Hence it is clear that $$$(0, 0)$$$ will be the first element in the sorted array. The statement is that if we considered $$$(i, j)$$$ as a minimal fraction, then two fractions are added to the "candidates" for a new minimum: $$$(i + 1, j)$$$ and $$$(i, j + 1)$$$. This seems intuitive, however, just below is an attempt to prove why this is so. The task was reduced to supporting candidates and taking the best of them.
Codeset<pair<int, int>> candidates;
void add(int i, int j) {
if (i >= n || j >= n) return;
candidates.insert({i, j}); //IMPORTANT, code should comapre not i, j pairs but fractions 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;
Proof about 2 candidatesIt can be imagined as a weighted directed graph at $$$n^2$$$ vertexes where edge $$$(i, j) \rightarrow (k, l)$$$ exists if $$$(i, j) \leq (k, l)$$$, and edge weight $$$w= (k, l) - (i, j)$$$. Then if you run Dijkstra on this graph, it will pass all the fractions in sorted order. Then the transition from the vertex $$$(i, j)$$$ to vertex $$$(i+ 1, j)$$$ it will be no worse than any transition from the vertex $$$(i, j)$$$ to vertex $$$(i+ k, j), 0 < k$$$
Proof of asymptoticsEvery time we get the $$$i$$$-th element in the sorted array, we remove 1 element from the candidates and add no more than 2 new ones. We get that time complexity $$$O(k*logk)$$$
Problem 2
Definition: 1637E - Best Pair
Idea: Note that different $$$cnt_x$$$ no more $$$\sqrt{n}$$$. Create an array $$$A$$$, which in index $$$i$$$ stores a vector sorted in descending order $$$x$$$ such that $$$cnt_x = i$$$. Let's fix $$$cnt_x$$$ and $$$cnt_y$$$. Since we have fixed one of the multipliers, we need to maximize $$$x+y$$$.
For convenience , we denote $$$a = A[cnt_x]$$$, $$$b = A[cnt_y]$$$. As position denote $$$(i, j)$$$. You need to choose a position such that $$$(a_i, b_j)$$$ is not a bad pair. Using the observations that were made above, we note that:
- Best answer at the "position" $$$(0, 0)$$$
- If we are not satisfied $$$(i, j)$$$ we are adding candidates $$$(i + 1, j)$$$ and $$$(i, j + 1)$$$
This is the same task 1, but now we are not doing it a fixed number of times, but for now the best pair is bad. My solution: 146149856
Proof of asymptoticsEvery time we get the $$$i$$$-th element in the sorted array, we remove 1 element from the candidates and add no more than 2 new ones. Since each bad pair can only meet in one pair $$$(cnt_x, cnt_y)$$$, we will process each bad pair no more than once. We get that time complexity $$$O(k*logk)$$$
Problem 3
Definition:
Original statementsThe 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)$$$.
Idea: Similarly to the problem 2 we have bad sets and we need to choose the best among the others (in this case, the function of the set is the number of complaints). The initial value is not difficult to determine: For each bit, we look independently, it is more profitable to put 0 either 1. Next we try to change exactly one bit. The logic is the same as in the problem 2, but now not 2 transitions, but $$$P$$$. Time complexity $$$O(PMlog(PM))$$$.
Code#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';
}
}
Hope it will help someone.
Good luck and have a high rating!
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