2158A - Suspension Idea & Solution: kingmessi

#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();
    }
}

How do you calculate the minimum number of players suspended from the game possible?

2158B - Split Idea & Solution: kingmessi

Does the contribution of an element depend on its exact split $$$(u, v)$$$, or only on whether $$$u$$$ and $$$v$$$ are odd or even?

If every distinct element contributed its maximum possible amount, what would be the upper bound of the answer?

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.

The number of elements with odd total frequency is always even. How can these elements help correct any size imbalance?

In which situation does the size imbalance become impossible to fix, making the upper bound unreachable?

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?

#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();
    }
}

2158C - Annoying Game Idea & Solution: kingmessi

If Alice makes a move and Bob immediately performs the opposite move on the same index (and vice versa), what happens to the array?

How does the parity of $$$k$$$ affect who makes the last move and therefore who can enforce the final uncancelled change?

Using the cancellation idea, can the entire game be reduced to a simpler one with exactly $$$k \bmod 2$$$ effective moves?

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$$$?

#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();
    }
}

How do you calculate the final score if goals of Alice and Bob were swapped?

2158D - Palindrome Flipping Idea & Solution: kingmessi and abc864197532

Instead of directly transforming $$$s$$$ into $$$t$$$, is it enough to know how to transform any string into an intermediate string?

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?

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]$$$?

How do you ensure such a position $$$p$$$ in strictly alternating string after exactly one operation?

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?

#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();
    }
}

2158E - Sink Idea & Solution: kingmessi

How would you solve the problem if every value in the grid was distinct?

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?

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?

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?

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?

#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;
}

2158F2 - Distinct GCDs (Hard Version) Idea & Solution: koderkushy