Thanks for the participation. I hope you enjoyed the problems, or at the very least learned something new.
The codes will be posted after the hacking phase is over. Codes have been posted.
(Author & Analysis: SpyrosAliv)
Every character of $$$a$$$ is flipped in exactly one string. Therefore, if $$$a_i = 1$$$, we need to add $$$n-1$$$ to the answer (since the $$$i$$$-$$$th$$$ character will stay $$$1$$$ for $$$n-1$$$ strings), and if $$$a_i = 0$$$ we need to add $$$1$$$ (since the $$$i$$$-$$$th$$$ character will be $$$1$$$ in exactly one string).
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n; cin >> n;
string s; cin >> s;
int ans = 0;
for (auto x: s) {
if (x == '0') ans++;
else ans += n - 1;
}
cout << ans << '\n';
}
int main() {
int t; cin >> t;
while (t--) solve();
return 0;
}
(Author & Analysis: SpyrosAliv)
If $$$x = n$$$ then we can output any permutation, since in order for the $$$\operatorname{MEX}$$$ to be equal to $$$n$$$, every value $$$0, 1, ..., n-1$$$ must appear. Otherwise, we want to build a permutation $$$p$$$ such that two main conditions hold.
Firstly, we want $$$x$$$ to appear on the final strip as soon as possible. In other words, the first index $$$i$$$ such that $$$\operatorname{MEX}(p_1, p_2, ..., p_i) = x$$$ must be minimized. In addition, the index $$$j$$$ such that $$$p_j = x$$$ must be maximized, since the $$$\operatorname{MEX}$$$ of a set that contains $$$x$$$ cannot be equal to $$$x$$$.
There are a lot of constructions that satisfy those conditions. One of them is the permutation $$$p = [0, 1, ..., x-1, x+1, ..., n-1, x]$$$.
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, x; cin >> n >> x;
for (int i = 0; i < x; i++) cout << i << " ";
for (int i = x+1; i < n; i++) cout << i << " ";
if (x < n) cout << x;
cout << '\n';
}
int main() {
int t; cin >> t;
while (t--) solve();
return 0;
}
(Author & Analysis: SpyrosAliv)
Suppose that the two arrays $$$a$$$ and $$$b$$$ of size $$$n$$$ are called $$$s$$$-complementary if and only if $$$a_i + b_i = s$$$ for all $$$1 \le i \le n$$$.
Observation 1: If we know every element of $$$a$$$, and we know $$$s$$$, we can uniquely determine the elements of $$$b$$$.
We split the problem into two cases.
The first case is if there exists at least one element in $$$b$$$ that is not missing. Then we know the required sum $$$s = a_i + b_i$$$ for every $$$1 \le i \le n$$$. For every index $$$i$$$, we know $$$b_i = s - a_i$$$. If $$$0 \le s - a_i \le k$$$ doesn't hold for some index, the answer is $$$0$$$, since it is impossible for the two arrays to be complementary while $$$0 \le b_i \le k$$$. Otherwise, the answer is $$$1$$$ from Observation 1.
The second case is if every element of $$$b$$$ is missing:
Observation 2: if $$$a$$$ and $$$b$$$ are $$$s$$$-complementary, then the maximum element of $$$b$$$ is positioned at the index where the minimum element of $$$a$$$ is positioned at. That is because in order for $$$a_i + b_i = s$$$ to hold when $$$a_i$$$ is minimum, $$$b_i$$$ must be maximized.
Observation 3: The maximum element of $$$b$$$ must be at least $$$mx_a - mn_a$$$, i.e. the difference between the maximum and minimum elements of $$$a$$$.
Suppose that the maximum of $$$b$$$ is positioned at index $$$i$$$, and $$$b_i < mx_a - mn_a$$$. From Observation 2, $$$a_i = mn_a$$$, since the position of the maximum element of $$$b$$$ is the position of the minimum element of $$$a$$$. Then $$$s = a_i + b_i$$$, and $$$a_i + b_i < a_i + mx_a - mn_a$$$ (since $$$b_i < mx_a - mn_a$$$), so $$$s < mn_a + mx_a - mn_a = mx_a$$$ (since $$$a_i = mn_a$$$). However, $$$s < mx_a$$$ cannot hold (since elements of $$$b$$$ cannot be negative), therefore this is a contradiciton.
From Observation 3 and 1, we can set the maximum element of $$$b$$$ to $$$mx_a - mn_a, mx_a - mn_a + 1, ..., k$$$, which results to $$$k - (mx_a - mn_a) + 1$$$ different solutions.
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, k; cin >> n >> k;
int a[n], b[n];
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
int s = -1;
for (int i = 0; i < n; i++) {
if (b[i] != -1) {
if (s == -1) s = a[i] + b[i];
else {
if (s != a[i] + b[i]) {
cout << 0 << '\n';
return;
}
}
}
}
if (s == -1) {
sort(a, a+n);
int mx = a[n-1] - a[0];
cout << k - mx + 1 << '\n';
return;
}
for (int i = 0; i < n; i++) {
if (a[i] > s || s - a[i] > k) {
cout << 0 << '\n';
return;
}
}
cout << 1 << '\n';
}
int main() {
int t; cin >> t;
while (t--) solve();
return 0;
}
(Author: cry, Analysis: cowthecow)
There is a greedy strategy. Every time you see some flower in $$$a$$$, if its beauty is not less than the beauty of next flower you must pick from $$$b$$$, you will pick it. The answer is $$$0$$$ if we run the greedy without inserting a new flower in $$$a$$$ and still collecting all $$$m$$$ needed flowers.
Now, consider what inserting a new flower of beauty $$$k$$$ in $$$a$$$ will do. It will allow you to "skip" some flower listed in $$$b$$$, as you can place it anywhere in $$$a$$$ and just pick it up when necessary. Therefore, instead of inserting a new element, we can reconsider the problem as deleting some element listed in $$$b$$$. So, one slow solution would be to try deleting $$$b_1$$$, then running the greedy on $$$a$$$, and repeat for $$$b_2$$$, $$$b_3, ..., b_m$$$. Then, we can keep the minimum $$$b_i$$$ such that the greedy was successful when deleting that flower.
The solution is too slow. Instead, we can compute for every index $$$1 \le i \le m$$$ the minimum index $$$j$$$ such that if we run the greedy on the prefix $$$a_1, a_2, ..., a_j$$$, we will have collected flowers $$$b_1, b_2, ..., b_i$$$. Let this value for index $$$i$$$ of $$$b$$$ be $$$p_i$$$. Do the same for each suffix of $$$a$$$. Specifically, let $$$s_i$$$ be the maximum index $$$j$$$ such that if we run the greedy on the suffix $$$a_j, a_{j+1}, ..., a_n$$$ we would have collected the flowers $$$b_i, b_{i+1}, ..., b_m$$$. These values can be calculated with two pointers.
Now, we can delete $$$b_j$$$ if $$$p_{j-1} < s_{j+1}$$$ (to delete $$$b_1$$$, it must be that $$$s_{2} > 0$$$ and to delete $$$b_m$$$ that $$$p_{m-1} \le n$$$). We keep the minimum among all deletable values in $$$b$$$. If there does not exist such a value the answer is $$$-1$$$.
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 5;
int main(){
int T; cin >> T;
while(T--){
int N, M; cin >> N >> M;
vector<int> a(N), b(M);
for(int i = 0; i < N; i++) cin >> a[i];
for(int i = 0; i < M; i++) cin >> b[i];
vector<int> backwards_match(M);
int j = N - 1;
for(int i = M - 1; i >= 0; i--){
while(j >= 0 && a[j] < b[i]) j--;
backwards_match[i] = j--;
}
vector<int> forwards_match(M);
j = 0;
for(int i = 0; i < M; i++){
while(j < N && a[j] < b[i]) j++;
forwards_match[i] = j++;
}
if(forwards_match.back() < N){
cout << 0 << endl;
continue;
}
int ans = INF;
for(int i = 0; i < M; i++){
int match_previous = i == 0 ? -1 : forwards_match[i - 1];
int match_next = i + 1 == M ? N : backwards_match[i + 1];
if(match_next > match_previous){
ans = min(ans, b[i]);
}
}
cout << (ans == INF ? -1 : ans) << "\n";
}
}
(Author: SpyrosAliv, Analysis: cowthecow)
Consider some permutation $$$p_1, p_2, ..., p_n$$$. Before answering queries, precompute the index of integer $$$i$$$ $$$(1 \le i \le n)$$$, suppose it is represented as $$$idx_i$$$.
Let's see how to answer some query $$$l, r, x$$$. Obviously, if $$$idx_x$$$ does not belong in the range $$$[l, r]$$$, the answer is $$$-1$$$. Otherwise, we want to somehow manipulate the elements so the binary search ends up checking $$$idx_x$$$.
Suppose the binary search is currently working on some range $$$[a, b]$$$. Let $$$m = \lfloor\frac{a + b}{2}\rfloor$$$. If $$$p_m = x$$$, we are done. Otherwise, consider the following cases:
- $$$p_m < x$$$ and $$$m < idx_x$$$: the binary search will continue on $$$[m+1, b]$$$, and since $$$idx_x$$$ belongs in that range, we simply let it continue. We must not swap this value.
- $$$p_m < x$$$ and $$$m > idx_x$$$: the binary search will continue on $$$[m+1, b]$$$, but $$$idx_x$$$ does not belong in that range. To fix this, we must replace $$$p_m$$$ with a value that is greater than $$$x$$$, in which case the search will continue on $$$[a, m-1]$$$.
- $$$p_m > x$$$ and $$$m < idx_x$$$: the binary search will continue on $$$[a, m-1]$$$, but $$$idx_x$$$ does not belong in that range. To fix this, we must replace $$$p_m$$$ with a value that is less than $$$x$$$, in which case the search will continue on $$$[m+1, b]$$$.
- $$$p_m > x$$$ and $$$m > idx_x$$$: the binary search will continue on $$$[a, m-1]$$$, and since $$$idx_x$$$ belongs in that range, we simply let it continue. We must not swap this value.
Keep doing this process until $$$p_m = x$$$. Suppose that the amount of integers less than $$$x$$$ needed are $$$s$$$, and the amount of integers greater than $$$x$$$ needed are $$$b$$$. In addition, let the values smaller than $$$x$$$ that we can't swap (because they already lead to the wanted direction) be denoted by $$$ss$$$ and those bigger as $$$bb$$$. There are $$$n - x$$$ greater values available in $$$p$$$, and $$$x-1$$$ smaller values available. Therefore, if $$$b > n - x - bb$$$ or $$$s > x - 1 - ss$$$, the answer is $$$-1$$$.
If the answer is not $$$-1$$$, we swap as many values as possible from $$$b$$$ and $$$s$$$ (which will be $$$\min{(b, s)} * 2$$$) and those that are still left after that (which will be $$$(\max{(b, s)} - \min{(b, s)}) * 2)$$$. The final answer is $$$(\max{(b, s)} - \min{(b, s)}) * 2 + \min{(b, s)} * 2$$$.
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n, q; cin >> n >> q;
int arr[n+1];
vector<int> idx(n+1, 0);
for (int i = 1; i <= n; i++) {
cin >> arr[i];
idx[arr[i]] = i;
}
while (q--) {
int l, r, k; cin >> l >> r >> k;
if (idx[k] > r || idx[k] < l) {
cout << -1 << " ";
continue;
}
int big = n - k, small = k - 1;
int needBig = 0, needSmall = 0;
int bigAv = n - k, smallAv = k - 1;
int lo = l, hi = r;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (arr[mid] == k) break;
if (mid < idx[k]) { // i want to go right
if (k < arr[mid]) {
needSmall++;
}
else smallAv--;
small--;
lo = mid+1;
}
else { // i want to go left
if (k > arr[mid]) {
needBig++;
}
else bigAv--;
big--;
hi = mid-1;
}
}
if (big < 0 || small < 0) {
cout << -1 << " ";
continue;
}
int ans = 2 * min(needBig, needSmall);
int diff = abs(needBig - needSmall);
if (needBig > needSmall) {
if (bigAv < diff) cout << -1 << " ";
else cout << ans + 2 * diff << " ";
}
else {
if (smallAv < diff) cout << -1 << " ";
else cout << ans + 2 * diff << " ";
}
}
}
signed main() {
int t; cin >> t;
while (t--){
solve();
cout << "\n";
}
return 0;
}
(Author & Analysis: SpyrosAliv)
Each column can be broken down to $$$3$$$ components:
- If $$$a_i = 0$$$, the top-most component will contain $$$i-1$$$ zeros, the second component a single one, and the third component $$$n-i$$$ zeros.
- If $$$a_i = 1$$$, the top-most component will contain $$$i-1$$$ ones, the second component a single zero, and the third component $$$n-i$$$ ones.
The easiest way to visualize is with DSU. For each column, create $$$3$$$ components, and for each component implicitly store the number of $$$0$$$s in it. Now, we will try to merge all adjacent components that both consist of zeros. Consider the following transitions, for every $$$1 < i \le n$$$:
- If $$$a_i = 0$$$ and $$$a_{i-1} = 0$$$, then the top-most component of column $$$i-1$$$ will be merged with the top-most component of column $$$i$$$. The same goes for the two bottom-most components.
- If $$$a_i = 0$$$ and $$$a_{i-1} = 1$$$, then the top-most component of column $$$i$$$ will be merged with the top-most component of column $$$i-1$$$.
- If $$$a_i = 1$$$ and $$$a_{i-1} = 0$$$, then the bottom-most component of column $$$i$$$ will be merged with the bottom-most component of column $$$i-1$$$.
- If $$$a_i = 1$$$ and $$$a_{i-1} = 1$$$, we merge nothing.
After we finish the merging, we just take the component with the maximum number of zeros, which will be the answer to this problem. Note that you do not actually have to use DSU; we only care about the sizes and not the representatives, so we can also use simple prefix sums.
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n; cin >> n;
string s; cin >> s;
s = " " + s;
vector<int> top(n+1, 0), bot(n+1, 0);
int ans = 0;
for (int i = 1; i <= n; i++) {
if (s[i] == '1') {
top[i] = bot[i-1] + 1;
}
else {
top[i] = top[i-1] + (i - 1);
bot[i] = bot[i-1] + (n - i);
}
ans = max(ans, max(top[i], bot[i]));
}
cout << ans << "\n";
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t; cin >> t;
while (t--) solve();
return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }
struct DSU{
vector<int> p, sz;
vector<ll> score;
DSU(int n){
p.assign(n, 0);
sz.assign(n, 1);
score.assign(n, 0);
for (int i = 0; i < n; i++) p[i] = i;
}
int find(int u){
if (p[u] == u) return u;
p[u] = find(p[u]);
return p[u];
}
void unite(int u, int v){
u = find(u);
v = find(v);
if (u == v) return;
if (sz[u] < sz[v]) swap(u, v);
p[v] = u;
sz[u] += sz[v];
score[u] += score[v];
}
bool same(int u, int v){
return find(u) == find(v);
}
int size(int u){
u = find(u);
return sz[u];
}
};
void solve(){
int n;
cin >> n;
string s;
cin >> s;
DSU dsu(2 * n);
vector<array<int, 2>> prev;
for (int i = 0; i < n; i++){
if (s[i] == '1'){
dsu.score[2 * i] = 1;
dsu.unite(2 * i, 2 * i + 1);
for (int j = 0; j < prev.size(); j++){
int l = prev[j][0];
int r = prev[j][1];
if (i >= l && i <= r)
dsu.unite(2 * i, 2 * (i - 1) + j);
}
prev = {{i, i}};
continue;
}
vector<array<int, 2>> nxt = {{0, i - 1}, {i + 1, n - 1}};
for (int j = 0; j < nxt.size(); j++){
auto [l, r] = nxt[j];
dsu.score[2 * i + j] = r - l + 1;
}
for (int j = 0; j < prev.size(); j++){
for (int k = 0; k < nxt.size(); k++){
auto [l1, r1] = prev[j];
auto [l2, r2] = nxt[k];
if (l2 > r1 || r2 < l1)
continue;
dsu.unite(2 * i + k, 2 * (i - 1) + j);
}
}
prev = nxt;
}
ll ans = 0;
for (int i = 0; i < 2 * n; i++)
ans = max(ans, dsu.score[i]);
cout << ans << "\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) solve();
}
Problem G1 — BAUDELAIRE (Easy Version)
(Author & Analysis: SpyrosAliv)
For some node $$$u$$$, let $$$v_u$$$ be its value and $$$s_u$$$ be the sum of the values of all nodes on the simple path from the root of the tree to node $$$u$$$ ($$$s_u$$$ will also be referenced as "the sum of node $$$u$$$" for the purposes of this solution). Also, let $$$p_u$$$ be the parent of node $$$u$$$ (if $$$u$$$ is not the root).
Suppose that we know which node is the root of the tree. Then, we can make $$$n$$$ queries to find $$$s_1, s_2, ..., s_n$$$, which is sufficient to figure out $$$v_1, v_2, ..., v_n$$$: it holds that $$$s_u = s_{p_u} + v_u$$$, therefore $$$v_u = s_u - s_{p_u}$$$.
Then, we have $$$200$$$ queries left to find the actual root of the tree. Consider some node $$$u$$$, and all of its neighbor nodes $$$c_1, c_2, ..., c_k$$$.
Observation 1: Toggling the value of node $$$u$$$ will change the sum of every adjacent node to $$$u$$$ that is not the parent.
Observation 2: We can find the parent of node $$$u$$$ within $$$3\log k$$$ queries. Consider doing binary search to find which node does not change its sum when toggling the value of $$$u$$$. In order to check if the prefix $$$c_1, c_2, ..., c_m$$$ includes the parent of $$$u$$$, we do the following: query for $$$s1 = s_{c_1} + s_{c_2} + ... + s_{c_m}$$$, toggle the value of $$$u$$$, and query for $$$s2 = s_{c_1}' + s_{c_2}' + ... + s_{c_m}'$$$ again. Let $$$D = |s1 - s2|$$$. From Observation 1, if every node among $$$c_1, c_2, ..., c_m$$$ changed its value, then $$$D = 2m$$$, so we know that the parent does not belong in that prefix. Otherwise, there is a node that did not change its sum, so we can continue our binary search on that prefix. This takes $$$3$$$ queries performed $$$\log k$$$ times. Note that if we never find the parent, it must mean that $$$u$$$ is the root of the tree.
Since the tree is a star, if we find the parent of node $$$1$$$, we will find the root. If there does not exist a parent, then $$$1$$$ is the root. The problem has been solved in $$$n + 3 \log(n)$$$ queries, which comfortably fits the query limit.
There are a lot of other (better) solutions for this version (for example, this solution), but this solution helps best for coming up with the idea for G2.
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n+1), son(n-1);
for (int i = 1; i < n; ++i) {
int u, v;
std::cin >> u >> v;
son[i-1] = i + 1;
}
int Q = 0;
auto ask = [&](int op, const std::vector<int> &v) {
if (++Q > n + 200) {
assert(false);
}
std::cout << "? " << op;
if (op == 1) {
std::cout << ' ' << v.size();
for (auto u: v) std::cout << ' ' << u;
std::cout << std::endl;
int res = 0;
std::cin >> res;
return res;
} else {
std::cout << ' ' << v[0] << std::endl;
return 0;
}
};
int rt = 0;
int bef = ask(1, son);
ask(2, std::vector<int>{1});
int af = ask(1, son);
if (std::abs(bef - af) == 2 * son.size()) {
rt = 1;
} else {
int l = 0, r = son.size() - 1;
while (l < r) {
int mid = l + (r - l) / 2;
std::vector<int> query(son.begin() + l, son.begin() + mid + 1);
int bef = ask(1, query);
ask(2, std::vector<int>{1});
int af = ask(1, query);
if (std::abs(bef - af) != 2 * (mid - l + 1)) {
r = mid;
} else {
l = mid + 1;
}
}
rt = son[l];
}
for (int i = 1; i <= n; ++i) {
a[i] = ask(1, std::vector<int>{i});
}
for (int i = 2; i <= n; ++i) {
if (rt != i) {
a[i] -= a[1];
}
}
if (rt > 1) a[1] -= a[rt];
std::cout << '!';
for (int i = 1; i <= n; ++i) {
std::cout << ' ' << a[i];
}
std::cout << std::endl;
}
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int T = 1;
std::cin >> T;
while (T--) solve();
return 0;
}
Problem G2 — BAUDELAIRE (Hard Version)
(Author & Analysis: SpyrosAliv)
Read the solution to the Easy Version first.
Obviously, if we know the parent of some node, we know which nodes are under that node's subtree, so we never have to consider them as candidates for the root of the tree. Let's use this to choose nodes in a way such that each time we eliminate as many candidates as possible, even in the worst case.
Specifically, consider querying for the centroid of the tree (a centroid of a tree is a node that if it is deleted, every connected component left has size no more than half of the original tree). When querying for the centroid, there are two cases: either it is the root of the tree, in which case we are finished, or we find its parent, which eliminates at least half of the current candidates. Then, we delete all nodes that could not possibly be the root, and query for the new centroid.
Since the candidates get halved each time, we repeat the above process no more than $$$\log n$$$ times. In the absolute worst case (which is not realistic), we make $$$3\log (n) + 3\log (\frac{n}{2}) + 3\log (\frac{n}{4}) + ... + 3$$$ queries. For $$$n = 1000$$$, this is about $$$165$$$ queries. I do want to stress that this case is impossible; the $$$200$$$ queries are pretty loose but I want to allow a lot of different solutions (there are some even better ones than the one I described here, feel free to describe better solutions in the comments).
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<int>> tree, cd;
vector<int> sub, val;
vector<bool> del;
int n, cdRoot = -1;
int ask(vector<int> a) {
int k = a.size();
cout << "? 1 " << k << " ";
for (auto x: a) {
cout << x << " ";
}
cout << endl;
int ans; cin >> ans;
return ans;
}
void toggle(int u) {
cout << "? 2 " << u << endl;
}
void answer(vector<int> ans) {
cout << "! ";
for (int i = 1; i <= n; i++) cout << ans[i] << " ";
cout << endl;
}
void calc_sums(int node, int par = 0) {
sub[node] = 0;
if (del[node]) return;
for (auto next: tree[node]) {
if (next == par) continue;
calc_sums(next, node);
sub[node] += sub[next];
}
sub[node]++;
}
int find_centroid(int node, int sz, int par = 0) {
for (auto next: tree[node]) {
if (next == par || del[next]) continue;
if (sub[next] * 2 >= sz) return find_centroid(next, sz, node);
}
return node;
}
void build(int node, int prev) {
cd[prev].push_back(node);
del[node] = true;
for (auto next: tree[node]) {
if (del[next]) continue;
calc_sums(next, node);
int cent = find_centroid(next, sub[next], node);
build(cent, node);
}
}
bool inspect(vector<int> a, int tog) {
int b4 = ask(a);
toggle(tog);
int aft = ask(a);
int k = a.size();
int must = b4;
if (aft < b4) {
must -= 2 * k;
}
else must += 2 * k;
if (aft != must) return true;
else return false;
}
int find_sus(vector<int> a, int tog) {
int k = a.size();
int lo = 0, hi = k-1;
int ans = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
vector<int> qr;
for (int j = 0; j <= mid; j++) {
qr.push_back(a[j]);
}
if (inspect(qr, tog)) {
ans = mid;
hi = mid-1;
}
else lo = mid+1;
}
return ans;
}
int find_root(int node, int par = 0) {
if (cd[node].empty()) return node;
vector<int> ch;
for (auto next: cd[node]) {
if (next == par) continue;
ch.push_back(next);
}
int sus = find_sus(ch, node);
if (sus == -1) return node;
return find_root(ch[sus], node);
}
void find_vals(int node, int par = 0, int above = 0) {
val[node] -= above;
above += val[node];
for (auto next: tree[node]) {
if (next != par) {
find_vals(next, node, above);
}
}
}
void solve() {
cin >> n;
cd.assign(n+1, {});
tree.assign(n+1, {});
for (int i = 1; i < n; i++) {
int u, v; cin >> u >> v;
tree[u].push_back(v);
tree[v].push_back(u);
}
del.assign(n+1, false);
sub.assign(n+1, 0);
calc_sums(1);
cdRoot = find_centroid(1, n);
build(cdRoot, 0);
int root = find_root(cdRoot);
val.resize(n+1);
for (int i = 1; i <= n; i++) {
val[i] = ask({i});
}
find_vals(root);
answer(val);
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t; cin >> t;
while (t--) solve();
return 0;
}
Thank you for the good contest
the best d3 of 2025 maybe :heart:
The question is great. Thank you for providing an exciting competition.
BlackCat is Hmm! Hope to see void Hmm tomorrow.
Problem statement of E was hilarious
Problem D messed me up for good, however I had fun. It was a great contest, shout out to the team who made it possible.
I think first think the easier version.If the boy can't use magic,the problem can be solved by greedy And this is a routine.The problem wants us to select a position in the middle,usually we can preprocess the prefix and suffix Here's my code https://codeforces.com/contest/2106/submission/317020209
Thanks a lot
I think first think the easier version.If the boy can't use magic,the problem can be solved by greedy
And this is a routine.The problem wants us to select a position in the middle,usually we can preprocess the prefix and suffix
Here's my code https://codeforces.com/contest/2106/submission/317020209
Thank you !
Oh I was hacked.The infinite number is too small
enjoyed the problemset <3
Problem G2 is also solvable in $$$n + 58$$$ queries.
First, we use $$$n$$$ queries to find $$$f(u)$$$ of each node.
For each centroid $$$u$$$, toggle it. Then, to find the subtree that has the root, perform a binary search by querying the new value and comparing it with the value we initially queried. If the root is in the subtree $$$v$$$, then toggling $$$u$$$ does not affect our next queries when searching in subtree $$$v$$$.
To recover the answer, we can compute it from the values we initially queried, then toggle all the toggled nodes.
This process uses $$$\log n + (\log n + \log(\frac{n}{2}) + \dots + 1)$$$ additional queries, which adds up to about $$$58$$$ queries when $$$n = 1000$$$.
My submission: 317066028
orzorzorzorz
I think the argument can be modified to get $$$n + O(\log n)$$$
total queries.
At each stage of the binary search, define a potential to be the number of candidates that we have so far for the root, i.e., the sum of the sizes of all sub-trees that we binary search on.
Suppose we have narrowed down the root to one of $$$k$$$ sub-trees of sizes $$$x_1 \geq x_2 \geq \dots x_k$$$ and that $$$x_1 + x_2 + \dots x_k = m$$$
. In our algorithm, we choose the smallest prefix whose sum is at least $$$m/4$$$ and query if the root is in one of these subtrees. To analyze the query complexity, let's consider the following cases.
Case 1: $$$x_1 \leq m/2$$$ . In this case, the subset that we query has total size at least $$$m/4$$$ (by definition) and at most $$$m/2 + m/4 \leq 3m/4$$$. Hence, regardless of where the root lies, the number of potential candidates reduces to $$$3m/4$$$.
Case 2: $$$x_1 \geq m/2$$$ In this case, we check whether the root is in the sub-tree $$$x_1$$$. If the answer is false, then we are down to at most $$$m/2$$$ candidates. If the answer is true, then in the next query we will be in Case 1 after centroid decomposition of the root at $$$x_1$$$.
Hence, after every two binary searches, the number of candidates reduces by a factor of $$$3/4$$$. This leads to at most $$$n + 2 \cdot \log_{4/3} n$$$ queries which is at most $$$n + 48$$$ for $$$n \leq 1000$$$. (Sigh, the $$$48$$$ is much larger than I was hoping and sadly not dramatically different from $$$58$$$).
I modified your submission and added an assert and this passes all cases.
For analysis, I suspect the $$$1/4$$$ factor is optimal, because we only have a guarantee of at most $$$1/2$$$ after centroid decomposition, so using say a different factor $$$\lambda$$$ the best we could get is $$$\max(\lambda, 1/2 - \lambda)$$$ which is minimized at $$$\lambda = 1/4$$$. Not sure if the constant can be made better.
the same works if we find the root first and then calculate our answer
E is a nice problem, But I made a stupid mistake on it.
For problem D, Can we do binary search on the beauty of flower that needs to be inserted? I was trying to solve it this way but WA on Test case 2.
Yes, you can. I used DP to make a function f that, given a value x, determines if it is possible to solve the instance by creating a flower of value x. Then, after checking if the instance is solvable (by running f on the maximal beauty of the second array), I binsearch on f to find the smallest x such as f(x)=true. It passed all the tests.
I solved it with binary search the answer (317002102)
Without adding DP? is there any easier version of this?
...
it is hard to check without using DP, because you have to find the optimal position to use the operation, i don't think greedy will work and i haven't figure out any other way during the contest.
Thanks...! I wasted my whole time thinking on Binary Search.. and I dont know DP mainly.
yes, it is possible.
https://codeforces.com/contest/2106/submission/317091954
Thank you guys for providing the solution. I was trying entirely different approach. Everytime I come across undesirable condition i.e. b(j)>a(i), I tried to use magic and kept track of index for which it's been used and then releasing this magic if possible for future. This is where I got stuck, couldn't implement it nicely.
https://codeforces.com/contest/2106/submission/317067927
Am I completely wrong or is it doable like this? Ofc needs some improvement in Check function.
ok, if I am not wrong the check function of Binary Search create's dp array with state for every index if it consumes the magic or not, right ?
Best div3 till now for me, ig. Couldn't get time to solve D, but yeah, understood what happened :D
in the E problem, it says "For each query, output the minimum integer d that Cow the Nerd must choose so that f(l,r,k) can be successful", but in second test case, 1st query, it says answer is 2 because we have changed 2 elements, but the value of d should be 3 because we are changing elements before index 3, how is answer equal to 2? what do we have to answer? the number of minimum elements that are changed or the minimum index before which numbers are changed?
The integer $$$d$$$ represents the number of elements chosen and then swapped, not the index.
Thanks for a great contest!
I liked C.
I misread E which made it buffed , i want to suggest it and its approach anyways.
basically consider the rearrangements to be allowed in only $$$l$$$ and $$$r$$$ rather than $$$1$$$ to $$$n$$$ that way you will have to use a segment tree to obtain the amount of elements greater and less than $$$x$$$ in the given range, and then use same logic.
Time complexity : $$$n *(log{n})^2$$$
Space complexity : $$$n *log{n}$$$
Yep, did the same mistake and abandoned the problem as too hard.
Hello, when were the changes made in problem c?
Since it was stated in the beginning that a and b are complementary, i thought the obvious answer for no loss of elements is 0. At first i assumed there is at least one loss of element since it is stated that there is a loss of elements. But after a "Wrong Answer" i still added the case for no loss of elements. Of course, I still made a mistake of my own. But i still didn't notice when the changes were made?
You can also solve G1 in $$$n + 2$$$ queries. First query node 1, if the result is 1 or -1 then it is the root and you can find all other node values in $$$n - 1$$$ queries. Otherwise, if the result is not 0, toggle it so that it is. Now query all nodes other than node 1: if it is the root, then its value is clearly equal to the query result, and if it is not the root, then the query result is its value + (value of node 1 + value of root) = its value + 0 = its value. Finally we can find the value of node 1 in 2 extra queries if we didn't need to toggle it earlier.
Submission: 317084942
I did the same: 317072800
(Now I can brag I think like an International Grandmasters.)
I did that too lol. But after the contest, and in Python. Only had 8 minutes left when I got to that question so I basically just wrote out my notes and watched the clock tick down.
Submission
I did the same 317056650
Wait, aren't you the guy who made Minecraft in Minecraft?
yes
orz
orz
orz
Did the same. Node 1 being singled out in the statement made it more tempting than enough to base my solution around it.
How come so many solutions of Problem C are being hacked? mine too got hacked :(
2 1000000000
0 500000000
-1 -1
The answer is 500000001. You iterate over this answer. This alone would probably take the whole time limit(to be safe assume like 10^8 operations per second). Now imagine 10000 testcases like this.
Nvm, these are pretty fast operations, so one test like this is fine, but there can be a lot of tests and only the sum of n is bounded, not sum of k
I also see some python solutions with set getting hacked, I think it's antihash
After having non finite amount of testers too many mistakes in problem statements.Wasted too much time. Disappointed :(
It's true, there were a lot of last minute changes, so the testers didn't get to see the latest versions. I apologize for any inconveniences caused, and I hope they didn't affect the quality and enjoyability of the round too much.
E is a good problem, I like it.
implementations are not loading so can anyone check my code for D? I used prefix and suffix arrays which record till which flower from the beginning we can get and from which flower to the end we can get resp. Then iterate for each flower and keep minimum valid one to plant. Failed on test2. https://codeforces.com/contest/2106/submission/317078271
Here the logic is wrong.The else is based on the outside "if".So if (a[i] >= b[j ]) is true and (j < m) is wrong,left[i] will be undefined
You can write if(a[i]>=b[j] && j<m)
Thanks! I fixed that. There were 2 more indexing errors: 1.
j < mshould bej <= mas b is one based. 2.int chk2 = lower_bound(right.begin() + chk, right.end) - right.begin()should beint chk2 = lower_bound(right.begin() + chk + 1, right.end()) - right.begin()Mann, I feel bad I didn't get these during the contest. would do better next time.
I'm newbie, but E is the most interesting binary search problem I've ever seen.
Similar interesting problem on binary search — 1945E - Binary Search
can any one tell me that is
Problem C — CHERRY BOMB can't be done by binary Search
I try but fails on some test case
this is my logic
i did using binary search
https://codeforces.com/contest/2106/submission/317013039
Thanks grate approch when I dry run I knew there is BS but don't able to know where I do mistake looking to your solution is very helpfull
I have a solution for F without DSU or prefix sums, just three variables: https://codeforces.com/contest/2106/submission/317081638 . Idea is the same as in editorial, and also all the possible transitions (00, 01, 10, 11) change connected component sizes in a very particular way. Hope it will stand against hacks
You can solve it in an even easier way taking advantage of the fact that any "1" essentially means we should swap upper and lower components, abandon the lower and continue the upper.
https://codeforces.com/contest/2106/submission/317101894
Here is an easier solution to F : 317055960
The approach is that, at any position, there is at max one lower half of ongoing 0s and one upper half of ongoing 0s, so I just keep on updating the number of 0s in the lower and upper half for each index, and the answer is max value of the upper/lower half accross all indexes.
Really liked the problem :)
I also wonder why DSU or prefix sums is needed here. Since every column contains just either 1 or 2 consecutive segments of 0's, we can iterate columns from left to right and keep track of such segments, adding amount of 0's from previous column segment to the current column segment if and only if these segments intersect. Here is the code: https://codeforces.com/contest/2106/submission/317063909
Same approach for F. This approach is very easy to implement and no need for algorithm (very beautiful!). I think it should add to editorial.
Searching for this comment — I loved this question and expected this to be the intended solution. I hope the coordinators include this as an alternate solution.
Here is a C++ implementation of the same algorithm : 317097588
For problem C, I found it easier to think of it like this:
It's clear that if we know the sum $$$x$$$ then there is at most one way to fill in the blanks. We can calculate the possible values of $$$x$$$ for each index independently and merge them.
If $$$b_i = -1$$$, then $$$s = a_i + b_i$$$ must be in range $$$[a_i .. a_i + k]$$$ because $$$b_i$$$ must be between 0 and $$$k$$$.
If $$$b_i ≠ -1$$$, then $$$s = a_i + b_i$$$ which is just the singular range: $$$[a_i + b_i .. a_i + b_i] $$$.
The number of solutions is given by the intersection of those ranges, which can be computed as the maximum of the lower bounds and minimum of the upper bounds.
C++ code: 316991209
Did the same thing in the contest
W problemset, had so much fun!
Alternate algorithm for G2 to find the root: Find the Heavy light decomposition of the tree. Arbitrarily root the tree at 1. Lets say you know that the actual root is in the subtree of x. First, binary search on the heavy path that contains node x, to find the last node y on this path which is an ancestor of the actual root. Then, binary search on the child subtrees of y which aren't its heavy subtree, to find the child subtree which contains the actual root.
The number of times this process will be repeated is O(log n), as the size of the subtree is divided by at least 2 after each iteration. Therefore this takes O(log^2 n) queries.
Tyler the creator reference?
We can solve G2 in $$$N + 3log(N)$$$ queries, which is about $$$N+30$$$ = 1030 queries.
STEP 1)
STEP 2)
Submission: 317054904
It is not always possible to find subtrees of size exactly n/2, e.g. all subtrees could have size n/3.
It is easy to show that we can at least remove 1/4 of the vertices; if we sort the subtrees in descending order (by size) and take while the new sum is less than n/2, we take at least n/4 vertices (assume that we took less, then the next biggest subtrees has size <1/4 so we can take that).
But this would mean that you need around 3 * 24 queries to find the root.
Yes right, I did same approach, but made mistake in analysis, thank you for pointing out the mistake.
There is a very clean and easy solution for G1.
Sorry, for bad English.
It was a good one but i still cant believe that why for the observation 3 in problem 3, (k+mina)-(maxa-mina) couldn't worked out instead of k−(mxa−mna)+1.
I think problem F is so nice,I used extended DSU to deal with it. I enjoyed it so much.
Hi! Does anyone have a dp solution of problem D?
:D
for fixed
k, we can usedpto check whether we can pickmflowers inO(n)time.Let
dp[i][0]: amount of flowers we picked without using magic when walked to i-th flowerdp[i][1]: amount of flowers we picked that we have used magic when walked to i-th flowerThen we have:
dp[i][j] = dp[i-1][j] + 1IFb[dp[i-1][j]] <= a[i]dp[i][j] = dp[i-1][j]IFb[dp[i-1][j]] > a[i]dp[i][1] = max(dp[i][1],dp[i][0]+1)IFb[dp[i][0]]<=k(that is if we use magic)Note that we can use magic at
n+1positions so the last trainsmition needed for all i from 0 to n.And then we do binary-search on
kto solve the problem. Total time complexity isO(nlogA)You can simplify dp process by only record
dp[i][0]anddp[i][1]values when i iter from 1 to n. Here's my code for this approach 317052110I dont know but problem D felt way too hard for a div3 contest
i love this contest
G1&G2 are great problems! Solution of G2 can be figured out much more easily with the inspiration of G1.
Why hasn't the implementation code uploaded yet?
The codes will be posted after the hacking phase is over.
I have a simpler solution for G1.
At the beginning, first query $$$\texttt{1 1 1}$$$. If the obtained answer $$$\bmod 2 = 0$$$, then $$$1$$$ is not a root, otherwise it is.
If $$$1$$$ is not a root, we first set $$$v_1 + v_{root} = 0$$$. We can complete this by at most one operation $$$\texttt{2 1}$$$.
Then for each $$$2\leq i\leq n$$$, we query $$$\texttt{1 1 i}$$$. Obviously, the obtained answer is $$$r_i$$$.
Then we can finish it in $$$O(n)$$$ times.
If $$$1$$$ is a root, for each $$$2\leq i\leq n$$$, we query $$$\texttt{1 1 i}$$$. Obviously, the obtained answer is $$$r_i + r_1$$$. Since we know $$$r_1$$$, it is very easy to obtain $$$r_i$$$.
submission:https://codeforces.com/contest/2106/submission/317057915.
Great contest, though I didn't participate in
Hello, can anyone help me to find out what I miss, please T.T ?
problem C, in Test #2, answer must be 1 at subtest 35 but mine returns 3.
Thank you for your help
You missed the case for when there is no b[i]==-1 and also the case where needsum==0
thank you
I am wrong with test case:
1 3 7 0 0 0 0 0 0
just change initial value of needsum to -1, then it will return the right answer
It is really good contest.The question is standard quality.Thank you contest organizers.
For problem E is quite similar to this 1945E - Binary Search
317113829
The key idea for problem E is you can think like this,if we are doing a binary search on a random order array of length n there will also almost log(n) times,if among these log(n) times you can find mid=k then answer is 0 but if not then we can try to do something to make mid=k,but how?For the problem above(1945E) you are allowed to swap k and mid but in this problem k is not allowed to swap so we can try another ways to done it
The idea in this problem to make mid = k is let think out of the box,we think reverse,let assume that in the first iteration mid>k then we will search on [l,mid-1] if k is in this range then we do nothing because we are closing to k otherwise we need to change mid to element which less than k such that allow we change from range [l,mid-1] to [mid+1,r],similary for mid<k,so let us denoted x=number of mid greater than k need to be change and y=number of mid less than k need to be change,obviously x and y can change to each other so the answer is min(x,y)*2+(max(x,y)-min(x,y))*2,for example if x=1,y=2 ,then you can swap the element in x to element in y these cost 2 operation then x=1,y=2 -> x=0,y=1 and after someone become 0 then the remain one need to change will other these cause 2 operation
dp approach for D O(n) 317129437
dp appraoch for F O(n) 317133776
Thankyou for the great contest! Was able to get three problems in Div 3 after a long time. Had taken a hiatus. Would you say the first three were a bit easier than usual?
An amazing solution of Problem F with DP !
Wow!this slution is very amazing!
bro can you please explain this solution?
Start by constructing the matrix
for example
matrix
pay attention to the columns. you will find :
0 : the column is divided into two parts by 1
1 : the column is divided into two parts by 0
We use $$$dp[i][0]$$$ to represent the number of zeros in the top half of column i and $$$dp[i][1]$$$ to represent the number of zeros in the bottom half of column i
0 will contribute $$$i - 1$$$ and $$$n - i$$$ to the upper and lower parts of the previous column, respectively.
1 would contribute $$$1$$$ to the bottom half of the previous column. Since i is traversed backward and forward, this contribution is considered to be added to the top half for columns i+1
So we get the transfer equation
0:
1:
If you are still confused, try to exemplify a simple example yourself and follow the process to get the answer, which can help you understand.
thank you so much for your detailed explanation. I get it now...
sarigga explain chey ra pooka
is there any binary search solution of question D
what is wrong in this submission for E?317165447
Can someone tell why this is giving TLE 317015169 https://codeforces.com/contest/2106/submission/317015169
Anybody can tell me where this solution for E fails? I know it is overcomplicating the problem a little bit, but I can see eventually no difference between it and the editorial
Solution: 317115381
Try it on the following input:
2
dont ever register unrated just because you are not confident... Great contest, hope to see more contest from you in the future!
Can anyone tell me where this solution is failing for C: https://codeforces.com/contest/2106/submission/317190195. I have been stuck finding the testcase in the whole contest. Even still i can't find any difference between the correct code and mine. Thanks in advance
Try it on the following input:
This line is problematic:
Say at first you get a sum of $$$x$$$, then you get a sum of $$$y \neq x$$$ , and finally another sum of $$$y$$$. In this case, the final value for the variable
yeswill betrue, and notfalse.This might explain why the testcase you are failing is expecting you to output
0, whereas your answer is1Solution: 317217812
Why I'm unrated in this contest.I have points and rank,but my rate wasn't change,is there anyone know why? I'm a new guy in codeforces,and I stay up late to participate contests(it begin at 22:35 in china's Beijing time),I don't want my hardworks in vain,please help me.
hey,is there any way i can see all the test cases ,or atleast full text of a test case,my code fails at 2nd testcase 24th input of problem C. btw ,i would be grateful if anybody can check my code and guide me through my error. https://codeforces.com/contest/2106/submission/317335587
I am stuck on problem D
My approach is that i can find the number of flowers in prefix and suffix of each index
Then if prefix[i]+suffix[i]>=m ans=0; else if prefix[i]+suffix[i]==m-1 ans=min(ans,b[i])
Here is my code
https://codeforces.com/contest/2106/submission/317047928
Please help
SpyrosAliv problem E is one of the best binary search problems I have ever met
For E, I solved thinking that my swaps are limited to $$$[L,R]$$$ as well, which ended up in me learning merge sort tree! here's the code if someone is interested, TC: $$$ O((n+Q) \log^2 N)$$$
just put L,R in MST query and voila we can solve for restricted swaps as well!
good contest.
can anyone explain 5th test case of problem D : 5 5 1 2 3 4 5 5 4 3 2 1
why the answer is -1 here.
Since you can use the magic wand only once to raise a flower of beauty k,
In the given test case you provided
Your best shot for solving it is from end of array b You can assign,
However, you are left with b[0] = 5 and b[1] = 4 , since you can use wand only once you may fulfill b[1] = 4 but fixing both of them is not possible.
Hope it helps !
thanks
Hello Codeforces community! I'm having trouble with my solution to problem D — I'm getting a Wrong Answer on test case 2. Submission Link My approach: If a valid answer exists, it must be one of the elements in the array B. So I perform binary search on array B. For each candidate mid, I assume it's the flower that Igor grows using his magic.
Then I check: All elements before mid must be matched with beauties ≥ their respective B[i]. Similarly, for elements after mid. This is what I'm validating in my check function.
If anyone could point out where my logic might be wrong or share a countercase, I'd really appreciate it! Thanks in advance
I ran your submission through the stress test with my accepted solution and I have found a contradicting test case. Here it is:
test failed!
expected: 1
received: 3
test case:
n = 4 and m = 3
a: 1 1 2 3
b: 2 3 1
Ahh!! Got my mistake. Thank You.
i think we can use combinatorics to solve problem A, quite unessesary but it might be intuitive for some people.
Hey please tell me where am i going wrong in D. i make a new array containing pair of number and index of second array, i sorted it. then used binary search low = 0, high = m — 1 on the new array. and used check function to skip the element that comes on index newarray[mid].second. it passes the prestest. but fails to pass the WA2. please tell me where am i going wrong. here is my submission = flower boy
are problems like D not supposed to be intutive ?
whats the reason behind this in tutorial of D
Now, we can delete bj if pj−1<sj+1 (to delete b1 , it must be that s2>0 and to delete bm that pm−1≤n ). We keep the minimum among all deletable values in b . If there does not exist such a value the answer is −1 .Thank you! B was my favourite
In problem E, if k belongs to the range, we can easily solve it, swapping p_i = k and p_m, where m = (l + r) / 2. Am I wrong or these is a hole in task description?