Thank you for participating, we hope you enjoyed the problems! We kindly ask you to 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 an 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
Can you figure out which of your friends can't get the number $$$y$$$ regardless of the order of operations? The answer to the problem would be the other person, since the jury guarantees that exactly one of your friends could get it.
Hint 2
What do the numbers $$$a \oplus b$$$ and $$$a + b$$$ have in common for any $$$a, b$$$?
Hint 3
What do all the numbers that can be obtained by all combinations of 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$$$? Does the same rule of thumb hold for other $$$k > 1$$$?
Hint 2
Note that the array $$$[1, 3, 5, 7, 9, ...]$$$ satisfies the requirements (that is, the arithmetic mean of each subsegment is an integer) because the sum of the first $$$X$$$ elements of this array is $$$X^2$$$. Try to generalize this special case and find other arrays that satisfy the conditions.
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 follows: find $$$n - 2$$$ indices that definitely can't contain a zero.
Hint 2
Solve the problem for $$$n = 4$$$.
Hint 2.1
For $$$n = 4$$$, denote by $$$\bar{i}$$$ the answer to the query for the three indices except $$$i$$$. Knowing $$$\bar{1}$$$, $$$\bar{2}$$$, $$$\bar{3}$$$, and $$$\bar{4}$$$, can you find two indexes that don't contain zero for certain? Use the fact that there is exactly one zero in the array.
Hint 3
Solve the problem for even $$$n$$$ using the 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 (or a union of several circuits if the graph is disconnected). It turns out that an Euler circuit exists if and only if the degree of each vertex is 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 $$$C_i = A_i - B_i$$$. Perform all operations on the array $$$C$$$.
Hint 2
Nevermind Fibonacci and suppose the operation was to increase the elements of a given subsegment by a given constant. Can you solve this problem without using heavy data structures like segment tree?
Hint 3
Generalize the idea from hint 2 using the characteristic 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;
}
