Thank you for participating! We hope you enjoyed the problems!
1805A - We Need the Zero
Idea and preparation: Alexdat2000
Hint 1
Recall the basic properties of the $$$\oplus$$$ operation: $$$A \oplus 0 = A$$$, $$$A \oplus A = 0$$$, $$$A \oplus B = B \oplus A$$$.
Hint 2
Consider the cases of even and odd array lengths.
Editorial
Tutorial is loading...
Solution
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
xor = 0
for x in a:
xor ^= x
if xor == 0:
print(0)
else:
if n % 2 == 1:
print(xor)
else:
print(-1)
1805B - The String Has a Target
Idea and preparation: Alexdat2000
Hint 1
What should be the first character if we are trying to make the string lexicographically minimal?
Hint 2
Consider the string «baba». If you choose $$$i=2$$$, you get the string «abba», and if you choose $$$i=4$$$ you get «abab». Try to generalize this reasoning to any string.
Editorial
Tutorial is loading...
Solution
for _ in range(int(input())):
n = int(input())
s = input()
ind = s.rfind(min(s)) # Find the last ind such that s[ind] = min(s)
print(s[ind] + s[:ind] + s[ind + 1:])
1805C - Place for a Selfie
Idea and preparation: Alexdat2000
Hint 1
Note that the distance between the line and the parabola will also be a parabola. Then what is the condition that the line and the parabola have no common points?
Hint 2
Recall the discriminant formula from school: If a parabola $$$ax^2 + bx + c$$$ is given, then calculate $$$D=b^2 - 4ac$$$ (discriminant). Then, if $$$D > 0$$$, the parabola has $$$2$$$ roots, if $$$D=0$$$, it has one root, if $$$D<0$$$, it has no roots.
Hint 3
If we choose the parabola $$$ax^2 + bx + c$$$, then the lines with such coefficient $$$k$$$ that $$$(b-k)^2<4ac$$$ have no common points with it. How can we find such $$$k$$$ among the given lines?
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector <int> lines(n);
for (int i = 0; i < n; i++) {
cin >> lines[i];
}
sort(lines.begin(), lines.end());
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
int ind = lower_bound(lines.begin(), lines.end(), b) - lines.begin();
if (ind < n && (lines[ind] - b) * (lines[ind] - b) < 4 * a * c) {
cout << "YES\n" << lines[ind] << "\n";
continue;
}
if (ind > 0 && (lines[ind - 1] - b) * (lines[ind - 1] - b) < 4 * a * c) {
cout << "YES\n" << lines[ind - 1] << "\n";
continue;
}
cout << "NO\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q = 1;
cin >> q;
while (q--) {
solve();
}
return 0;
}
1805D - A Wide, Wide Graph
Idea: FairyWinx, preparation: Alexdat2000
Hint 1
At what maximal $$$k$$$ does the graph $$$G_k$$$ not decompose into single components? What happens if we decrease $$$k$$$ by $$$1$$$?
Hint 2
Consider some diameter of a tree (the path of the longest length). If in the graph $$$G_k$$$ a vertex has a neighbor, then it is also connected by an edge to one of the ends of the diameter. How can we use this fact to find the answer for $$$k$$$ if we know the components of graph $$$G_{k+1}$$$?
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
const int N = 1e5 + 228;
vector<int> G[N];
void dfs(int v, int par, int h, vector<int> &d) {
d[v] = h;
for (int i : G[v]) {
if (i != par) {
dfs(i, v, h + 1, d);
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n - 1; ++i) {
int a, b;
cin >> a >> b;
G[a - 1].push_back(b - 1);
G[b - 1].push_back(a - 1);
}
vector<int> d1(n), d2(n);
dfs(0, -1, 0, d1);
int a = max_element(all(d1)) - d1.begin();
dfs(a, -1, 0, d1);
int b = max_element(all(d1)) - d1.begin();
dfs(b, -1, 0, d2);
for (int i = 0; i < n; ++i) {
d2[i] = max(d2[i], d1[i]);
}
sort(all(d2));
int ans = 0;
for (int i = 1; i <= n; ++i) {
while (ans < n && d2[ans] < i) {
++ans;
}
cout << min(n, ans + 1) << ' ';
}
cout << '\n';
}
1805E - There Should Be a Lot of Maximums
Idea and preparation: Alexdat2000
Hint 1
Let $$$M$$$ — $$$MAD$$$ of the whole tree. What is the answer if there are many vertices with value $$$M$$$ in the tree?
Hint 2
Note that for many edges the answer is $$$M$$$. And for which edges is it not so?
Hint 3
Let the tree have only two vertices with value $$$M$$$. Then for the edges not on the path between them we know the answer. What about the path between two vertices of $$$M$$$? Can we walk along it by calculating the answer for all vertices?
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 100;
vector <pair <int, int>> g[N];
int val[N];
vector <int> ans;
map <int, int> cnt1, cnt2;
set <int> mad1, mad2;
vector <int> path, path_ind;
bool used[N];
bool dfs(int v, int tar) {
used[v] = true;
path.push_back(v);
if (v == tar) {
return true;
}
for (auto [i, ind] : g[v]) {
if (!used[i]) {
path_ind.push_back(ind);
if (dfs(i, tar)) {
return true;
}
path_ind.pop_back();
}
}
path.pop_back();
return false;
}
int mad() {
int mx = 0;
if (!mad1.empty()) {
mx = max(mx, *mad1.rbegin());
}
if (!mad2.empty()) {
mx = max(mx, *mad2.rbegin());
}
return mx;
}
void recalc(int v, int ban1, int ban2) {
cnt1[val[v]]++;
if (cnt1[val[v]] == 2) {
mad1.insert(val[v]);
}
cnt2[val[v]]--;
if (cnt2[val[v]] == 1) {
mad2.erase(val[v]);
}
for (auto [i, _] : g[v]) {
if (i != ban1 && i != ban2) {
recalc(i, v, -1);
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
a--, b--;
g[a].emplace_back(b, i);
g[b].emplace_back(a, i);
}
map <int, vector <int>> ind;
for (int i = 0; i < n; i++) {
cin >> val[i];
ind[val[i]].push_back(i);
cnt2[val[i]]++;
if (cnt2[val[i]] == 2) {
mad2.insert(val[i]);
}
}
while (!ind.empty() && ind.rbegin() -> second.size() == 1) {
ind.erase(prev(ind.end()));
}
if (ind.empty()) {
for (int i = 0; i < n - 1; i++) {
cout << "0\n";
}
return 0;
} else if (ind.rbegin()->second.size() > 2) {
for (int i = 0; i < n - 1; i++) {
cout << ind.rbegin() -> first << "\n";
}
return 0;
}
int a = ind.rbegin()->second[0], b = ind.rbegin()->second[1];
dfs(a, b);
ans.assign(n - 1, ind.rbegin() -> first);
recalc(path[0], path[1], -1);
ans[path_ind[0]] = mad();
for (int i = 1; i + 1 < path.size(); i++) {
recalc(path[i], path[i - 1], path[i + 1]);
ans[path_ind[i]] = mad();
}
for (int i : ans) {
cout << i << "\n";
}
return 0;
}
1805F2 - Survival of the Weakest (hard version)
Idea and preparation: sevlll777
Hints for the simple version:
Hint 1
Figure out how to implement the function $$$F$$$ in $$$O(n log n)$$$
Hint 1.1
You'll need $$$std::priority\_queue$$$ or $$$std::set$$$
Hint 2
If you run $$$F$$$ for $$$O(n log n)$$$ $$$n - 1$$$ times, we'll get the solution in $$$O(n^2 log n)$$$. However, the numbers in the array can grow very fast. Can you somehow modify the numbers in the array so that $$$F$$$ changes in a predictable way?
Hint 2.2
$$$F([a_1, a_2, \ldots, a_n]) = F([a_1 - x, a_2 - x, \ldots, a_n - x]) + x \cdot 2^{n-1}$$$
Hints for the hard version:
Hint 3
How to solve the problem if $$$a_i \leq 1$$$? $$$\leq 2$$$? Can you notice anything about these solutions?
Hint 4
If $$$n$$$ is large enough, then $$$F(F(\ldots F([a_1, a_2, \ldots, a_n])\ldots)) = F(F( \ldots F([a_1, a_2, \ldots, a_{n-1}, X])\ldots))$$$ where $$$X$$$ any number $$$\geq a_{n-1}$$$, in other words: the largest element is useless for the final answer
Hint 5
Only a small number of the smallest elements of the original array will affect the answer
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define all(x) x.begin(), (x).end()
using namespace std;
const int M = 1000000007;
long long ans = 0;
int real_len = 0;
long long binpow(long long a, int x) {
long long ans0 = 1;
while (x) {
if (x % 2) {
ans0 *= a;
ans0 %= M;
}
a *= a;
a %= M;
x /= 2;
}
return ans0;
}
void chill(vector<int> &b) {
int mn = b[0];
ans += (int) ((long long) mn * binpow(2, real_len - 1) % M);
if (ans >= M) {
ans -= M;
}
for (auto &x : b) {
x -= mn;
}
}
void F(vector<int> &b, int sub = 0) {
--real_len;
vector<int> cnd;
for (int i = 0; i < b.size(); i++) {
for (int j = i + 1; j < b.size(); j++) {
if (i * j >= b.size()) break;
cnd.push_back(b[i] + b[j]);
}
}
sort(all(cnd));
vector<int> b2((int) b.size() - sub);
for (int i = 0; i < (int) b.size() - sub; i++) {
b2[i] = cnd[i];
}
chill(b2);
b = b2;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(all(a));
int L = 64;
vector<int> b(min(n, L));
for (int i = 0; i < min(n, L); i++) {
b[i] = a[i];
}
real_len = n;
chill(b);
while (b.size() < real_len) {
if (b[1] + b[2] > b.back()) {
F(b, 1);
F(b, 1);
} else {
F(b);
}
}
while (real_len > 1) {
F(b, 1);
}
ans += b[0];
ans %= M;
cout << ans << '\n';
}
