We hope you enjoyed the contest! We recommend you to read all tutorials even if you solve the problem, maybe you will learn something new.
1637A - Sorting Parts
Idea: __JustMe__.
What does happen if the array is already sorted?
What does happen if there are two indexes $$$i$$$ and $$$j$$$, such that $$$i < j$$$ and $$$a_i > a_j$$$?
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
for (int i = 0; i < t; i++) {
int n;
cin >> n;
vector<int> a(n);
for (auto& u : a)
cin >> u;
if (!is_sorted(a.begin(), a.end()))
cout << "YES\n";
else
cout << "NO\n";
}
}
1637B - MEX and Array
Idea: __JustMe__ and Mangooste.
What does happen after replacing a segment of length greater than $$$1$$$ with segments of length $$$1$$$?
The cost of the array $$$b_1, b_2, \ldots, b_k$$$ equals to $$$k + \sum_{i=1}^{k} mex($$${$$$b_i$$$}$$$)$$$.
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
for (int i = 0; i < t; i++) {
int n;
cin >> n;
vector<int> a(n);
for (auto& u : a)
cin >> u;
int ans = 0;
for (int i = 0; i < n; i++) {
ans += (i + 1) * (n - i);
if (a[i] == 0)
ans += (i + 1) * (n - i);
}
cout << ans << '\n';
}
}
1637C - Andrew and Stones
Idea: TeaTime.
The answer is $$$-1$$$ in two cases. If $$$n = 3$$$ and $$$a_2$$$ is odd. Also if for all $$$1 < i < n$$$: $$$a_i = 1$$$.
It is not optimal to add $$$1$$$ to an odd number more than once.
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a)
cin >> x;
if (*max_element(a.begin() + 1, a.end() - 1) == 1 || (n == 3 && a[1] % 2 == 1)) {
cout << "-1\n";
return;
}
long long answer = 0;
for (int i = 1; i < n - 1; i++)
answer += (a[i] + 1) / 2;
cout << answer << '\n';
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int tests;
cin >> tests;
while (tests--)
solve();
}
1637D - Yet Another Minimization Problem
Idea: Mangooste.
Try to simplify the array cost formula.
The total cost of two arrays equals to $$$(n - 2) \cdot \sum_{i=1}^{n} (a_i^2 + b_i^2) + (\sum_{i=1}^n a_i)^2 + (\sum_{i=1}^n b_i)^2$$$.
Find all possible sums of the array $$$a$$$ after some operations.
#include <bits/stdc++.h>
using namespace std;
constexpr int MAXSUM = 100 * 100 + 10;
int sqr(int x) {
return x * x;
}
void solve() {
int n;
cin >> n;
vector<int> a(n), b(n);
for (auto& u : a)
cin >> u;
for (auto& u : b)
cin >> u;
int sumMin = 0, sumMax = 0, sumSq = 0;
for (int i = 0; i < n; i++) {
if (a[i] > b[i])
swap(a[i], b[i]);
sumSq += sqr(a[i]) + sqr(b[i]);
sumMin += a[i];
sumMax += b[i];
}
bitset<MAXSUM> dp;
dp[0] = 1;
for (int i = 0; i < n; i++)
dp |= dp << (b[i] - a[i]);
int ans = sqr(sumMin) + sqr(sumMax);
for (int i = 0; i <= sumMax - sumMin; i++)
if (dp[i])
ans = min(ans, sqr(sumMin + i) + sqr(sumMax - i));
cout << sumSq * (n - 2) + ans << '\n';
}
int main() {
int t;
cin >> t;
while (t--)
solve();
}
1637E - Best Pair
Idea: Mangooste.
Fix $$$x$$$ and iterate over all $$$cnt_y \le cnt_x$$$. It works in $$$O(n)$$$ summary.
When you fix $$$x$$$ and $$$cnt_y$$$, interate over all $$$y$$$ in the non increasing order while $$$x = y$$$ or the pair $$$(x, y)$$$ is bad.
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n);
map<int, int> cnt;
for (auto &x : a) {
cin >> x;
cnt[x]++;
}
vector<pair<int, int>> bad_pairs;
bad_pairs.reserve(2 * m);
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
bad_pairs.emplace_back(x, y);
bad_pairs.emplace_back(y, x);
}
sort(bad_pairs.begin(), bad_pairs.end());
vector<vector<int>> occ(n);
for (auto &[x, c] : cnt)
occ[c].push_back(x);
for (auto &v : occ)
reverse(v.begin(), v.end());
long long answer = 0;
for (int cnt_x = 1; cnt_x < n; cnt_x++)
for (int x : occ[cnt_x])
for (int cnt_y = 1; cnt_y <= cnt_x; cnt_y++)
for (auto y : occ[cnt_y])
if (x != y && !binary_search(bad_pairs.begin(), bad_pairs.end(), pair<int, int>{x, y})) {
answer = max(answer, 1ll * (cnt_x + cnt_y) * (x + y));
break;
}
cout << answer << '\n';
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int tests;
cin >> tests;
while (tests--)
solve();
}
1637F - Towers
Idea: TeaTime.
Find the answer when heights of all vertices are equal to $$$1$$$.
Consider tree where all heights are either $$$1$$$ or $$$0$$$. What is the answer in this case?
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
ll n;
vector<vector<ll>> gr;
vector<ll> vec;
void input() {
cin >> n;
vec.resize(n);
for (auto& c : vec) cin >> c;
gr.resize(n);
for (int i = 0; i < n - 1; i++) {
ll u, v;
cin >> u >> v;
u--; v--;
gr[u].push_back(v);
gr[v].push_back(u);
}
}
ll sol() {
ll ans = 0;
set<pair<ll, ll>> leaves;
vector<pair<ll, ll>> srt;
vector<ll> degree(n);
srt.push_back({ 0, -1 });
for (int i = 0; i < n; i++) {
degree[i] = gr[i].size();
srt.push_back({ vec[i], i });
if (gr[i].size() == 1) {
leaves.insert({vec[i], i});
}
}
sort(srt.begin(), srt.end());
for (int i = 1; i <= n; i++) {
while (leaves.size() > 0 && (*leaves.begin()).first < srt[i].first) {
ll v = (*leaves.begin()).second;
degree[v] = -2;
leaves.erase(leaves.begin());
for (auto to : gr[v]) {
degree[to]--;
if (degree[to] == 1 || degree[to] == 0) leaves.insert({ vec[to], to });
}
}
ans += max(2ll, ll(leaves.size())) * (srt[i].first - srt[i - 1].first);
}
return ans;
}
int main() {
fastInp;
input();
cout << sol();
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n;
cin >> n;
vector<int> h(n);
for (int i = 0; i < n; ++i) cin >> h[i];
vector<vector<int>> g(n);
for (int i = 0; i + 1 < n; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
g[u].push_back(v);
g[v].push_back(u);
}
int rt = 0;
for (int i = 0; i < n; ++i) {
if (h[i] > h[rt]) {
rt = i;
}
}
ll ans = 0;
function<int(int, int)> dfs = [&](int u, int p) {
int mx1 = 0, mx2 = 0;
vector<int> have;
for (auto v : g[u]) {
if (v != p) {
int cur = dfs(v, u);
if (cur > mx1) swap(cur, mx1);
if (cur > mx2) swap(cur, mx2);
}
}
if (p != -1) {
int delta = max(0, h[u] - mx1);
ans += delta;
mx1 += delta;
} else {
ans += max(0, h[u] - mx1) + max(0, h[u] - mx2);
}
return mx1;
};
dfs(rt, -1);
cout << ans << '\n';
}
1637G - Birthday
Idea: EvgeniyPonasenkov.
It's impossible to construct a sequence of operations only when $$$n = 2$$$.
Answer is the smallest power of two which is at least $$$n$$$.
Try to transform all numbers into the powers of two (maybe different).
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> ops;
vector<int> a;
void rec(int n, int coeff) {
if (n <= 2) {
for (int i = 1; i <= n; i++)
a.push_back(i * coeff);
return;
}
int p = 1;
while (p * 2 <= n) p *= 2;
if (p == n) {
a.push_back(n * coeff);
n--, p /= 2;
}
a.push_back(p * coeff);
for (int i = p + 1; i <= n; i++) {
a.push_back(2 * p * coeff);
ops.emplace_back(i * coeff, (2 * p - i) * coeff);
}
rec(2 * p - n - 1, coeff);
rec(n - p, coeff * 2);
}
void solve() {
int n;
cin >> n;
if (n == 2) {
cout << "-1\n";
return;
}
ops.clear();
a.clear();
rec(n, 1);
sort(a.begin(), a.end());
int answer = 1;
while (answer < n)
answer *= 2;
for (int i = 0;; i++)
if (a[i] == a[i + 1]) {
assert(a[i] != answer);
ops.emplace_back(a[i], a[i]);
a[i + 1] *= 2;
a.erase(a.begin() + i);
break;
}
for (auto x : a)
while (x != answer) {
ops.emplace_back(0, x);
ops.emplace_back(x, x);
x *= 2;
}
ops.emplace_back(0, answer);
cout << ops.size() << '\n';
for (auto &[x, y] : ops)
cout << x << ' ' << y << '\n';
}
int main() {
int tests;
cin >> tests;
while (tests--)
solve();
}
1637H - Minimize Inversions Number
Idea: Mangooste.
We have a proof that for each length, in the optimal sequence the following condition is satisfied: if the element $$$i$$$ is selected, then all elements $$$j > i$$$ and $$$p_j < p_i$$$ are also selected.
Let $$$d_i$$$ is a number by which the number of inversions will decrease after moving only the element with index $$$i$$$ to the beginning. Then, if sequence $$$seq$$$ is selected, then the number of inversions in a new permutation will be equal to $$$invs - \sum_{i \in seq} d_i + seqInvs - (\frac{|seq| \cdot (|seq| - 1)}{2} - seqInvs) = invs - \sum_{i \in seq} d_i + 2 \cdot seqInvs - \frac{|seq| \cdot (|seq| - 1)}{2}$$$. Here $$$invs$$$ — the number of inversions in the initial permutation, and $$$seqInvs$$$ — the number of inversions over all elements in the $$$seq$$$.
Assume that the number of inversions equals to $$$invs - \sum_{i \in seq} c_i - \frac{|seq| \cdot (|seq| - 1)}{2}$$$. What is $$$c_i$$$?
If $$$i > j$$$ and $$$p_i > p_j$$$ then $$$c_i < c_j$$$. So for the length $$$len$$$ it's optimal to choose $$$len$$$ maxmum elements by the value of $$$c_i$$$.
#include <bits/stdc++.h>
using namespace std;
struct binary_index_tree {
int n;
vector<int> bit;
binary_index_tree(int n) : n(n), bit(n + 1) {}
void increase(int pos) {
for (pos++; pos <= n; pos += pos & -pos)
bit[pos]++;
}
int query(int pref) const {
int sum = 0;
for (; pref; pref -= pref & -pref)
sum += bit[pref];
return sum;
}
};
void solve() {
int n;
cin >> n;
vector<int> d(n);
binary_index_tree bit(n);
long long inversions = 0;
for (int i = 0; i < n; i++) {
int p;
cin >> p;
p--;
d[i] = i - 2 * p;
inversions += i - bit.query(p);
bit.increase(p);
}
sort(d.rbegin(), d.rend());
cout << inversions;
long long sum = 0;
for (int i = 0; i < n; i++) {
sum += d[i];
cout << ' ' << inversions - sum - 1ll * i * (i + 1) / 2;
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int tests;
cin >> tests;
while (tests--)
solve();
}