Thank you for participating!
1979A - Guess the Maximum
Let $$$m$$$ be the maximum among the numbers $$$a_i, a_{i + 1},\ldots, a_j$$$. Notice that there always exists such $$$k$$$ that $$$i \le k < j$$$ and $$$a_k = m$$$ or $$$a_{k + 1} = m$$$. Therefore, we can assume that Bob always chooses the pair of numbers $$$p$$$ and $$$p + 1$$$ ($$$1 \le p < n$$$) as $$$i$$$ and $$$j$$$.
Therefore you need to consider the maximums in pairs of adjacent elements and take the minimum among them. Let $$$min$$$ be the found minimum, then it is obvious that the answer is equal to $$$min - 1$$$.
#include <iostream>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int a[n];
for (int& i : a) {
cin >> i;
}
int mini = max(a[0], a[1]);
for (int i = 1; i < n - 1; i++) {
mini = min(mini, max(a[i], a[i + 1]));
}
cout << mini - 1 << "\n";
}
}
1979B - XOR Sequences
Look at samples.
Consider two numbers $$$v$$$ and $$$u$$$ such that $$$x \oplus v = y \oplus u$$$. Then consider the numbers $$$x \oplus (v + 1)$$$ and $$$y \oplus (u + 1)$$$. Let's look at the last bit of $$$v$$$ and $$$u$$$. Possible scenarios:
- Both bits are equal to $$$0$$$ — adding one will change the bits at the same positions, therefore $$$x \oplus (v + 1) = y \oplus (u + 1)$$$;
- Both bits are equal to $$$1$$$ — adding one will change the bits at the same positions and also add one to the next bit, therefore we can similarly consider the next bit;
- Bits are different — adding one to the zero bit will only change one bit, while the subsequent bit of the other number will be changed. This means that $$$x \oplus (v + 1) \neq y \oplus (u + 1)$$$.
It is clear that we need to maximize the number of zeros in the maximum matching suffix of $$$u$$$ and $$$v$$$. Obviously, this number is equal to the maximum matching suffix of $$$x$$$ and $$$y$$$. Let $$$k$$$ be the length of the maximum matching suffix of $$$x$$$ and $$$y$$$, then the answer is $$$2^k$$$.
This can be calculated in $$$O(\log C)$$$ time for one test case, where $$$C$$$ is the limit on $$$x$$$ and $$$y$$$.
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int a, b;
cin >> a >> b;
for (int i = 0; i < 30; i++) {
if ((a & (1 << i)) != (b & (1 << i))) {
cout << (1ll << i) << "\n";
break;
}
}
}
}
1979C - Earning on Bets
Try to come up with a condition for the existence of an answer.
Let $$$S$$$ be the total amount of coins placed on all possible outcomes. Then, if the coefficient for winning is $$$k_i$$$, we have to place more than $$$\frac{S}{k_i}$$$ on this outcome.
We can obtain the following inequality:
Dividing both sides by $$$S$$$, we obtain the necessary and sufficient condition for the existence of an answer:
This check can be performed by reducing all fractions to a common denominator. Notice that the numerators of the reduced fractions correspond to the required bets on the outcomes.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int gcd(int a, int b) {
while (b != 0) {
int tmp = a % b;
a = b;
b = tmp;
}
return a;
}
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
void solve() {
int n;
cin >> n;
vector <int> k(n);
for (int i = 0; i < n; i++) {
cin >> k[i];
}
int z = 1;
for (int i = 0; i < n; i++) {
z = lcm(z, k[i]);
}
int suma = 0;
for (int i = 0; i < n; i++) {
suma += z / k[i];
}
if (suma < z) {
for (int i = 0; i < n; i++) {
cout << z / k[i] << " ";
}
cout << "\n";
} else {
cout << -1 << "\n";
}
}
signed main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
1979D - Fixing a Binary String
Let's consider the block of characters at the end. Notice that their quantity cannot decrease. Let $$$x$$$ be the number of identical characters at the end; there are three possible cases:
- $$$x = k$$$ — it is enough to find any block of length greater than $$$k$$$ and separate a block of length $$$k$$$ from it;
- $$$x > k$$$ — obviously, there is no solution;
- $$$x < k$$$ — find a block of length $$$k - x$$$ or $$$2k - x$$$ and separate a block of length $$$k - x$$$ from it.
This solution works in $$$O(n)$$$, but it is not the only correct one. Your solution may differ significantly from the one proposed.
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
string s;
cin >> s;
int x = 0;
for (int i = n - 1; i >= 0; i--) {
if (s[i] == s[n - 1]) {
x++;
} else {
break;
}
}
auto check = [&]() {
for (int i = 0; i < k; i++) {
if (s[i] != s[0]) return false;
}
for (int i = 0; i + k < n; i++) {
if (s[i] == s[i + k]) return false;
}
return true;
};
auto operation = [&](int p) {
reverse(s.begin(), s.begin() + p);
s = s.substr(p, (int)s.size() - p) + s.substr(0, p);
if (check()) {
cout << p << "\n";
} else {
cout << -1 << "\n";
}
};
if (x == k) {
int p = n;
for (int i = n - 1 - k; i >= 0; i--) {
if (s[i] == s[i + k]) {
p = i + 1;
break;
}
}
operation(p);
} else if (x > k) {
cout << -1 << "\n";
} else {
bool was = false;
for (int i = 0; i < n; i++) {
if (s[i] != s.back()) continue;
int j = i;
while (j + 1 < n && s[i] == s[j + 1]) {
j++;
}
if (j - i + 1 + x == k) {
operation(j + 1);
was = true;
break;
} else if (j - i + 1 - k + x == k) {
operation(i + k - x);
was = true;
break;
}
i = j;
}
if (!was) {
operation(n);
}
}
}
}
1979E - Manhattan Triangle
In every Manhattan triangle there are two points such that $$$|x_1 - x_2| = |y_1 - y_2|$$$.
Note this fact: in every Manhattan triangle there are two points such that $$$|x_1 - x_2| = |y_1 - y_2|$$$.
Let's start with distributing all points with their $$$(x + y)$$$ value.
For each point $$$(x; y)$$$ find point $$$(x + d / 2; y - d / 2)$$$ using lower bound method in corresponding set. Then we have to find the third point: it can be in either $$$(x + y + d)$$$ or $$$(x + y - d)$$$ diagonal. Borders at $$$x$$$ coordinate for them are $$$[x + d / 2; x + d]$$$ and $$$[x - d / 2; x]$$$ — it can be found using the same lower bound method.
Then, distribute all points with $$$(x - y)$$$ value and do the same algorithm.
Total time complexity is $$$O(n \log n)$$$.
#include <bits/stdc++.h>
using namespace std;
const int MAXC = 1e5;
const int MAXD = 4e5 + 10;
set <pair <int, int>> diag[MAXD];
void solve() {
int n, d;
cin >> n >> d;
vector <int> x(n), y(n);
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
x[i] += MAXC;
y[i] += MAXC;
}
bool found = false;
{
for (int i = 0; i < n; i++) {
diag[x[i] + y[i]].insert({x[i], i});
}
for (int i = 0; i < n; i++) {
auto it1 = diag[x[i] + y[i]].lower_bound({x[i] + d / 2, -1});
if (it1 == diag[x[i] + y[i]].end() || it1->first != x[i] + d / 2) continue;
if (x[i] + y[i] + d < MAXD) {
auto it2 = diag[x[i] + y[i] + d].lower_bound({x[i] + d / 2, -1});
if (it2 != diag[x[i] + y[i] + d].end() && it2->first <= it1->first + d / 2) {
cout << i + 1 << " " << it1->second + 1 << " " << it2->second + 1 << "\n";
found = true;
break;
}
}
if (x[i] + y[i] - d >= 0) {
auto it2 = diag[x[i] + y[i] - d].lower_bound({x[i] - d / 2, -1});
if (it2 != diag[x[i] + y[i] - d].end() && it2->first <= it1->first - d / 2) {
cout << i + 1 << " " << it1->second + 1 << " " << it2->second + 1 << "\n";
found = true;
break;
}
}
}
for (int i = 0; i < n; i++) {
diag[x[i] + y[i]].erase({x[i], i});
}
}
if (!found) {
for (int i = 0; i < n; i++) {
y[i] -= 2 * MAXC;
diag[x[i] - y[i]].insert({x[i], i});
}
for (int i = 0; i < n; i++) {
auto it1 = diag[x[i] - y[i]].lower_bound({x[i] + d / 2, -1});
if (it1 == diag[x[i] - y[i]].end() || it1->first != x[i] + d / 2) continue;
if (x[i] - y[i] + d < MAXD) {
auto it2 = diag[x[i] - y[i] + d].lower_bound({x[i] + d / 2, -1});
if (it2 != diag[x[i] - y[i] + d].end() && it2->first <= it1->first + d / 2) {
cout << i + 1 << " " << it1->second + 1 << " " << it2->second + 1 << "\n";
found = true;
break;
}
}
if (x[i] - y[i] - d >= 0) {
auto it2 = diag[x[i] - y[i] - d].lower_bound({x[i] - d / 2, -1});
if (it2 != diag[x[i] - y[i] - d].end() && it2->first <= it1->first - d / 2) {
cout << i + 1 << " " << it1->second + 1 << " " << it2->second + 1 << "\n";
found = true;
break;
}
}
}
for (int i = 0; i < n; i++) {
diag[x[i] - y[i]].erase({x[i], i});
}
}
if (!found) {
cout << "0 0 0\n";
}
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
1979F - Kostyanych's Theorem
Let's consider the following recursive algorithm. We will store the Hamiltonian path as a double-ended queue, maintaining the start and end.
In case there are only $$$1$$$ or $$$2$$$ vertices left in the graph, the problem is solved trivially.
Suppose we know that the current graph has $$$n$$$ vertices, and there are at most $$$(n - 2)$$$ edges missing. Then the total number of edges in such a graph is at least
Let all vertices in the graph have a degree of at least $$$(n - 3)$$$, then the total number of edges does not exceed
which is less than the stated value. Hence, we conclude that there is at least one vertex with a degree greater than $$$(n - 3)$$$.
If there exists a vertex $$$v$$$ with a degree of $$$(n - 2)$$$, then it is sufficient to run our recursive algorithm for the remaining graph. Since $$$v$$$ is only not connected by an edge to one vertex, $$$v$$$ is connected either to the start or the end of the maintained path in the remaining graph. Thus, we can insert the vertex $$$v$$$ either at the beginning or at the end of the path.
Otherwise, let $$$u$$$ be the vertex with a degree of $$$(n - 1)$$$. There is at least one vertex $$$w$$$ with a degree not exceeding $$$(n - 3)$$$. Remove $$$u$$$ and $$$w$$$ from the graph. Notice that the number of edges in such a graph does not exceed
The invariant is preserved, so we can run the algorithm for the remaining graph. Then, we can arrange the vertices in the following order: $$$w$$$ — $$$u$$$ — $$$s$$$ — ..., where $$$s$$$ — the start of the Hamiltonian path in the remaining graph.
It remains to understand how to use queries.
Make a query $$$d = (n - 2)$$$. Let $$$u$$$ be the second number in the response to our query. If $$$u \neq 0$$$, the degree of vertex $$$v$$$ is $$$(n - 2)$$$. Run our recursive algorithm, and then compare the start and end of the obtained path with $$$u$$$.
Otherwise, if $$$u = 0$$$, it means the degree of vertex $$$v$$$ is $$$(n - 1)$$$. In this case, ask about any vertex with a low degree (this can be done with a query $$$d = 0$$$). Then simply arrange the vertices in the order mentioned above.
We will make no more than $$$n$$$ queries, and the final asymptotic will be $$$O(n)$$$.
#include <bits/stdc++.h>
using namespace std;
pair <int, int> ask(int d) {
cout << "? " << d << endl;
int v, u;
cin >> v >> u;
return {v, u};
}
pair <int, int> get(int n, vector <int>& nxt) {
if (n == 1) {
int v = ask(0).first;
return {v, v};
}
if (n == 2) {
int u = ask(0).first;
int v = ask(0).first;
nxt[u] = v;
return {u, v};
}
pair <int, int> t = ask(n - 2);
int v = t.first;
int ban = t.second;
if (ban != 0) {
pair <int, int> res = get(n - 1, nxt);
if (ban != res.first) {
nxt[v] = res.first;
return {v, res.second};
} else {
nxt[res.second] = v;
return {res.first, v};
}
} else {
int u = ask(0).first;
nxt[u] = v;
pair <int, int> res = get(n - 2, nxt);
nxt[v] = res.first;
return {u, res.second};
}
}
void solve() {
int n;
cin >> n;
vector <int> nxt(n + 1, -1);
pair <int, int> ans = get(n, nxt);
int v = ans.first;
cout << "! ";
do {
cout << v << " ";
v = nxt[v];
} while (v != -1);
cout << endl;
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}