[problem:2158A]↵
Idea & Solution: [user:kingmessi,2025-11-29]↵
↵
<spoiler summary="Hint 1">↵
Each red card immediately suspends a player. What is the best way to use $r$ red cards to maximize the number of distinct suspended players?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
A player is suspended after receiving 2 yellow cards. With $y$ yellow cards, what is the maximum number of players you can suspend using only yellows?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
If you add the maximum suspensions from red cards and yellow cards, can this total ever exceed $n$? What should happen with extra cards in that case?↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:2158A]↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
void solve(){↵
int n,y,r;↵
cin >> n;↵
cin >> y >> r;↵
cout << min(n,r+y/2) << "\n";↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
int t;↵
cin >> t;↵
while(t--){↵
solve();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Bonus">↵
How do you calculate the **minimum** number of players suspended from the game possible?↵
</spoiler>↵
↵
[problem:2158B]↵
Idea & Solution: [user:kingmessi,2025-11-29]↵
↵
<spoiler summary="Hint 1">↵
Does the contribution of an element depend on its exact split $(u, v)$, or only on whether $u$ and $v$ are **odd** or **even**?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
If every distinct element contributed its maximum possible amount, what would be the upper bound of the answer?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
Elements with frequency of the form $4k+2$ can be split as $(2k+1,\,2k+1)$, creating $0$ size imbalance.↵
Elements with frequency of the form $4k$ can be split as $(2k-1,\,2k+1)$, creating $2$ size imbalance.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 4">↵
The number of elements with odd total frequency is always even.↵
How can these elements help correct any size imbalance?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 5">↵
In which situation does the size imbalance become impossible to fix, making the upper bound unreachable?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 6">↵
Consider the case when the number of distinct elements with frequency of the form $4k$ is **odd**.↵
What happens if there exists **at least one** element with odd frequency?↵
What happens if there are **no** elements with odd frequency?↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:2158B]↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
void solve(){↵
int n;↵
cin >> n;↵
vector<int> a(2*n);↵
for(int i = 0;i < 2*n;i++){↵
cin >> a[i];↵
}↵
↵
vector<int> cnt(2*n+1);↵
for(auto &x : a)cnt[x]++;↵
↵
int x = 0,y = 0,z = 0;↵
for(int i = 1;i <= 2*n;i++){↵
if(cnt[i] == 0)continue; ↵
if(cnt[i]&1)x++; //odd elements↵
else if(cnt[i]%4)y++; //element of form 4*k + 2↵
else z++; //element of form 4*k ↵
}↵
↵
int ans = x+2*y+2*z;↵
if((z&1) && x == 0)ans -= 2; ↵
cout << ans << "\n";↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
int t;↵
cin >> t;↵
while(t--){↵
solve();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:2158C]↵
Idea & Solution: [user:kingmessi,2025-11-29]↵
↵
<spoiler summary="Hint 1">↵
If Alice makes a move and Bob immediately performs the opposite move on the same index (and vice versa), what happens to the array?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
How does the parity of $k$ affect who makes the last move and therefore who can enforce the final uncancelled change?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
Using the cancellation idea, can the entire game be reduced to a simpler one with exactly $k \bmod 2$ effective moves?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 4">↵
If Alice changes $a_i$, only subarrays containing $i$ can improve. What are the maximum-sum subarrays that **end at $i$** and **start at $i$**, and how can combining them give the best subarray passing through $i$?↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:2158C]↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
void solve(){↵
int n,k;↵
cin >> n >> k;↵
vector<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];↵
k &= 1; //It can be reduced as 0/1 move game↵
↵
vector<long long> L(n); //maximum sum non empty subarray ending at each position↵
for(int i = 0;i < n;i++){↵
L[i] = (i && L[i-1]>0 ? L[i-1] : 0ll) + a[i]; ↵
} ↵
↵
vector<long long> R(n); //maximum sum non empty subarray starting at each position↵
for(int i = n-1;i >= 0;i--){↵
R[i] = (i+1<n && R[i+1]>0 ? R[i+1] : 0ll) + a[i];↵
}↵
↵
if(k == 0){↵
long long ans = *max_element(L.begin(),L.end());↵
cout << ans << "\n";↵
}↵
else{↵
long long ans = LONG_MIN;↵
for(int i = 0;i < n;i++){↵
ans = max(ans,L[i]+R[i]-a[i]+b[i]);↵
}↵
cout << ans << "\n";↵
}↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
int t;↵
cin >> t;↵
while(t--){↵
solve();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Bonus">↵
How do you calculate the final score if goals of Alice and Bob were **swapped**?↵
</spoiler>↵
↵
[problem:2158D]↵
Idea & Solution: [user:kingmessi,2025-11-29] and [user:abc864197532,2025-11-29]↵
↵
<spoiler summary="Hint 1">↵
Instead of directly transforming $s$ into $t$, is it enough to know how to transform any string into an intermediate string?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
If you know how to turn any string into $0^n$ in at most $n$ operations, how can you use that to transform $s$ into $t$ in at most $2n$ operations?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
If there is at least one position $p$ with $s_p = s_{p+1}$. Can you grow a block of equal bits starting from $[p, p+1]$?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 4">↵
How do you ensure such a position $p$ in strictly alternating string after exactly one operation?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 5">↵
When trying to grow the block to the right (or left), what happens if the next bit is equal to the block's boundary bit? ↵
What if it is different? Can you use flipping a palindromic block (all equal bits) to force the boundary to match the next bit?↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:2158D]↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
vector<array<int,2>> reduce(string &s){↵
int n = s.size();↵
vector<array<int,2>> op;↵
↵
int p = -1; // position p such that two consecutive characters are same↵
for(int i = 0;i < n-1;i++){↵
if(s[i] == s[i+1])p = i;↵
}↵
if(p == -1){ // string is alternating↵
op.push_back({0,2}); // substring of first three character must be palindrome↵
s[0] ^= 1;s[1] ^= 1;↵
p = 2;↵
}↵
↵
char value = s[p+1];↵
int L = p,R = p+1; // We maintain [L,R] such that all position in it have the same value↵
↵
while(R+1 < n){↵
if(s[R+1] != value)op.push_back({L,R});↵
R++;value = s[R];↵
}↵
↵
while(L){↵
if(s[L-1] != value)op.push_back({L,R});↵
L--;value = s[L];↵
}↵
↵
if(value == '1')op.push_back({0,n-1}); // We want to make all zeroes↵
↵
return op;↵
}↵
↵
void solve(){↵
int n;↵
cin >> n;↵
string s,t;↵
cin >> s >> t;↵
↵
auto operation_s = reduce(s); // operations to reduce s to all zeroes↵
auto operation_t = reduce(t); // operations to reduce t to all zeroes↵
↵
reverse(operation_t.begin(),operation_t.end());↵
↵
int moves = operation_s.size() + operation_t.size();↵
cout << moves << "\n";↵
for(auto &[x,y] : operation_s)cout << x+1 << " " << y+1 << "\n";↵
for(auto &[x,y] : operation_t)cout << x+1 << " " << y+1 << "\n";↵
↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
int t;↵
cin >> t;↵
while(t--){↵
solve();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:2158E]↵
Idea & Solution: [user:kingmessi,2025-11-29]↵
↵
<spoiler summary="Hint 1">↵
How would you solve the problem if every value in the grid was distinct?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
When some cells have the same value, is it natural to treat a connected component of equal valued cells as a single group? ↵
For such a group, how can you decide whether this entire group **needs** a hole?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
After a single query (decreasing the value of one cell), can the beauty increase by more than 1? ↵
How many groups from previous grid can stop needing a hole because they now have a strictly smaller neighbour? ↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 4">↵
How can you model the evolution of the grid as a graph, where edges reflect either adjacency in the grid or "time adjacency" between different versions of the same cell?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 5">↵
If a cell receives $k$ decreasing updates over all queries, can you model it as a chain of $k+1$ nodes (one per value over time)? ↵
How does connecting each new node to the latest versions of its neighbours help you maintain connected components of equal values efficiently?↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:2158E]↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
const int N = 400005;↵
int parent[N],siz[N],important[N],val[N];↵
↵
void make_set(int v,int x) {↵
parent[v] = v;siz[v] = 1;important[v] = 1;val[v] = x;↵
}↵
↵
int find_set(int v) {↵
if (v == parent[v])return v;↵
return parent[v] = find_set(parent[v]);↵
}↵
↵
void union_sets(int a, int b) {↵
a = find_set(a);↵
b = find_set(b);↵
if (a != b) {↵
if (siz[a] < siz[b])swap(a, b);↵
parent[b] = a;↵
siz[a] += siz[b];↵
important[a] = min(important[a],important[b]);↵
}↵
}↵
↵
int n,m;↵
↵
vector<array<int,2>> neighbours(int r,int c){↵
vector<array<int,2>> v;↵
if(r)v.push_back({r-1,c});↵
if(r+1 < n)v.push_back({r+1,c});↵
if(c)v.push_back({r,c-1});↵
if(c+1 < m)v.push_back({r,c+1});↵
return v;↵
}↵
↵
void solve()↵
{↵
cin >> n >> m;↵
vector<vector<int>> a(n,vector<int>(m)); // latest value of a given cell↵
vector<vector<int>> ls(n,vector<int>(m)); // latest node created for a given cell↵
for(int i = 0;i < n;i++){↵
for(int j = 0;j < m;j++){↵
cin >> a[i][j];↵
ls[i][j] = m*i+j;↵
}↵
}↵
↵
for(int i = 0;i < n;i++){↵
for(int j = 0;j < m;j++){↵
make_set(m*i+j,a[i][j]);↵
for(auto &[p,q] : neighbours(i,j)){↵
if(a[p][q] < a[i][j])important[m*i+j] = 0;↵
} ↵
}↵
}↵
↵
for(int i = 0;i < n;i++){↵
for(int j = 0;j < m;j++){↵
for(auto &[p,q] : neighbours(i,j)){↵
if(a[p][q] == a[i][j])union_sets(m*i+j,m*p+q);↵
}↵
}↵
}↵
↵
int ans = 0;↵
for(int i = 0;i < n;i++){↵
for(int j = 0;j < m;j++){↵
if(parent[m*i+j] == m*i+j)ans+=important[m*i+j];↵
}↵
}↵
↵
cout << ans << "\n";↵
↵
int q;↵
cin >> q;↵
int nd = n*m;↵
↵
for(int i = 0;i < q;i++){↵
int r,c,x;↵
cin >> r >> c >> x;↵
r--;c--;↵
x = a[r][c] - x;↵
set<int> s;↵
↵
int mn = INT_MAX;↵
for(auto &[p,q] : neighbours(r,c)){↵
s.insert(find_set(ls[p][q]));↵
mn = min(mn,a[p][q]);↵
}↵
s.insert(find_set(ls[r][c]));↵
↵
for(auto &y : s){↵
ans -= important[y];↵
}↵
↵
for(auto &y : s){↵
if(val[y] > x)important[y] = 0;↵
}↵
↵
make_set(nd,x);↵
if(mn < x)important[nd] = 0;↵
else important[nd] = 1;↵
↵
↵
for(auto &y : s){↵
if(val[y] == x){↵
union_sets(y,nd);↵
}↵
}↵
↵
a[r][c] = x;↵
ls[r][c] = nd++;↵
↵
s.clear();↵
for(auto &[p,q] : neighbours(r,c)){↵
s.insert(find_set(ls[p][q]));↵
}↵
s.insert(find_set(ls[r][c]));↵
↵
for(auto &y : s){↵
ans += important[y];↵
}↵
↵
cout << ans << "\n";↵
}↵
↵
}↵
↵
signed main(){↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
int t;↵
cin >> t;↵
while(t--)↵
solve();↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:2158F2]↵
Idea & Solution: [user:koderkushy,2025-11-29]↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:2158F2]↵
↵
</spoiler>↵
↵
<spoiler summary="Solution (Python)">↵
↵
~~~~~↵
from copy import deepcopy↵
↵
def get_nums(k: int=10):↵
nums = [↵
2**(i + j) * 3**i * 5**j * 7**(k-1-i) * 11**(k-1-j)↵
for i in range(k) for j in range(k)↵
]↵
↵
return nums↵
↵
def eulerian_paths(max_k: int = 100):↵
paths = [[], [0, 0], [1,1,0,0]]↵
↵
for k in range(3, max_k + 1):↵
path = deepcopy(paths[k - 2])↵
x, y = k-2, k-1↵
↵
if k % 2:↵
path.extend([x, x, y, y])↵
for j in range(1, x, 2):↵
path.extend([j, x, j+1, y])↵
path.append(0)↵
else:↵
path.extend([x, x, 1, y, y])↵
for j in range(2, x, 2):↵
path.extend([j, x, j+1, y])↵
path.append(0)↵
↵
paths.append(path)↵
↵
return paths↵
↵
def path_len(k: int):↵
return 1 + (k*k+k)//2 - (0 if k%2 else k//2-1)↵
↵
if __name__ == "__main__":↵
nums = get_nums(10)↵
paths = eulerian_paths(100)↵
↵
for i in range(1, 101):↵
assert len(paths[i]) == path_len(i)↵
↵
t = int(input())↵
↵
for _ in range(t):↵
n = int(input())↵
↵
l, r = 0, 100↵
while l < r-1:↵
m = r - (r-l)//2↵
if path_len(m) < n:↵
l = m↵
else:↵
r = m↵
↵
path = paths[r]↵
assert len(path) >= n↵
↵
a = [nums[i] for i in path[: n]]↵
print(*a)↵
↵
↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution (C++)">↵
↵
~~~~~↵
#include "bits/stdc++.h"↵
using namespace std;↵
↵
↵
constexpr int64_t poww (int64_t a, int64_t p) {↵
assert(p >= 0);↵
int64_t res = 1;↵
while (p > 0) {↵
if (p & 1) res *= a;↵
a *= a, p >>= 1;↵
}↵
return res;↵
}↵
↵
constexpr int32_t path_len(const int32_t n) {↵
return 1 + (n*n + n) / 2 - (n % 2 ? 0: n/2 - 1);↵
}↵
↵
vector nums(0, 0ll);↵
vector walks(0, vector(0, 0));↵
↵
void load_nums(const size_t p=10) {↵
nums.resize(p * p);↵
↵
for (int i = 0; i < p; ++i)↵
for (int j = 0; j < p; ++j)↵
nums[i * 10 + j] = poww(2,(i+j)) * poww(3,i) * poww(5,j) * poww(7,(9-i)) * poww(11,(9-j));↵
}↵
↵
void load_walks(const size_t max_k=100) {↵
walks.resize(max_k + 1);↵
walks[1] = vector({0, 0});↵
walks[2] = vector({1, 1, 0, 0});↵
↵
for (int k = 3; k <= max_k; k++) {↵
auto& walk = walks[k];↵
walk = walks[k - 2];↵
const int x = k-2, y = k-1;↵
↵
if (k % 2) {↵
walk.push_back(x);↵
walk.push_back(x);↵
walk.push_back(y);↵
walk.push_back(y);↵
for (int j = 1; j < x; j += 2)↵
walk.push_back(j),↵
walk.push_back(x),↵
walk.push_back(j+1),↵
walk.push_back(y);↵
walk.push_back(0);↵
} else {↵
walk.push_back(x);↵
walk.push_back(x);↵
walk.push_back(1);↵
walk.push_back(y);↵
walk.push_back(y);↵
for (int j = 2; j < x; j += 2)↵
walk.push_back(j),↵
walk.push_back(x),↵
walk.push_back(j+1),↵
walk.push_back(y);↵
walk.push_back(0);↵
}↵
}↵
}↵
↵
void solve (const int kase) {↵
↵
int n; cin >> n;↵
↵
int l = 0, r = 100;↵
while (l < r - 1) {↵
int m = r - (r-l) / 2;↵
if (path_len(m) < n)↵
l = m;↵
else↵
r = m;↵
}↵
↵
vector a(n, 0ll);↵
for (size_t i = 0; i < n; ++i) {↵
a[i] = nums[walks[r][i]];↵
cout << a[i] << ' ' ;↵
}↵
↵
vector gcds(n-1, 0ll);↵
for (size_t i = 1; i < n; ++i) {↵
gcds[i-1] = gcd(a[i], a[i - 1]);↵
}↵
↵
assert(set(gcds.begin(), gcds.end()).size() == n-1);↵
↵
cout << '\n';↵
}↵
↵
int main () {↵
ios_base::sync_with_stdio(0), cin.tie(0);↵
↵
load_nums();↵
load_walks();↵
↵
for (size_t i = 1 ; i < 101; ++i)↵
assert(walks[i].size() == path_len(i));↵
↵
int t; cin >> t, assert(t >= 0);↵
for (int i = 0; t--; )↵
solve(++i);↵
↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Idea & Solution: [user:kingmessi,2025-11-29]↵
↵
<spoiler summary="Hint 1">↵
Each red card immediately suspends a player. What is the best way to use $r$ red cards to maximize the number of distinct suspended players?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
A player is suspended after receiving 2 yellow cards. With $y$ yellow cards, what is the maximum number of players you can suspend using only yellows?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
If you add the maximum suspensions from red cards and yellow cards, can this total ever exceed $n$? What should happen with extra cards in that case?↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:2158A]↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
void solve(){↵
int n,y,r;↵
cin >> n;↵
cin >> y >> r;↵
cout << min(n,r+y/2) << "\n";↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
int t;↵
cin >> t;↵
while(t--){↵
solve();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Bonus">↵
How do you calculate the **minimum** number of players suspended from the game possible?↵
</spoiler>↵
↵
[problem:2158B]↵
Idea & Solution: [user:kingmessi,2025-11-29]↵
↵
<spoiler summary="Hint 1">↵
Does the contribution of an element depend on its exact split $(u, v)$, or only on whether $u$ and $v$ are **odd** or **even**?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
If every distinct element contributed its maximum possible amount, what would be the upper bound of the answer?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
Elements with frequency of the form $4k+2$ can be split as $(2k+1,\,2k+1)$, creating $0$ size imbalance.↵
Elements with frequency of the form $4k$ can be split as $(2k-1,\,2k+1)$, creating $2$ size imbalance.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 4">↵
The number of elements with odd total frequency is always even.↵
How can these elements help correct any size imbalance?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 5">↵
In which situation does the size imbalance become impossible to fix, making the upper bound unreachable?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 6">↵
Consider the case when the number of distinct elements with frequency of the form $4k$ is **odd**.↵
What happens if there exists **at least one** element with odd frequency?↵
What happens if there are **no** elements with odd frequency?↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:2158B]↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
void solve(){↵
int n;↵
cin >> n;↵
vector<int> a(2*n);↵
for(int i = 0;i < 2*n;i++){↵
cin >> a[i];↵
}↵
↵
vector<int> cnt(2*n+1);↵
for(auto &x : a)cnt[x]++;↵
↵
int x = 0,y = 0,z = 0;↵
for(int i = 1;i <= 2*n;i++){↵
if(cnt[i] == 0)continue; ↵
if(cnt[i]&1)x++; //odd elements↵
else if(cnt[i]%4)y++; //element of form 4*k + 2↵
else z++; //element of form 4*k ↵
}↵
↵
int ans = x+2*y+2*z;↵
if((z&1) && x == 0)ans -= 2; ↵
cout << ans << "\n";↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
int t;↵
cin >> t;↵
while(t--){↵
solve();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:2158C]↵
Idea & Solution: [user:kingmessi,2025-11-29]↵
↵
<spoiler summary="Hint 1">↵
If Alice makes a move and Bob immediately performs the opposite move on the same index (and vice versa), what happens to the array?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
How does the parity of $k$ affect who makes the last move and therefore who can enforce the final uncancelled change?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
Using the cancellation idea, can the entire game be reduced to a simpler one with exactly $k \bmod 2$ effective moves?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 4">↵
If Alice changes $a_i$, only subarrays containing $i$ can improve. What are the maximum-sum subarrays that **end at $i$** and **start at $i$**, and how can combining them give the best subarray passing through $i$?↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:2158C]↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
void solve(){↵
int n,k;↵
cin >> n >> k;↵
vector<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];↵
k &= 1; //It can be reduced as 0/1 move game↵
↵
vector<long long> L(n); //maximum sum non empty subarray ending at each position↵
for(int i = 0;i < n;i++){↵
L[i] = (i && L[i-1]>0 ? L[i-1] : 0ll) + a[i]; ↵
} ↵
↵
vector<long long> R(n); //maximum sum non empty subarray starting at each position↵
for(int i = n-1;i >= 0;i--){↵
R[i] = (i+1<n && R[i+1]>0 ? R[i+1] : 0ll) + a[i];↵
}↵
↵
if(k == 0){↵
long long ans = *max_element(L.begin(),L.end());↵
cout << ans << "\n";↵
}↵
else{↵
long long ans = LONG_MIN;↵
for(int i = 0;i < n;i++){↵
ans = max(ans,L[i]+R[i]-a[i]+b[i]);↵
}↵
cout << ans << "\n";↵
}↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
int t;↵
cin >> t;↵
while(t--){↵
solve();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Bonus">↵
How do you calculate the final score if goals of Alice and Bob were **swapped**?↵
</spoiler>↵
↵
[problem:2158D]↵
Idea & Solution: [user:kingmessi,2025-11-29] and [user:abc864197532,2025-11-29]↵
↵
<spoiler summary="Hint 1">↵
Instead of directly transforming $s$ into $t$, is it enough to know how to transform any string into an intermediate string?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
If you know how to turn any string into $0^n$ in at most $n$ operations, how can you use that to transform $s$ into $t$ in at most $2n$ operations?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
If there is at least one position $p$ with $s_p = s_{p+1}$. Can you grow a block of equal bits starting from $[p, p+1]$?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 4">↵
How do you ensure such a position $p$ in strictly alternating string after exactly one operation?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 5">↵
When trying to grow the block to the right (or left), what happens if the next bit is equal to the block's boundary bit? ↵
What if it is different? Can you use flipping a palindromic block (all equal bits) to force the boundary to match the next bit?↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:2158D]↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
vector<array<int,2>> reduce(string &s){↵
int n = s.size();↵
vector<array<int,2>> op;↵
↵
int p = -1; // position p such that two consecutive characters are same↵
for(int i = 0;i < n-1;i++){↵
if(s[i] == s[i+1])p = i;↵
}↵
if(p == -1){ // string is alternating↵
op.push_back({0,2}); // substring of first three character must be palindrome↵
s[0] ^= 1;s[1] ^= 1;↵
p = 2;↵
}↵
↵
char value = s[p+1];↵
int L = p,R = p+1; // We maintain [L,R] such that all position in it have the same value↵
↵
while(R+1 < n){↵
if(s[R+1] != value)op.push_back({L,R});↵
R++;value = s[R];↵
}↵
↵
while(L){↵
if(s[L-1] != value)op.push_back({L,R});↵
L--;value = s[L];↵
}↵
↵
if(value == '1')op.push_back({0,n-1}); // We want to make all zeroes↵
↵
return op;↵
}↵
↵
void solve(){↵
int n;↵
cin >> n;↵
string s,t;↵
cin >> s >> t;↵
↵
auto operation_s = reduce(s); // operations to reduce s to all zeroes↵
auto operation_t = reduce(t); // operations to reduce t to all zeroes↵
↵
reverse(operation_t.begin(),operation_t.end());↵
↵
int moves = operation_s.size() + operation_t.size();↵
cout << moves << "\n";↵
for(auto &[x,y] : operation_s)cout << x+1 << " " << y+1 << "\n";↵
for(auto &[x,y] : operation_t)cout << x+1 << " " << y+1 << "\n";↵
↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
int t;↵
cin >> t;↵
while(t--){↵
solve();↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:2158E]↵
Idea & Solution: [user:kingmessi,2025-11-29]↵
↵
<spoiler summary="Hint 1">↵
How would you solve the problem if every value in the grid was distinct?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
When some cells have the same value, is it natural to treat a connected component of equal valued cells as a single group? ↵
For such a group, how can you decide whether this entire group **needs** a hole?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
After a single query (decreasing the value of one cell), can the beauty increase by more than 1? ↵
How many groups from previous grid can stop needing a hole because they now have a strictly smaller neighbour? ↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 4">↵
How can you model the evolution of the grid as a graph, where edges reflect either adjacency in the grid or "time adjacency" between different versions of the same cell?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 5">↵
If a cell receives $k$ decreasing updates over all queries, can you model it as a chain of $k+1$ nodes (one per value over time)? ↵
How does connecting each new node to the latest versions of its neighbours help you maintain connected components of equal values efficiently?↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:2158E]↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
const int N = 400005;↵
int parent[N],siz[N],important[N],val[N];↵
↵
void make_set(int v,int x) {↵
parent[v] = v;siz[v] = 1;important[v] = 1;val[v] = x;↵
}↵
↵
int find_set(int v) {↵
if (v == parent[v])return v;↵
return parent[v] = find_set(parent[v]);↵
}↵
↵
void union_sets(int a, int b) {↵
a = find_set(a);↵
b = find_set(b);↵
if (a != b) {↵
if (siz[a] < siz[b])swap(a, b);↵
parent[b] = a;↵
siz[a] += siz[b];↵
important[a] = min(important[a],important[b]);↵
}↵
}↵
↵
int n,m;↵
↵
vector<array<int,2>> neighbours(int r,int c){↵
vector<array<int,2>> v;↵
if(r)v.push_back({r-1,c});↵
if(r+1 < n)v.push_back({r+1,c});↵
if(c)v.push_back({r,c-1});↵
if(c+1 < m)v.push_back({r,c+1});↵
return v;↵
}↵
↵
void solve()↵
{↵
cin >> n >> m;↵
vector<vector<int>> a(n,vector<int>(m)); // latest value of a given cell↵
vector<vector<int>> ls(n,vector<int>(m)); // latest node created for a given cell↵
for(int i = 0;i < n;i++){↵
for(int j = 0;j < m;j++){↵
cin >> a[i][j];↵
ls[i][j] = m*i+j;↵
}↵
}↵
↵
for(int i = 0;i < n;i++){↵
for(int j = 0;j < m;j++){↵
make_set(m*i+j,a[i][j]);↵
for(auto &[p,q] : neighbours(i,j)){↵
if(a[p][q] < a[i][j])important[m*i+j] = 0;↵
} ↵
}↵
}↵
↵
for(int i = 0;i < n;i++){↵
for(int j = 0;j < m;j++){↵
for(auto &[p,q] : neighbours(i,j)){↵
if(a[p][q] == a[i][j])union_sets(m*i+j,m*p+q);↵
}↵
}↵
}↵
↵
int ans = 0;↵
for(int i = 0;i < n;i++){↵
for(int j = 0;j < m;j++){↵
if(parent[m*i+j] == m*i+j)ans+=important[m*i+j];↵
}↵
}↵
↵
cout << ans << "\n";↵
↵
int q;↵
cin >> q;↵
int nd = n*m;↵
↵
for(int i = 0;i < q;i++){↵
int r,c,x;↵
cin >> r >> c >> x;↵
r--;c--;↵
x = a[r][c] - x;↵
set<int> s;↵
↵
int mn = INT_MAX;↵
for(auto &[p,q] : neighbours(r,c)){↵
s.insert(find_set(ls[p][q]));↵
mn = min(mn,a[p][q]);↵
}↵
s.insert(find_set(ls[r][c]));↵
↵
for(auto &y : s){↵
ans -= important[y];↵
}↵
↵
for(auto &y : s){↵
if(val[y] > x)important[y] = 0;↵
}↵
↵
make_set(nd,x);↵
if(mn < x)important[nd] = 0;↵
else important[nd] = 1;↵
↵
↵
for(auto &y : s){↵
if(val[y] == x){↵
union_sets(y,nd);↵
}↵
}↵
↵
a[r][c] = x;↵
ls[r][c] = nd++;↵
↵
s.clear();↵
for(auto &[p,q] : neighbours(r,c)){↵
s.insert(find_set(ls[p][q]));↵
}↵
s.insert(find_set(ls[r][c]));↵
↵
for(auto &y : s){↵
ans += important[y];↵
}↵
↵
cout << ans << "\n";↵
}↵
↵
}↵
↵
signed main(){↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
int t;↵
cin >> t;↵
while(t--)↵
solve();↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:2158F2]↵
Idea & Solution: [user:koderkushy,2025-11-29]↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:2158F2]↵
↵
</spoiler>↵
↵
<spoiler summary="Solution (Python)">↵
↵
~~~~~↵
from copy import deepcopy↵
↵
def get_nums(k: int=10):↵
nums = [↵
2**(i + j) * 3**i * 5**j * 7**(k-1-i) * 11**(k-1-j)↵
for i in range(k) for j in range(k)↵
]↵
↵
return nums↵
↵
def eulerian_paths(max_k: int = 100):↵
paths = [[], [0, 0], [1,1,0,0]]↵
↵
for k in range(3, max_k + 1):↵
path = deepcopy(paths[k - 2])↵
x, y = k-2, k-1↵
↵
if k % 2:↵
path.extend([x, x, y, y])↵
for j in range(1, x, 2):↵
path.extend([j, x, j+1, y])↵
path.append(0)↵
else:↵
path.extend([x, x, 1, y, y])↵
for j in range(2, x, 2):↵
path.extend([j, x, j+1, y])↵
path.append(0)↵
↵
paths.append(path)↵
↵
return paths↵
↵
def path_len(k: int):↵
return 1 + (k*k+k)//2 - (0 if k%2 else k//2-1)↵
↵
if __name__ == "__main__":↵
nums = get_nums(10)↵
paths = eulerian_paths(100)↵
↵
for i in range(1, 101):↵
assert len(paths[i]) == path_len(i)↵
↵
t = int(input())↵
↵
for _ in range(t):↵
n = int(input())↵
↵
l, r = 0, 100↵
while l < r-1:↵
m = r - (r-l)//2↵
if path_len(m) < n:↵
l = m↵
else:↵
r = m↵
↵
path = paths[r]↵
assert len(path) >= n↵
↵
a = [nums[i] for i in path[: n]]↵
print(*a)↵
↵
↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution (C++)">↵
↵
~~~~~↵
#include "bits/stdc++.h"↵
using namespace std;↵
↵
↵
constexpr int64_t poww (int64_t a, int64_t p) {↵
assert(p >= 0);↵
int64_t res = 1;↵
while (p > 0) {↵
if (p & 1) res *= a;↵
a *= a, p >>= 1;↵
}↵
return res;↵
}↵
↵
constexpr int32_t path_len(const int32_t n) {↵
return 1 + (n*n + n) / 2 - (n % 2 ? 0: n/2 - 1);↵
}↵
↵
vector nums(0, 0ll);↵
vector walks(0, vector(0, 0));↵
↵
void load_nums(const size_t p=10) {↵
nums.resize(p * p);↵
↵
for (int i = 0; i < p; ++i)↵
for (int j = 0; j < p; ++j)↵
nums[i * 10 + j] = poww(2,(i+j)) * poww(3,i) * poww(5,j) * poww(7,(9-i)) * poww(11,(9-j));↵
}↵
↵
void load_walks(const size_t max_k=100) {↵
walks.resize(max_k + 1);↵
walks[1] = vector({0, 0});↵
walks[2] = vector({1, 1, 0, 0});↵
↵
for (int k = 3; k <= max_k; k++) {↵
auto& walk = walks[k];↵
walk = walks[k - 2];↵
const int x = k-2, y = k-1;↵
↵
if (k % 2) {↵
walk.push_back(x);↵
walk.push_back(x);↵
walk.push_back(y);↵
walk.push_back(y);↵
for (int j = 1; j < x; j += 2)↵
walk.push_back(j),↵
walk.push_back(x),↵
walk.push_back(j+1),↵
walk.push_back(y);↵
walk.push_back(0);↵
} else {↵
walk.push_back(x);↵
walk.push_back(x);↵
walk.push_back(1);↵
walk.push_back(y);↵
walk.push_back(y);↵
for (int j = 2; j < x; j += 2)↵
walk.push_back(j),↵
walk.push_back(x),↵
walk.push_back(j+1),↵
walk.push_back(y);↵
walk.push_back(0);↵
}↵
}↵
}↵
↵
void solve (const int kase) {↵
↵
int n; cin >> n;↵
↵
int l = 0, r = 100;↵
while (l < r - 1) {↵
int m = r - (r-l) / 2;↵
if (path_len(m) < n)↵
l = m;↵
else↵
r = m;↵
}↵
↵
vector a(n, 0ll);↵
for (size_t i = 0; i < n; ++i) {↵
a[i] = nums[walks[r][i]];↵
cout << a[i] << ' ' ;↵
}↵
↵
vector gcds(n-1, 0ll);↵
for (size_t i = 1; i < n; ++i) {↵
gcds[i-1] = gcd(a[i], a[i - 1]);↵
}↵
↵
assert(set(gcds.begin(), gcds.end()).size() == n-1);↵
↵
cout << '\n';↵
}↵
↵
int main () {↵
ios_base::sync_with_stdio(0), cin.tie(0);↵
↵
load_nums();↵
load_walks();↵
↵
for (size_t i = 1 ; i < 101; ++i)↵
assert(walks[i].size() == path_len(i));↵
↵
int t; cin >> t, assert(t >= 0);↵
for (int i = 0; t--; )↵
solve(++i);↵
↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
