Unfortunately, the round turns out to be very unbalanced :( I'm deeply sorry about this issue.
I hope you still enjoy the problems.
2134A - Painting With Two Colors
Check the parity of numbers $$$a$$$, $$$b$$$, and $$$n$$$.
Let us first consider the $$$b$$$ blue cells. Since all $$$b$$$ cells appear in the final painting, for the coloring to be symmetric, they must be placed at the middle of the grid. Consequently, $$$b$$$ and $$$n$$$ must have the same parity.
Next, we examine two possible cases:
- If $$$b \geq a$$$, then the blue cells can fully cover all red cells. In this situation, the value of $$$a$$$ does not affect the final coloring.
- If $$$b \lt a$$$, then the red cells are not completely covered by the blue ones. Therefore, the red cells must also be placed in the middle of the grid, which means $$$a$$$ and $$$n$$$ must have the same parity as well.
Thus, by checking these conditions, we can determine whether a symmetric coloring exists. This requires only $$$\mathcal{O}(1)$$$ time.
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n, a, b;
cin >> n >> a >> b;
if (a <= b) {
cout << ((n % 2) == (b % 2) ? "YES\n" : "NO\n");
} else {
cout << ((n % 2) == (b % 2) && (n % 2) == (a % 2) ? "YES\n" : "NO\n");
}
}
}
t = int(input())
for _ in range(t):
n, a, b = map(int, input().split())
if a <= b:
if n % 2 == b % 2:
print('YES')
else:
print('NO')
else:
if n % 2 == a % 2 and n % 2 == b % 2:
print('YES')
else:
print('NO')
There are (at least) two solutions to the problem. Vote for your solution!
Find an integer $$$g \gt 1$$$ and integers $$$c_1, c_2, \ldots, c_n$$$ such that each $$$a_i + k \cdot c_i$$$ is divisible by $$$g$$$.
Decide the value of $$$g$$$ only based on $$$k$$$. There may be more than one possible choices.
The problem is equivalent to finding an array of $$$n$$$ non-negative integers $$$c_1, c_2, \ldots, c_n$$$ such that $$$0 \le c_i \le k$$$ for $$$1 \le i \le n$$$ and
The idea is as follows. If we can find an integer $$$g \gt 1$$$ and integers $$$c_1, c_2, \ldots, c_n$$$ such that each $$$a_i + k \cdot c_i$$$ is divisible by $$$g$$$ (for $$$1 \le i \le n$$$), then the GCD condition is satisfied.
There are (at least) two ways to construct such a solution. The simplest solution is to take $$$g = k+1$$$ and define $$$c_i = a_i \bmod (k+1)$$$. This works because
Hence every term is divisible by $$$k+1$$$.
Alternatively, you can also find the smallest integer $$$x$$$ such that $$$\gcd(x,k) = 1$$$, and set $$$g = x$$$. Note that $$$g \leq 29$$$, since $$$k \leq 10^9$$$ and the product of all prime numbers from $$$2$$$ to $$$29$$$ already exceeds $$$10^9$$$.
Then, for each $$$a_i$$$, we can add $$$k$$$ to it until it becomes divisible by $$$g$$$. In fact, the value of $$$c_i$$$ can be determined explicitly (though it is not required) as
where $$$k^{-1}$$$ is the modular inverse of $$$k$$$ modulo $$$g$$$.
Thus, in either method, we can always construct a valid array so that the GCD of the resulting numbers is greater than $$$1$$$.
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
vector<long long> a(n);
for (auto &i : a) {
cin >> i;
i += (i % (k + 1)) * k;
}
for (auto i : a)
cout << i << ' ';
cout << '\n';
}
}
t = int(input())
for _ in range(t):
n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
a[i] += (a[i] % (k + 1)) * k
print(*a)
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
vector<long long> a(n);
for (auto &i : a) {
cin >> i;
}
for (int g = 2;; g++) {
if (gcd(g, k) != 1)
continue;
for (auto &i : a) {
while (i % g != 0)
i += k;
}
for (auto i : a)
cout << i << ' ';
cout << '\n';
break;
}
}
}
import math
t = int(input())
for _ in range(t):
n, k = map(int, input().split())
a = list(map(int, input().split()))
for g in range(2, k + 2):
if math.gcd(g, k) > 1:
continue
ok = True
b = list(a)
for i in range(n):
if b[i] % g == 0:
continue
for j in range(1, k + 1):
b[i] += k
if b[i] % g == 0:
break
if b[i] % g != 0:
ok = False
if ok:
print(*b)
break
Only subarrays with length equal to $$$2$$$ or $$$3$$$ are useful.
Propose a greedy algorithm to decide which element to perform an operation.
For convenience, if $$$n$$$ is even, we append $$$a_{n+1}=0$$$ to the end of the array. Note that $$$a_{n+1}$$$ cannot be modified.
The first key observation is the following:
Observation. If all subarrays $$$[a_l, a_{l+1}, \ldots, a_r]$$$ with the following properties satisfy the condition, then all subarrays satisfy the condition:
- $$$r = l + 2$$$,
- $$$l$$$ and $$$r$$$ are both odd.
Proof. Consider such subarrays where both $$$l$$$ and $$$r$$$ are odd:
&=& a_l \;+\; \displaystyle \left( \sum_{\substack{l+2 \leq i \leq r-2 \\ i \ \text{odd}}} 2a_i \right) \;+\; a_r \\[1.2em]
&\geq& a_l \;+\; \displaystyle \left( \sum_{\substack{l+2 \leq i \leq r-2 \\ i \ \text{odd}}} a_i \right) \;+\; a_r \\[1.2em]
&=& \displaystyle \sum_{\substack{l \leq i \leq r \\ i \ \text{odd}}} a_i \end{array}$$$
The second inequality holds because all numbers are non-negative.
Thus, checking only these subarrays is sufficient: all other subarrays will automatically satisfy the condition because they involve fewer elements at odd positions. $$$\square$$$
We will call these subarrays important in the following discussion.
Now we find the minimum number of operations. Instead of directly minimizing the number of operations, we can think in terms of constructing the final array $$$b$$$ after the operations. Our goal is to maximize the sum of the elements in $$$b$$$.
Initially, we set $$$b_i = 0$$$ for all $$$i$$$. Notice that it is never beneficial to reduce values at even indices. Therefore, we can safely set $$$b_i = a_i$$$ for every even $$$i$$$.
The task is then to determine the values of $$$b_i$$$ at odd indices. It turns out that the following greedy algorithm works:
- Repeatedly pick the smallest odd index $$$i$$$ such that $$$b_i \lt a_i$$$, and increasing $$$b_i$$$ by $$$1$$$ does not violate the condition for any important subarray. Then increment $$$b_i$$$ by $$$1$$$.
This greedy algorithm ensures that we maximize the sum of $$$b$$$ while preserving validity. It can be simulated in $$$\mathcal{O}(n)$$$ time.
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto &i : a)
cin >> i;
vector<int> b(n + 1);
long long ans = 0;
for (int i = 0; i < n; i += 2) {
int mn = a[i];
if (i >= 2)
mn = min(mn, a[i - 1] - b[i - 2]);
if (i + 1 < n)
mn = min(mn, a[i + 1]);
b[i] = mn;
ans += (a[i] - b[i]);
}
cout << ans << '\n';
}
}
t = int(input())
for _ in range(t):
n = int(input())
a = list(map(int, input().split()))
b = [0] * (n + 1)
ans = 0
for i in range(0, n, 2):
mn = a[i]
if i >= 2:
mn = min(mn, a[i - 1] - b[i - 2])
if i + 1 < n:
mn = min(mn, a[i + 1])
b[i] = mn
ans += (a[i] - b[i])
print(ans)
Consider the diameter of the tree. What do you discover?
Each sliding operation increases the diameter of the tree by at most $$$1$$$.
Now about the construction. How to perform an operation at each step that increases the diameter by exactly $$$1$$$?
We begin with the following observation:
Observation. Each sliding operation increases the diameter of the tree by at most $$$1$$$.
Proof. Consider an operation $$$(a,b,c)$$$, any pair of indices $$$(u,v)$$$, and the unique path $$$p$$$ between $$$u$$$ and $$$v$$$. If $$$p$$$ does not pass through $$$b$$$, or if $$$b$$$ is an endpoint of $$$p$$$, then the length of $$$p$$$ increases by at most $$$1$$$ before and after the operation. Otherwise, let $$$i_1$$$ and $$$i_2$$$ denote the two neighbors of $$$b$$$ on the path $$$p$$$. Then:
- If $$$i_1 = a$$$ and $$$i_2 = c$$$ (or vice versa), the length of $$$p$$$ does not change.
- If $$$i_1 = a$$$ and $$$i_2 \neq c$$$ (or vice versa), the length of $$$p$$$ increases by $$$1$$$.
- If $$$i_1 \neq a$$$ and $$$i_2 = c$$$ (or vice versa), the length of $$$p$$$ decreases by $$$1$$$.
- In all other cases, the length of $$$p$$$ does not change.
Thus, for any path in the tree, its length can increase by at most $$$1$$$. Consequently, the diameter of the tree increases by at most $$$1$$$ after a single operation. $$$\square$$$
Let $$$l$$$ denote the diameter of the input tree. To transform it into a path graph (whose diameter is $$$n-1$$$), it is clear that at least $$$(n-1) - l$$$ operations are required.
The remaining question is whether it is always possible to perform an operation at each step that increases the diameter by exactly $$$1$$$. This turns out to be true. To see this, take any diameter of the tree and root the tree at one of its endpoints. In each operation, select an edge adjacent to the diameter. Suppose this edge is $$$(u,v)$$$, where $$$u$$$ lies on the diameter and $$$v$$$ does not. Then perform the operation with $$$a$$$ as the parent of $$$u$$$ (in the rooted tree), $$$b = u$$$, and $$$c = v$$$. One can verify that this increases the diameter by $$$1$$$.
From the above construction, we conclude not only that the minimum number of operations is $$$(n-1)-l$$$, but also that we can explicitly construct a sequence of operations that transforms the given tree into a path graph with this minimum number of moves.
Finally, finding the first sliding operation can be done in $$$\mathcal{O}(n)$$$ time.
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<vector<int>> G(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--, v--;
G[u].push_back(v);
G[v].push_back(u);
}
vector<int> dist(n), p(n);
function<void(int, int)> dfs = [&](int now, int par) {
p[now] = par;
for (int i : G[now]) {
if (i != par) {
dist[i] = dist[now] + 1;
dfs(i, now);
}
}
};
dist[0] = 0;
dfs(0, -1);
int x = max_element(dist.begin(), dist.end()) - dist.begin();
dist[x] = 0;
dfs(x, -1);
int y = max_element(dist.begin(), dist.end()) - dist.begin();
if (dist[y] == n - 1) {
cout << -1 << '\n';
} else {
vector<int> on_diameter(n);
int now = y;
while (now != -1) {
on_diameter[now] = 1;
now = p[now];
}
int a = -1, b = -1, c = -1;
for (int u = 0; u < n; u++) {
for (int v : G[u]) {
if (on_diameter[u] && !on_diameter[v]) {
a = p[u], b = u, c = v;
break;
}
}
if (a != -1)
break;
}
cout << a + 1 << ' ' << b + 1 << ' ' << c + 1 << '\n';
}
}
}
An intuitive starting point may be to perform a throw query on every coordinate $$$i$$$. For which $$$i$$$ we can decide the value of $$$a_i$$$ immediately?
For those incides whose $$$a_i$$$ is unknown, try to perform some swap queries on them to get the values of $$$a_i$$$ for them.
No two unknown indices are adjacent.
An intuitive starting point is to perform a throw query on every coordinate $$$i$$$ ($$$1 \le i \le n$$$). Let $$$d_i$$$ denote the total number of jumps the ball makes when starting from coordinate $$$i$$$. For convenience, define $$$d_{n+1} = d_{n+2} = 0$$$.
Notice that for $$$1 \le i \le n$$$, if $$$d_{i+1} \neq d_{i+2}$$$, then we can immediately determine $$$a_i$$$: if $$$d_i = d_{i+1} + 1$$$, then $$$a_i = 1$$$; otherwise $$$a_i = 2$$$.
The difficult part of the problem is when $$$d_{i+1} = d_{i+2}$$$. We call an index $$$i$$$ \textbf{unknown} if $$$d_{i+1} = d_{i+2}$$$. In such cases, we can deduce $$$d_i$$$ without issuing a query, thus saving it for later use. The following observation is crucial:
Observation. No two unknown indices are adjacent.
Proof. If $$$i$$$ is unknown, then $$$d_i = d_{i+1} + 1$$$, hence $$$d_i \neq d_{i+1}$$$. Therefore, $$$i-1$$$ cannot be unknown. $$$\square$$$
To exploit this fact, we adopt the following strategy: After computing all $$$d_i$$$, for each unknown index $$$i$$$ (in increasing order), we swap the boxes at positions $$$i$$$ and $$$i+1$$$, and then perform a throw query at coordinate $$$i+1$$$. Since index $$$i+1$$$ is not unknown, this reveals $$$a_i$$$. The special case is $$$i = n$$$: here, we swap boxes $$$n-1$$$ and $$$n$$$, then perform a throw query on coordinate $$$n-1$$$ to obtain $$$a_n$$$.
To sum up:
- For $$$i$$$ from $$$n$$$ down to $$$1$$$: perform a throw query on coordinate $$$i$$$. If $$$d_{i+1} = d_{i+2}$$$, skip the query for $$$i$$$ and mark $$$i$$$ as unknown (but still compute $$$d_i$$$). Otherwise, determine both $$$a_i$$$ and $$$d_i$$$.
- For each $$$i$$$ from $$$1$$$ to $$$n-1$$$: if $$$i$$$ is unknown, swap box $$$i$$$ with box $$$i+1$$$ and perform a throw query at coordinate $$$i+1$$$. This reveals $$$a_i$$$.
- Finally, swap $$$n-1$$$ and $$$n$$$, and perform a throw query on coordinate $$$n-1$$$ to determine $$$a_n$$$.
For every unknown index we use $$$2$$$ queries, and for each known index we use $$$1$$$. Since no two unknown indices are adjacent, there are at most $$$\lceil \frac{n}{2} \rceil$$$ unknown indices. Hence, the total number of queries is at most $$$\left\lceil \frac{3n}{2} \right\rceil$$$.
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
auto swap = [&](int x) {
cout << "swap " << x + 1 << endl;
};
auto throw_ball = [&](int x) {
cout << "throw " << x + 1 << endl;
int ret;
cin >> ret;
return ret;
};
auto answer = [&]() {
cout << "!";
for (auto i : a)
cout << ' ' << i;
cout << endl;
};
vector<int> jumps(n + 2);
for (int i = n - 1; i >= 0; i--) {
if (jumps[i + 1] == jumps[i + 2]) {
jumps[i] = jumps[i + 1] + 1;
} else {
jumps[i] = throw_ball(i);
if (jumps[i] == jumps[i + 1] + 1)
a[i] = 1;
else
a[i] = 2;
}
}
for (int i = 0; i + 1 < n; i++) {
if (a[i] == 0) {
swap(i);
int jumps_i = throw_ball(i + 1);
if (jumps_i == jumps[i + 2] + 1)
a[i] = 1;
else
a[i] = 2;
}
}
swap(n - 2);
int jumps_last = throw_ball(n - 2);
if (jumps_last == 2)
a[n - 1] = 1;
else
a[n - 1] = 2;
answer();
}
}
Thanks to Misuki for coming up with a better solution! My original solution has a much larger constant.
Consider two groups of numbers; one is $$${0, 2}$$$ and another is $$${1, 3}$$$. What do you discover?
Consider the segments formed by $$${0, 2}$$$ (same for $$${1, 3}$$$). For each $$$i$$$ and $$$j$$$, find the number of ways to arrange them into $$$i$$$ segments so that the total number of adjacent pairs inside all segments contribute oddness $$$j$$$.
Enumerate all binary strings consisting of $$$c_0$$$ zeros and $$$c_2$$$ twos. Then split these strings into several substrings.
Brute force over the number of runs of the binary string. Find the contribution to the count.
Consider any rearrangement $$$b$$$. We color all elements $$$b_i$$$ with value $$$0$$$ or $$$2$$$ as red, and those with value $$$1$$$ or $$$3$$$ as blue. Then the array can be viewed as alternating red and blue segments.
We observe the following:
- Adjacent pairs within a red segment contribute $$$0$$$ or $$$2$$$ to the oddness. The same holds for blue segments.
- Adjacent pairs between red and blue segments contribute exactly $$$1$$$ to the oddness.
- The number of red and blue segments differs by at most $$$1$$$.
Hence, if we can calculate the following:
- $$$r_{i,j}$$$: number of ways to arrange $$$c_0$$$ zeros and $$$c_2$$$ twos into $$$i$$$ segments, so that the total number of adjacent pairs inside all segments contribute oddness $$$j$$$.
- Similarly define $$$b_{i,j}$$$ for the blue digits ($$$1$$$ and $$$3$$$)
Then the final answer can be computed in $$$\mathcal{O}(n^3)$$$ by performing convolutions between the arrays pairs $$$(r_i, b_i), (r_{i+1}, b_i), (r_i, b_{i+1})$$$.
Now about computing $$$r_{i,j}$$$. This reduces to counting tuples of $$$i$$$ binary strings formed from $$$c_0$$$ zeros and $$$c_2$$$ twos, such that the total number of alternating adjacent pairs inside them equals $$$j$$$.
The idea is as follows. First, enumerate all binary strings consisting of $$$c_0$$$ zeros and $$$c_2$$$ twos. Then split these strings into several substrings.
Suppose a binary string has $$$l$$$ runs. Let $$$l_1 = \left\lceil \frac l 2 \right\rceil$$$ be the number of runs of $$$0$$$, and $$$l_2 = l - l_1$$$ the number of runs of $$$2$$$ (or vice versa). The number of such binary strings is
In such strings, there are $$$l-1$$$ adjacent pairs with different numbers, and $$$c_0 + c_2 - l$$$ adjacent pairs with the same numbers.
Now split the string into several substrings. Assume we choose $$$k_1$$$ positions among the $$$l-1$$$ differing adjacencies, and $$$k_2$$$ positions among the $$$c_0 + c_2 - l$$$ equal adjacencies. The number of ways to do this is
This partition produces $$$k_1 + k_2 + 1$$$ substrings, each contributing oddness $$$2 \cdot (l - 1 - k_1)$$$.
Thus, the contribution to $$$r_{k_1 + k_2 + 1, \, 2 \cdot (l - 1 - k_1)}$$$ is
Enumerating all possible tuples $$$(l, k_1, k_2)$$$ suffices to compute all $$$r_{i,j}$$$. This computation takes $$$\mathcal{O}(n^3)$$$ time.
By the same process, we can compute $$$b_{i,j}$$$ in $$$\mathcal{O}(n^3)$$$. Finally, convolving the results yields the number of distinct permutations for each oddness value. The entire algorithm runs in $$$\mathcal{O}(n^3)$$$ time.
#include <iostream>
#include <vector>
using namespace std;
constexpr int MAXN = 800;
// Modified from https://github.com/ToxicPie/NaCl
template <typename T> struct M {
constexpr static T MOD = 1'000'000'007;
T v;
M(T x = 0) {
v = (-MOD <= x && x < MOD) ? x : x % MOD;
if (v < 0)
v += MOD;
}
explicit operator T() const { return v; }
bool operator==(const M &b) const { return v == b.v; }
bool operator!=(const M &b) const { return v != b.v; }
M operator-() { return M(-v); }
M operator+(M b) { return M(v + b.v); }
M operator-(M b) { return M(v - b.v); }
M operator*(M b) { return M((long long)v * b.v % MOD); }
M operator/(M b) { return *this * (b ^ (MOD - 2)); }
friend M operator^(M a, int b) {
M ans(1);
for (; b; b >>= 1, a *= a)
if (b & 1)
ans *= a;
return ans;
}
friend M &operator+=(M &a, M b) { return a = a + b; }
friend M &operator-=(M &a, M b) { return a = a - b; }
friend M &operator*=(M &a, M b) { return a = a * b; }
friend M &operator/=(M &a, M b) { return a = a / b; }
};
using Mod = M<int>;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
vector<vector<Mod>> binom_(MAXN + 1, vector(MAXN + 1, Mod(0)));
for (int i = 0; i <= MAXN; i++)
for (int j = 0; j <= i; j++) {
if (j == 0 || j == i)
binom_[i][j] = 1;
else
binom_[i][j] = binom_[i - 1][j] + binom_[i - 1][j - 1];
}
auto binom = [&](int x, int y) {
if (x >= y && y >= 0 && x >= 0)
return binom_[x][y];
else
return Mod(0);
};
int t;
cin >> t;
while (t--) {
vector<int> cnt(4);
for (auto &i : cnt)
cin >> i;
int n = cnt[0] + cnt[1] + cnt[2] + cnt[3];
vector<vector<Mod>> r(n + 1, vector(n + 1, Mod(0))),
b(n + 1, vector(n + 1, Mod(0)));
auto fill_table = [&](int x, int y, vector<vector<Mod>> &table) {
for (int i = 2; i <= x + y; i++) {
vector<pair<int, int>> segments;
if (i & 1)
segments = {{i / 2, i - i / 2}, {i - i / 2, i / 2}};
else
segments = {{i / 2, i / 2}, {i / 2, i / 2}};
for (auto [l1, l2] : segments) {
if (x < l1 || y < l2)
continue;
auto mul = binom(x - 1, l1 - 1) * binom(y - 1, l2 - 1);
int different = i - 1, same = (x + y) - 1 - different;
for (int j = 0; j <= different; j++)
for (int k = 0; k <= same; k++) {
auto mul2 = binom(different, j) * binom(same, k);
int c = different - j;
table[j + k + 1][c] += mul * mul2;
}
}
}
};
fill_table(cnt[0], cnt[2], r);
fill_table(cnt[1], cnt[3], b);
vector<Mod> ans(2 * (n - 1) + 1);
for (int i = 1; i <= (n + 1) / 2; i++)
for (int j = 0; j <= n; j++)
for (int k = 0; k <= n; k++) {
int oddness = (j + k) * 2 + (i * 2 - 1);
if (oddness >= 0 && oddness <= 2 * (n - 1))
ans[oddness] += r[i][j] * b[i][k] * 2;
}
for (int i = 1; i <= (n + 1) / 2 && i + 1 <= n; i++)
for (int j = 0; j <= n; j++)
for (int k = 0; k <= n; k++) {
int oddness = (j + k) * 2 + i * 2;
if (oddness >= 0 && oddness <= 2 * (n - 1)) {
ans[oddness] += r[i][j] * b[i + 1][k];
ans[oddness] += r[i + 1][j] * b[i][k];
}
}
for (int i = 0; i <= 2 * (n - 1); i++)
cout << ans[i].v << " \n"[i == 2 * (n - 1)];
}
}
