We hope you enjoyed the problems! Thank you for participating in the contest! We would love to hear your feedback in the comments.
2071A - Игра никогда не заканчивается
When Fofo is the spectator of the first match, what is the earliest subsequent game in which he will spectate again?
Suppose Sosai wins the first game. What becomes clear?
Once the winner of the first match is decided, the rest of the game is completely predictable.
For example, if Hohai wins the first match which Fofo spectated, we can see that:
No matter who wins in the second match, Hohai won't be able to continue playing in the third match (even if he wins the second match) since he has already played two times in a row. Similarly, Fofo won't be able to play in the fourth match because he has already played twice in a row, regardless of the match result.
As a result, Fofo won't be able to spectate in the $$$k$$$-th match for any $$$k$$$ of the form $$$3x + 1$$$.
The overall time complexity is: $$$O(1)$$$.
#include<bits/stdc++.h>
using namespace std;
void solve() {
int k;
cin >> k;
if (k % 3 == 1) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
}
Consider the identity permutation, defined by $$$p_i = i$$$. When and why does this permutation not work?
The smallest index $$$i$$$ where the issue occurs must satisfy the condition that $$$1 + \ldots + i$$$ is a perfect square. What is the simplest and most efficient way to resolve this issue?
The first observation is that if the sum $$$1 + 2 + … + n = \frac{n(n+1)}{2}$$$ is a perfect square, no valid perfect permutation exists.
To prove that a solution always exists otherwise, start with the identity permutation $$$p_i = i$$$ and iterate through indices from $$$1$$$ to $$$n$$$. We keep on iterating as long as the prefix sum till that moment isn’t a perfect square. If the prefix sum up to index $$$k$$$ becomes a perfect square, $$$\frac{k(k+1)}{2} = x^2$$$, swap $$$p_k$$$ and $$$p_{k + 1}$$$. This changes the prefix sum to $$$x^2 + 1$$$, which is not a perfect square.
To ensure this method works, we must show that $$$\frac{(k+1)(k+2)}{2}$$$ cannot also be a perfect square. Assume for contradiction that $$$\frac{(k+1)(k+2)}{2} = y^2$$$. Then:
Since $$$x \gt \frac{k}{2}$$$ (because $$$x^2 = \frac{k(k+1)}{2} \gt \frac{k^2}{4}$$$), we have:
which is a contradiction. Thus, $$$\frac{(k+1)(k+2)}{2}$$$ cannot be a perfect square, and the process can be repeated until all indices are processed, ensuring a valid permutation.
The overall time complexity is: $$$O(n)$$$.
#include<bits/stdc++.h>
using namespace std;
void solve() {
auto check = [&](int k) {
int j = sqrtl((int64_t)k * (k + 1) / 2);
return ((int64_t)j * j != (int64_t)k * (k + 1) / 2);
};
int n;
cin >> n;
if (!check(n)) {
cout << "-1\n";
return;
}
vector<int> ans(n + 1);
for (int i = 1; i <= n; i++) {
ans[i] = i;
}
int j = 0;
for (int i = 1; i <= n; i++) {
while ((int64_t)j * j < (int64_t)i * (i + 1) / 2) j++;
if ((int64_t)j * j == (int64_t)i * (i + 1) / 2) {
swap(ans[i], ans[i + 1]);
}
cout << ans[i] << " ";
}
cout << "\n";
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
}
Root the tree at vertex $$$\textrm{en}$$$. What observations can you make?
Can the cheese be placed at the vertices in a specific sequence that prevents the mouse from moving farther away from vertex $$$\textrm{en}$$$?
First, root the tree at vertex $$$\textrm{en}$$$ and approach it step by step. Observe that after processing all vertices at the largest depth $$$n−1$$$, the mouse’s current depth cannot exceed $$$n−1$$$. By repeating this process for the next largest depth $$$n−2$$$, the mouse’s depth will inevitably become $$$n−2$$$ or less. Continuing this way, we process vertices in descending order of depth until we reach the root, achieving the desired result.
The overall time complexity is: $$$O(n)$$$.
#include<bits/stdc++.h>
using namespace std;
void solve() {
int n, s, e;
cin >> n >> s >> e;
vector adj(n + 1, vector<int> ());
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v), adj[v].push_back(u);
}
vector dis(n + 1, vector<int> ());
vector<int> d(n + 1);
auto dfs = [&](auto &&self, int v, int par) -> void {
d[v] = d[par] + 1;
dis[d[v]].push_back(v);
for (int u: adj[v]) {
if (u == par) continue;
self(self, u, v);
}
};
dfs(dfs, e, 0);
for (int i = n; i >= 1; i--) {
for (int j: dis[i]) {
cout << j << " ";
}
}
cout << "\n";
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
}
2071D1 - Бесконечная последовательность (простая версия)
Try to determine the connection between $$$a_{2m}$$$ and $$$a_{2m+1}$$$ for indices where $$$2m \gt n$$$.
Try to express $$$a_{2m}$$$ as the XOR of a short prefix of terms plus at most one extra term.
For convenience, assume $$$n$$$ is odd (if not, increment $$$n$$$ and handle the edge case separately). Start by precomputing the first $$$2n$$$ terms $$$a_1, a_2, \ldots, a_{2n}$$$. For queries with indices less than or equal to $$$2n$$$, directly return the precomputed value. For $$$2m \gt n$$$, observe the following relationship
Define $$$p = a_1 \oplus a_2 \oplus \ldots \oplus a_n$$$. Notice that when $$$m \gt n$$$, we can decompose the XOR sum as:
Since $$$n$$$ is odd, the pairs $$$(a_{n + 1} \oplus a_{n + 2}), (a_{n + 3} \oplus a_{n + 4}), \ldots$$$ cancel out. This simplifies the formula to:
As a result, we can compute $$$a_m$$$ recursively by halving $$$m$$$ until $$$m \le 2n$$$, applying the parity rule at each step.
The overall time complexity is: $$$O(n+\log(m))$$$.
#include<bits/stdc++.h>
using namespace std;
void solve() {
int n;
int64_t l, r;
cin >> n >> l >> r;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
vector<int> pref(n + 1);
for (int i = 1; i <= n; i++) {
pref[i] = pref[i - 1] + a[i];
}
if (n % 2 == 0) {
n++;
int cur = pref[n / 2] & 1;
a.push_back(cur);
pref.push_back(pref.back() + cur);
}
for (int i = n + 1; i <= n * 2; i++) {
a.push_back(pref[i / 2] & 1);
pref.push_back(pref[i - 1] + a[i]);
}
int p = pref[n] & 1;
auto get = [&](int64_t x) {
int ret = 0;
while (true) {
if (x <= n * 2) {
ret ^= a[x];
break;
}
ret ^= p;
if ((x / 2 - n) % 2 == 0) {
break;
}
x /= 2;
}
return ret;
};
cout << get(l) << "\n";
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
}
2071D2 - Бесконечная последовательность (сложная версия)
Generalize the recursive method for evaluating an index to handle the computation of the prefix sum.
First, check the editorial of D1.
To upgrade the solution, we define a recursive function:
We precompute the even and odd prefix sums for $$$m \le 2n$$$. For $$$m \gt 2n$$$, the term $$$a_m$$$ follows:
For simplicity, assume $$$m \equiv 1 \pmod{4}$$$ (if not, keep incrementing $$$m$$$ and adjusting its contribution separately).
Define
This sum can be expressed as:
The pairs we're interested in computing are (keep in mind that $$$n$$$ is odd):
Notice that the sums of the above even and odd indices are equal, and depend on $$$p$$$:
Thus, the final sums are:
As a result, we can compute $$$\text{sum}(m)$$$ recursively by halving $$$m$$$ until $$$m \le 2n$$$, benefitting the precomputed even and odd prefix sums at each step.
The overall time complexity is: $$$O(n+\log(m))$$$.
#include<bits/stdc++.h>
using namespace std;
void solve() {
int n;
int64_t l, r;
cin >> n >> l >> r;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
vector<int> pref(n + 1);
for (int i = 1; i <= n; i++) {
pref[i] = pref[i - 1] + a[i];
}
if (n % 2 == 0) {
n++;
int cur = pref[n / 2] & 1;
a.push_back(cur);
pref.push_back(pref.back() + cur);
}
for (int i = n + 1; i <= n * 2; i++) {
a.push_back(pref[i / 2] & 1);
pref.push_back(pref[i - 1] + a[i]);
}
vector<int> even(n * 2 + 1);
for (int i = 1; i <= n * 2; i++) {
even[i] = even[i - 1] + (i & 1 ? 0 : a[i]);
}
int p = pref[n] & 1;
auto get = [&](int64_t x) {
int ret = 0;
while (true) {
if (x <= n * 2) {
ret ^= a[x];
break;
}
ret ^= p;
if ((x / 2 - n) % 2 == 0) {
break;
}
x /= 2;
}
return ret;
};
auto sum = [&](auto&& self, int64_t m) -> pair<int64_t, int64_t> {// {sum even, sum odd}
if (m <= n * 2) {
return {even[m], pref[m] - even[m]};
}
int64_t eve = even[n * 2 - 1], odd = pref[n * 2 - 1] - eve;
if (m % 2 == 0) {
m += 1, odd -= get(m);
}
if (m / 2 % 2) {
m += 1, eve -= get(m);
m += 1, odd -= get(m);
}
auto [e, _] = self(self, m / 2);
e -= even[n];
int64_t c = m / 2 - n + 1, both = (p ? c - e : e);
eve += both, odd += both;
return {eve, odd};
};
int64_t ans = 0;
auto [re, ro] = sum(sum, r);
ans += re + ro;
auto [le, lo] = sum(sum, l - 1);
ans -= le + lo;
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
}
Think about an unordered pair $$$(u, v)$$$ where both u and v are leaves in the final forest. Consider dividing all such pairs into separate categories based on their relationship in the original tree.
Let the first category be the pairs that are directly connected (neighbors), and analyze under what conditions both vertices become leaves.
For the pairs that are not direct neighbors, focus on those that share a common neighbor. Investigate how the state (fallen or not) of their neighbors influences the possibility of both vertices becoming leaves.
Let $$$fall_{i} $$$ denote the probability that the $$$i$$$-th node falls. We partition the unordered pairs $$$(u,v)$$$ into three categories:
- $$$u$$$ and $$$v$$$ are direct neighbors.
- $$$u$$$ and $$$v$$$ share a common neighbor.
- Pairs that do not satisfy the first two conditions.
Now, let us analyze the contribution of the first category to the final answer. For a pair $$$(u,v)$$$ of direct neighbors, both vertices become leaves if neither $$$u$$$ nor $$$v$$$ falls and if all of their other neighbors fall. Thus, the contribution of a specific pair $$$(u,v)$$$ is given by:
The whole contribution of the first category is:
For the second category, $$$u$$$ and $$$v$$$ share a neighbor, so this shared neighbor either must be the only one not falling among the neighbors of $$$u$$$ and $$$v$$$, or it must fall and exactly one of the other neighbors of both $$$u$$$ and $$$v$$$ must not fall. Additionally, both $$$u$$$ and $$$v$$$ must not fall anyway. Therefore, the contribution for a pair $$$(u,v)$$$ in the second category is given by:
where $$$s$$$ is the shared neighbor of $$$u$$$ and $$$v$$$.
The whole contribution of the second category is:
Moving to the third category: Here, $$$u$$$ and $$$v$$$ are neither direct neighbors nor do they share any common neighbor. In this case, the events that $$$u$$$ and $$$v$$$ become leaves are completely independent.
Define $$$leaf_{i} = (1 - fall_{i}) \cdot (\prod_{c \text{ is a neighbor of } i} fall_{c}) \cdot (\sum_{c \text{ is a neighbor of } i} \frac{1 - fall_{c}}{fall_{c}})$$$ as the probability that vertex $$$i$$$ becomes a leaf. Hence, for a pair $$$(u,v)$$$ in this category, the contribution is given by:
The whole contribution of the third category is:
The final answer is obtained by summing the contributions from all three categories. We can compute the contribution of the third category by summing $$$leaf_{i} \cdot leaf_{j}$$$ for all pairs $$$(i, j)$$$ with $$$i \lt j$$$, and then subtracting the contributions corresponding to pairs that satisfy one of the first two categories. The contribution of the second category can be computed by iterating over each node and accumulating the contributions from its neighbors (since these pairs share that node as their only common neighbor). The contribution of the first category can be computed in linear time too.
The overall time complexity is $$$O(n \cdot \log M)$$$, where the $$$\log$$$ factor arises from the modular inverse computations.
#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int add(int x, int y) {
return x + y - (x + y >= mod) * mod;
}
void add2(int &x, int y) {
x += y;
if (x >= mod) x -= mod;
}
int mul(int x, int y) {
return int((int64_t)x * y % mod);
}
int sub(int x, int y) {
return x - y + (x < y) * mod;
}
void sub2(int &x, int y) {
x -= y;
if (x < 0) x += mod;
}
int pwr(int x, int y) {
int ret = 1;
while (y) {
if (y & 1) ret = mul(ret, x);
x = mul(x, x);
y /= 2;
}
return ret;
}
int inv(int x) {
return pwr(x, mod - 2);
}
int norm(int64_t x) {
x %= mod;
if (x < 0) x += mod;
return int(x);
}
void solve() {
int n;
cin >> n;
vector adj(n + 1, vector<int> ());
vector<int> p(n + 1);
for (int i = 1; i <= n; i++) {
int q;
cin >> p[i] >> q;
p[i] = mul(p[i], inv(q));
//here, p[i] is the probability that node i will fall
}
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v), adj[v].push_back(u);
}
vector<int> p1(n + 1), p2(n + 1);
for (int i = 1; i <= n; i++) {
p1[i] = sub(1, p[i]);
for (int u: adj[i]) {
p1[i] = mul(p1[i], p[u]);
}
//p1[i] is the probability that node i won't fall, but all nodes around it will fall
for (int u: adj[i]) {
add2(p2[i], mul(p1[i], mul(inv(p[u]), sub(1, p[u]))));
}
//p2[i] is the probability that node i will be a leaf (it won't fall, all it's neighbors except one will fall)
}
int ans = 0, sum = 0;
for (int i = 1; i <= n; i++) {
add2(ans, mul(p2[i], sum));
add2(sum, p2[i]);
}
//take all contributions of unordered pairs
for (int i = 1; i <= n; i++) {
//recalculate the contribution of neighboring pairs
for (auto u: adj[i]) {
if (u < i) continue;
//avoid calculating the same pair probabilty twice
int pi = mul(p1[i], inv(p[u]));
//pi is the probability that every neighbour of i would fall except for u (not including the probability of u not falling down)
int pu = mul(p1[u], inv(p[i]));
//pu is the probability that every neighbour of u would fall except for i (not including the probability of i not falling down)
//this case is just a tree of 2 nodes, both of them are leaves
add2(ans, mul(pi, pu));
//subtract the old contribution
sub2(ans, mul(p2[i], p2[u]));
}
//recalculate the contribution of pairs with a shared neighbour which is node i (ie calculate the contribution for pairs u, v such that dis(u, v) = 2 and dis(u, i) = dis(v, i) = 1
sum = 0;
for (int u: adj[i]) {
sub2(ans, mul(sum, p2[u]));
add2(sum, p2[u]);
//subtract the old contribution
}
//p[i] doesn't fall
sum = 0;
for (int u: adj[i]) {
int pu = mul(p1[u], inv(p[i]));
//pu is the probability that node u is a leaf connected to node i
add2(ans, mul(sum, pu));
add2(sum, mul(pu, sub(1, p[i])));
}
//p[i] falls
sum = 0;
for (int u: adj[i]) {
int pu = sub(p2[u], mul(p1[u], mul(inv(p[i]), sub(1, p[i]))));
//pu is the probability that node u is a leaf not connected to node i
add2(ans, mul(sum, pu));
add2(sum, mul(pu, inv(p[i])));
}
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
}
Binary search on $$$p$$$. After fixing $$$p$$$, find the maximum $$$p$$$-towering subsequence.
if we denote the set of indexes that correspond to the maximum "increasing" $$$p$$$-towering subsequence on prefix $$$i$$$ as $$$S_i$$$, then for any $$$i \lt n$$$: $$$S_i \subseteq S_{i + 1}$$$.
Let's do binary search on $$$p$$$. After fixing some $$$p$$$ our goal is to find the maximum $$$p$$$-towering subsequence and check if the length of that subsequence $$$s$$$ satisfies $$$n - s \le k$$$.
To find the maximum $$$p$$$-towering subsequence, for each index $$$i$$$ we will find the maximum $$$p$$$-towering subsequence such that the "left" part of that subsequence is in prefix $$$i$$$ and its right part is in suffix $$$i$$$.
Let's focus only on prefixes, as the suffixes can be done similarly. So, for each prefix $$$i$$$ we want to find the maximum "increasing" $$$p$$$-towering subsequence. To do it, we will traverse the array from left to right and maintain the currently found maximum subsequence. The key idea here is that as you move from left to right you only need to add new elements to the "increasing" subsequence and never delete any (or, formally speaking, if we denote the set of indexes that correspond to maximum "increasing" $$$p$$$-towering subsequence on prefix $$$i$$$ as $$$S_i$$$, then for any $$$i \lt n$$$: $$$S_i \subseteq S_{i + 1}$$$ (the proof is left to the reader).
Before moving to the details of implementation, let's elaborate a bit on the previous paragraph. Consider the fifth test case from the sample; suppose the current $$$p = 7$$$; and we have just arrived at the tenth element (denoted with star $$$^*$$$). Before this position, the maximum "increasing" $$$p$$$-towering subsequence consists of the first, third, and fifth elements (denoted with underlines):
$$$[\underline{6}, 3, \underline{8}, 5, \underline{8}, 3, 2, 1, 2, 7^*, 1]$$$.
Now we need to check if we can increase the size of the subsequence. Since $$$p = 7$$$, then we certainly can add the tenth element with value $$$7$$$ to the subsequence. However, since we add a new number to the subsequence, two numbers become available: the second one with value $$$3$$$ and the forth one with value $$$5$$$. Thus, after processing the tenth element, the maximum "increasing" $$$p$$$-towering subsequence will look like this:
$$$[\underline{6}, \color{red}{\underline{3}}, \underline{8}, \color{red}{\underline{5}}, \underline{8}, 3, 2, 1, 2, \color{red}{\underline{7}}^*, 1]$$$.
So we need some way to find such "new" numbers that appear when we add some elements to the subsequence (like when the element with value $$$5$$$ becomes available from the example). To resolve this we first assign $$$a_i := p - a_i$$$ for each $$$i$$$. To find the positions that are becoming available, we can search for the rightmost non-positive element on the current prefix. Once found (suppose its index is $$$j$$$), decrease all elements on the prefix $$$j$$$ by one and assign $$$a_j := \infty$$$ (to avoid this position in the future). All these operations can be performed with the help of a segment tree.
This concludes the asymptotic complexity: $$$O(n \log{C} \log{n})$$$.
#include <bits/stdc++.h>
#define len(a) (int)a.size()
#define all(a) a.begin(), a.end()
using namespace std;
const int MAXI = 1e9 + 1e7;
const int MAXN = 2e5 + 100;
struct Node {
int min_on_subtree = 0, push_addition = 0;
};
Node t[MAXN * 4];
int a[MAXN], pref[MAXN], suf[MAXN];
class Segtree {
private:
int n;
void add_on_subtree(int u, int val) {
t[u].push_addition += val;
t[u].min_on_subtree += val;
}
void push(int u) {
if (t[u].push_addition) {
add_on_subtree(u * 2 + 1, t[u].push_addition);
add_on_subtree(u * 2 + 2, t[u].push_addition);
t[u].push_addition = 0;
}
}
void recalc(int u) {
t[u].min_on_subtree = min(t[u * 2 + 1].min_on_subtree, t[u * 2 + 2].min_on_subtree);
}
void update(int u, int l, int r, int pos, int val) {
if (l == r) {
t[u].min_on_subtree = val;
} else {
push(u);
int mid = (l + r) / 2;
if (pos <= mid)
update(u * 2 + 1, l, mid, pos, val);
else
update(u * 2 + 2, mid + 1, r, pos, val);
recalc(u);
}
}
void add_on_segment(int u, int l, int r, int ql, int qr, int val) {
if (ql <= l && r <= qr)
add_on_subtree(u, val);
else {
push(u);
int mid = (l + r) / 2;
if (ql <= mid)
add_on_segment(u * 2 + 1, l, mid, ql, qr, val);
if (qr > mid)
add_on_segment(u * 2 + 2, mid + 1, r, ql, qr, val);
recalc(u);
}
}
int find_prev_non_pos_put_inf(int u, int l, int r, int pos) {
if (t[u].min_on_subtree > 0)
return -1;
if (l == r) {
t[u].min_on_subtree = MAXI;
return l;
}
push(u);
int mid = (l + r) / 2, res = -1;
if (pos > mid)
res = find_prev_non_pos_put_inf(u * 2 + 2, mid + 1, r, pos);
if (res == -1)
res = find_prev_non_pos_put_inf(u * 2 + 1, l, mid, pos);
recalc(u);
return res;
}
public:
explicit Segtree(int n): n(n) {
fill(t, t + 4 * n, Node{MAXI, 0});
};
void update(int pos, int val) {
update(0, 0, n - 1, pos, val);
}
void add_on_segment(int ql, int qr, int val) {
add_on_segment(0, 0, n - 1, ql, qr, val);
}
int find_prev_non_pos_put_inf(int pos) {
return find_prev_non_pos_put_inf(0, 0, n - 1, pos);
}
};
void f(int n, int p, int *res) {
Segtree tree(n);
int cur_sz = 0;
for (int i = 0; i < n; i++) {
tree.update(i, p - a[i]);
int pos = i;
while ((pos = tree.find_prev_non_pos_put_inf(pos)) != -1) {
cur_sz++;
tree.add_on_segment(0, pos, -1);
}
res[i] = cur_sz;
}
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int testcases;
cin >> testcases;
while (testcases--) {
int n, k;
cin >> n >> k;
int max_a = -1;
for (int i = 0; i < n; i++) {
cin >> a[i];
max_a = max(max_a, a[i]);
}
int l = 0, r = max_a + 1;
while (l + 1 < r) {
int mid = (l + r) / 2;
f(n, mid, pref);
reverse(a, a + n);
f(n, mid, suf);
reverse(a, a + n);
reverse(suf, suf + n);
int mx = -1;
for (int i = 0; i < n; i++) {
if (a[i] >= mid)
mx = max(mx, pref[i] + suf[i] - 1);
}
if (n - mx <= k)
l = mid;
else
r = mid;
}
cout << l << '\n';
}
}
