Thanks for participating in the round, we hope you liked the problems!
| Handle | A | B | C | D | E1 | E2 | F |
|---|---|---|---|---|---|---|---|
| Vladithur | 16K | 8K | 3K | 900 | 500 | 50 | 4 |
| GlowCheese | 14K | 9K | 5K | 500 | ? | ? | ? |
| thanhchauns2 | 14K | 8K | 2K | 1K | 500 | ? | ? |
| QuangBuiCPP | 14K | 7K | 2K | 1K | 500 | 24 | 5 |
| welleyth | 16K | 10K | 4K | 1.5K | 600 | 130 | 2 |
| Kon567889 | 14K | 10K | 5K | 2K | ? | ? | 5 |
The smallest possible sum is $$$1 + 2 + \ldots + k$$$.
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())
const char nl = '\n';
typedef long long ll;
typedef long double ld;
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int T;
cin >> T;
while (T--) {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
vector<int> b = a;
sort(all(b));
int x = b[k - 1];
int ans = 0;
for (int i = 0; i < k; i++) {
if (a[i] > x) ans++;
}
cout << ans << nl;
}
}
Bonus: solve for every $$$k$$$ from $$$1$$$ to $$$n$$$ for $$$n \le 10^5$$$.
In an optimal answer, for all $$$1 \le i \le n$$$, $$$\operatorname{lcm}(i, p_i) = i \cdot p_i$$$.
$$$\operatorname{lcm}(x, x + 1) = x \cdot (x + 1)$$$.
$$$\operatorname{lcm}(x, x + 1) + \operatorname{lcm}(x + 1, x) = x^2 + (x + 1)^2 - 1$$$.
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())
const char nl = '\n';
typedef long long ll;
typedef long double ld;
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
if (n % 2 == 0) {
for (int i = 1; i <= n; i += 2) {
cout << i + 1 << ' ' << i << ' ';
}
cout << nl;
} else {
cout << 1 << ' ';
for (int i = 2; i <= n; i += 2) {
cout << i + 1 << ' ' << i << ' ';
}
cout << nl;
}
}
}
Bonus: try to prove the solution without the editorial!
The operation only decreases numbers.
An array is sorted if there is no index $$$i$$$ such that $$$a_i > a_{i + 1}$$$.
Suppose there is an index $$$i$$$ such that $$$a_i > a_{i + 1}$$$. What operations do you need to perform to make $$$a_i \le a_{i + 1}$$$?
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())
const char nl = '\n';
typedef long long ll;
typedef long double ld;
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> a(n);
map<int, vector<int>> p;
for (int i = 0; i < n; i++) {
cin >> a[i];
p[a[i]].push_back(i);
}
int ans = 0;
set<int> ts;
for (int i = 0; i < n - 1; i++) {
if (a[i] > a[i + 1]) ts.insert(i);
}
while (!ts.empty()) {
int i = *ts.begin();
int x;
if (a[i] > 0) {
x = a[i];
} else {
x = a[i + 1];
}
for (int j: p[x]) {
a[j] = 0;
ts.erase(j - 1);
ts.erase(j);
if (j > 0 && a[j - 1] > a[j]) ts.insert(j - 1);
if (j + 1 < n && a[j] > a[j + 1]) ts.insert(j);
}
ans++;
}
cout << ans << nl;
}
}
Bonus: solve for when $$$a_i$$$ can also be negative.
$$$\operatorname{d}(u; v) \le 2 \cdot \min(a_1 \ldots a_n)$$$
diameter $$$\le 2 \cdot \min(a_1 \ldots a_n)$$$
diameter $$$\le \max\limits_{1 \le i \le n - 1}{\min(a_i,a_{i+1})}$$$
Binary search on the answer or do a clever greedy.
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())
const char nl = '\n';
typedef long long ll;
typedef long double ld;
using namespace std;
const int inf = 1000000000;
bool f(vector<int> a, int k, int ans) {
int n = gsize(a);
int dk = 0;
for (int i = 0; i < n; i++) {
if (a[i] * 2 < ans) {
a[i] = inf;
k--;
dk++;
}
}
if (k < 0) return false;
if ((k > 0 && dk > 0) || k >= 2) return true;
if (k == 1 && dk == 0) {
return *max_element(all(a)) >= ans;
}
for (int i = 0; i < n - 1; i++) {
if (min(a[i], a[i + 1]) >= ans) return true;
}
return false;
}
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
int lb = 0, ub = inf, tans = 0;
while (lb <= ub) {
int tm = (lb + ub) / 2;
if (f(a, k, tm)) {
tans = tm;
lb = tm + 1;
} else {
ub = tm - 1;
}
}
cout << tans << nl;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int T;
cin >> T;
while (T--) solve();
}
Bonus: solve for every $$$k$$$ from $$$1$$$ to $$$n$$$.
1712E2 - LCM Sum (hard version)
Count the number of "bad" triplets such that $$$\operatorname{lcm}(i, j, k) < i + j + k$$$.
$$$\operatorname{lcm}(i, j, k) \le 2 \cdot k$$$ in a bad triplet.
A triplet is bad iff $$$\operatorname{lcm}(i, j, k) = k$$$ or ($$$\operatorname{lcm}(i, j, k) = 2 \cdot k$$$ and $$$i + j > k$$$).
$$$\operatorname{lcm}(i, j, k) = x$$$ implies $$$i$$$, $$$j$$$, and $$$k$$$ are all divisors of $$$x$$$.
For every $$$k$$$, iterate over all pairs of divisors of $$$2 \cdot k$$$.
Think of the "bad" triplets as of segments $$$[i; k]$$$ with some weight.
Solve in offline.
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())
const char nl = '\n';
typedef long long ll;
typedef long double ld;
using namespace std;
const int maxn = 200000;
int t[(maxn + 1) * 4];
void update(int v, int tl, int tr, int i, int x) {
t[v] += x;
if (tl != tr - 1) {
int tm = (tl + tr) / 2;
if (i < tm) update(2*v + 1, tl, tm, i, x);
else update(2*v + 2, tm, tr, i, x);
}
}
int query(int v, int tl, int tr, int l, int r) {
if (l >= r) return 0;
if (tl == l && tr == r) return t[v];
else {
int tm = (tl + tr) / 2;
int r1 = query(2*v + 1, tl, tm, l, min(r, tm));
int r2 = query(2*v + 2, tm, tr, max(l, tm), r);
return r1 + r2;
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
vector<vector<int>> d(2*maxn + 1);
for (int i = 1; i <= maxn; i++) {
for (int j = i; j <= 2*maxn; j += i) {
d[j].push_back(i);
}
}
vector<vector<pair<int, int>>> segs(maxn + 1);
for (int k = 1; k <= maxn; k++) {
for (int ti = 0; ti < gsize(d[2*k]); ti++) {
int i = d[2*k][ti], ct = 0;
for (int tj = ti + 1; tj < gsize(d[2*k]); tj++) {
int j = d[2*k][tj];
if (j >= k) break;
if (i + j > k || (k % i == 0 && k % j == 0)) ct++;
}
if (ct > 0) {
segs[i].emplace_back(k, ct);
}
}
}
int T;
cin >> T;
vector<ll> ans(T);
vector<array<int, 3>> queries;
for (int i = 0; i < T; i++) {
ll l, r;
cin >> l >> r;
queries.push_back({l, r, i});
ans[i] = (r - l + 1) * (r - l) * (r - l - 1) / 6;
}
sort(all(queries));
int ti = T - 1;
for (int i = maxn; i >= 1; i--) {
// Update ST
for (auto [r, ct]: segs[i]) {
update(0, 0, maxn + 1, r, ct);
}
// Get Answers
while (ti >= 0 && queries[ti][0] == i) {
ans[queries[ti][2]] -= query(0, 0, maxn + 1, i, queries[ti][1] + 1);
ti--;
}
}
for (int i = 0; i < T; i++) cout << ans[i] << nl;
}
Bonus: solve the problem in $$$\mathcal{O}((n + t) \log n)$$$ or better.
Let $$$f_v$$$ be the distance to the closest vertex $$$\in L$$$ to $$$v$$$. You can calculate it for every vertex in $$$O(n)$$$.
The distance in the new graph $$$\operatorname{d'}(u, v)$$$ is equal to $$$\min(\operatorname{d}(u, v), f_u + f_v + x)$$$
Suppose there is a vertex $$$v$$$ with $$$f_v > 0$$$. Then there is always a vertex $$$u$$$ in the subtree of $$$v$$$ such that $$$f_u < f_v$$$ and $$$depth_u$$$ > $$$depth_v$$$.
Think small-to-large merging.
Maintain the largest value of $$$depth_v$$$ over all $$$v$$$ with $$$f_v = i$$$ for all needed $$$i$$$.
In this problem, small-to-large merging works in $$$O(n)$$$.
The diameter is $$$\le n$$$. So you can increase it by $$$1$$$ at most $$$n$$$ times.
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())
const char nl = '\n';
typedef long long ll;
typedef long double ld;
using namespace std;
const int maxn = 1000000;
int f[maxn], d[maxn];
vector<int> g[maxn], g2[maxn], val[maxn];
int n, q;
vector<int> ans, x;
void solve() {
for (int v = n - 1; v >= 0; v--) {
for (int u: g[v]) {
if (gsize(val[u]) > gsize(val[v])) swap(val[u], val[v]);
for (int fu = 0; fu < gsize(val[u]); fu++) {
for (int qi = 0; qi < q; qi++) {
while (true) {
int fv = max(0, ans[qi] - fu - x[qi]);
if (fv < gsize(val[v]) &&
val[v][fv] + val[u][fu] - 2*d[v] >= ans[qi]) ans[qi]++;
else break;
}
}
}
for (int fu = 0; fu < gsize(val[u]); fu++) {
val[v][fu] = max(val[v][fu], val[u][fu]);
}
val[u].clear();
val[u].shrink_to_fit();
}
{
int fu = f[v];
for (int qi = 0; qi < q; qi++) {
while (true) {
int fv = max(0, ans[qi] - fu - x[qi]);
if (fv < gsize(val[v]) &&
val[v][fv] - d[v] >= ans[qi]) ans[qi]++;
else break;
}
}
if (fu == gsize(val[v])) {
val[v].push_back(d[v]);
}
}
}
for (int i = 0; i < q; i++) {
ans[i]--;
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
vector<int> deg(n);
for (int i = 1; i < n; i++) {
int p;
cin >> p;
d[i] = d[p - 1] + 1;
g[p - 1].push_back(i);
g2[i].push_back(p - 1);
}
{
queue<int> qe;
vector<bool> used(n, false);
for (int i = 0; i < n; i++) {
if (gsize(g2[i]) + gsize(g[i]) == 1) {
qe.push(i);
used[i] = true;
}
}
while (!qe.empty()) {
int v = qe.front();
qe.pop();
for (int u: g[v]) {
if (used[u]) continue;
f[u] = f[v] + 1;
qe.push(u);
used[u] = true;
}
for (int u: g2[v]) {
if (used[u]) continue;
f[u] = f[v] + 1;
qe.push(u);
used[u] = true;
}
}
}
cin >> q;
for (int i = 0; i < q; i++) {
int tx;
cin >> tx;
x.push_back(tx);
ans.push_back(0);
}
solve();
for (int tans: ans) cout << tans << ' ';
cout << nl;
}
Bonus: solve for $$$n, q \le 10^6$$$.
Don't forget to rate the problems!
PS: Solution codes probably will be added later.
UPD: explanations of the references:
Hope you liked them!
The quote is just a modification of the original title of KonoSuba.
This is just something I invented, no reference here. Hope you liked the short poem!
The quote is the meme "people die when they are killed" in the Fate series, changed to fit the programming context. And the title is just "Fate Zero" changed to "Sort Zero".
"Do you have a wish?" is a recurring phrase in the LN series HakoMari, referring to the wish granting "boxes". The title is just "Empty Box" changed to "Empty Graph". Also, "O_o" is a reference to one of the main characters, "O".
The quote can probably be traced to many origins, but I personally modified the quote "We are legion, for we are many" from the series 86. There were also a lot of 6's and 8's in the sample, which might have helped you guess.
I didn't really think about this one, just modified a quote from Vivy a bit.
UPD2: added solution codes (better late than never...)
