Thank you for participating, we hope you enjoyed the problems! We also ask that you rate each of the round's problems in the corresponding spoiler in order to improve the quality of future contests.
All problems were prepared by Alexdat2000 with the help of coauthors.
1634A - Reverse and Concatenate
Idea: sevlll777
Hint 1
What property will the string have after the first operation (regardless of the type of operation)?
Hint 2
What happens if you apply the operation to a palindrome?
Tutorial
Tutorial is loading...
Solution
q = int(input())
for _ in range(q):
n, k = map(int, input().split())
s = input()
if s == s[::-1] or k == 0:
print(1)
else:
print(2)
1634B - Fortune Telling
Idea: crazyilian and antontrygubO_o
Hint 1
Try solving the problem <
Hint 2
What do the numbers $$$a \oplus b$$$ and $$$a + b$$$ have in common for any numbers $$$a,b$$$?
Hint 3
What do all the numbers that can be obtained by all operations starting with $$$x$$$ have in common? Does the set of these numbers intersect with the set of numbers that can be obtained starting with $$$x + 3$$$?
Tutorial
Tutorial is loading...
Solution
def main():
n, x, y = map(int, input().split())
a = list(map(int, input().split()))
if (sum(a) + x + y) % 2 == 0:
print('Alice')
else:
print('Bob')
for _ in range(int(input())):
main()
1634C - OKEA
Idea: sevlll777
Hint 1
If $$$k > 1$$$, for which $$$n$$$ is there no solution?
Hint 1.1
For which $$$n$$$ is there no solution when $$$k = 2$$$? Is it true for other $$$k > 1$$$?
Hint 2
Note that an array $$$[1, 3, 5, 7, 9, ...]$$$ will satisfy the condition (the arithmetic mean of each segment is an integer), since the sum of the first $$$X$$$ elements of this array is $$$X^2$$$. Try to generalize this case and find other arrays that satisfy the condition.
Tutorial
Tutorial is loading...
Solution
def solve():
n, k = map(int, input().split())
if k == 1:
print("YES")
for i in range(1, n + 1):
print(i)
return
if n % 2 == 1:
print("NO")
return
print("YES")
for i in range(1, n + 1):
print(*[i for i in range(i, n * k + 1, n)])
for _ in range(int(input())):
solve()
1634D - Finding Zero
Idea: sevlll777
Hint 1
The problem can be reworded as "Find $$$n - 2$$$ indexes that definitely can't contain zero".
Hint 2
Solve the problem for $$$n = 4$$$.
Hint 2.1
Denote as $$$f(i)$$$ — the answer to the query for three indices different from $$$i$$$. How, knowing $$$f(1)$$$, $$$f(2)$$$, $$$f(3)$$$, $$$f(4)$$$, understand which two indexes cannot contain zero? Note that there is exactly one zero in the array.
Hint 3
Solve the problem for even $$$n$$$ using solution for $$$n = 4$$$.
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define len(x) (int) (x).size()
using namespace std;
int get(const vector <int>& x) {
cout << "? " << x[0] + 1 << " " << x[1] + 1 << " " << x[2] + 1 << endl;
int ans;
cin >> ans;
return ans;
}
signed main() {
ios_base::sync_with_stdio();
cin.tie(nullptr);
int n;
cin >> n;
pair <int, int> possible = {0, 1};
for (int i = 2; i < n - 1; i += 2) {
vector <pair <int, int>> ch(4);
vector <int> now = {possible.first, possible.second, i, i + 1};
for (int j = 0; j < 4; j++) {
vector <int> x = now;
x.erase(x.begin() + j);
ch[j] = {get(x), now[j]};
}
sort(all(ch));
possible = {ch[0].second, ch[1].second};
}
if (n % 2 == 1) {
int other = 0;
while (possible.first == other || possible.second == other) {
other++;
}
vector <pair <int, int>> ch(4);
vector <int> now = {possible.first, possible.second, n - 1, other};
for (int j = 0; j < 4; j++) {
vector <int> x = now;
x.erase(x.begin() + j);
ch[j] = {get(x), now[j]};
}
sort(all(ch));
possible = {ch[0].second, ch[1].second};
}
cout << "! " << possible.first + 1 << " " << possible.second + 1 << endl;
return 0;
}
1634E - Fair Share
Idea: sevlll777
Hint 1
In what cases is the answer definitely NO?
Hint 2
The lengths of all arrays are even numbers, and each number appears an even number of times in total. There are suspiciously many even numbers...
Hint 3
An Euler circuit is a circuit that passes through all edges of a graph exactly once. It turns out that Euler circuit exists only in those graphs with degree of each vertex even.
Hint 4
Construct some graph such that the degree of each of its vertices is even, find a directed Eulerian circuit in it, and reconstruct the answer to the problem using this circuit. What do the edges of such graph correspond to?
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define len(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define endl "\n"
using namespace std;
const int N = 4e5 + 100, H = 2e5 + 50;
vector <pair <int, int>> g[N];
string ans[N];
int pos[N];
void dfs(int v) {
if (pos[v] == 0) {
ans[v] = string(len(g[v]), 'L');
}
while (pos[v] < len(g[v])) {
auto [i, ind] = g[v][pos[v]];
if (i == -1) {
pos[v]++;
continue;
}
g[i][ind].first = -1, g[v][pos[v]].first = -1;
if (v < H) {
ans[v][pos[v]] = 'R';
}
pos[v]++;
dfs(i);
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m;
cin >> m;
map <int, int> ind, cnt;
int fre_ind = 0;
vector <vector <int>> nums(m);
for (int i = 0; i < m; i++) {
int n;
cin >> n;
for (int _ = 0; _ < n; _++) {
int x;
cin >> x;
if (!ind.count(x)) {
ind[x] = fre_ind++;
}
x = ind[x];
cnt[x]++;
nums[i].push_back(x);
g[i].emplace_back(x + H, len(g[x + H]));
g[x + H].emplace_back(i, len(g[i]) - 1);
}
}
for (auto [num, cn] : cnt) {
if (cn % 2 == 1) {
cout << "NO" << endl;
return 0;
}
}
for (int i = 0; i < N; i++) {
dfs(i);
}
cout << "YES" << endl;
for (int i = 0; i < m; i++) {
cout << ans[i] << endl;
}
return 0;
}
1634F - Fibonacci Additions
Idea: Mangooste
Hint 1
Let array $$$C_i = A_i - B_i$$$. Perform all operations on array $$$C_i$$$.
Hint 2
Suppose you want to add not Fibonacci numbers, but any number $$$x$$$ to the whole segment of the query. Can you solve the problem in such a case without using heavy structures such as a segment tree?
Hint 3
Generalize the idea from hint 2 using the main property of Fibonacci numbers ($$$F_i = F_{i-1} + F_{i-2}$$$).
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define len(x) (int) (x).size()
#define endl "\n"
#define int long long
using namespace std;
const int N = 3e5 + 100;
int MOD;
int fib[N];
vector <int> unfib;
int notzero = 0;
void upd(int ind, int delta) {
notzero -= (unfib[ind] != 0);
unfib[ind] += delta;
if (unfib[ind] >= MOD) {
unfib[ind] -= MOD;
};
notzero += (unfib[ind] != 0);
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, q;
cin >> n >> q >> MOD;
fib[0] = fib[1] = 1;
for (int i = 2; i < N; i++) {
fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
}
vector <int> delta(n);
for (int& i : delta) {
cin >> i;
}
for (int i = 0; i < n; i++) {
int x;
cin >> x;
delta[i] = (delta[i] - x + MOD) % MOD;
}
unfib.resize(n);
unfib[0] = delta[0];
if (len(unfib) >= 2) {
unfib[1] = (delta[1] - delta[0] + MOD) % MOD;
}
for (int i = 2; i < n; i++) {
unfib[i] = ((long long) delta[i] - delta[i - 1] - delta[i - 2] + MOD * 2) % MOD;
}
for (int i = 0; i < n; i++) {
notzero += (unfib[i] != 0);
}
while (q--) {
char c;
int l, r;
cin >> c >> l >> r;
if (c == 'A') {
upd(l - 1, 1);
if (r != n) {
upd(r, MOD - fib[r - l + 1]);
}
if (r < n - 1) {
upd(r + 1, MOD - fib[r - l]);
}
} else {
upd(l - 1, MOD - 1);
if (r != n) {
upd(r, fib[r - l + 1]);
}
if (r < n - 1) {
upd(r + 1, fib[r - l]);
}
}
if (!notzero) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
return 0;
}
