After everyone else in the computer lab had many orange-rated handles, I finally achieved orange with my main account (apparently, I'm still quite weak). I'll write a blog post to record the experience.

My counting skills are very poor. In the last 5 minutes of the contest, I hastily came up with a solution for problem F, which later turned out to be much longer than others’ approaches.

A & B & C

Just simulate it.

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std; 
typedef long long ll;
typedef pair<int,int> pii;
template<typename T=int>
T read(){
    char c=getchar();T x=0;
    while(c<48||c>57) c=getchar();
    do x=(x<<1)+(x<<3)+(c^48),c=getchar();
    while(c>=48&&c<=57);
    return x;
}
void solve(){
    ll w=read(),d=read(),h=read();
    ll a=read(),b=read(),f=read(),g=read();
    printf("%lld\n",h+min({abs(a-w)+abs(b-g)+abs(w-f),abs(a-0)+abs(b-g)+abs(f-0),abs(a-f)+abs(b-0)+abs(g-0),abs(a-f)+abs(b-d)+abs(g-d)}));
}
int main(){
    int tc=read();
    while(tc--) solve();
    return 0;
}

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std; 
typedef long long ll;
typedef pair<int,int> pii;
template<typename T=int>
T read(){
    char c=getchar();T x=0;
    while(c<48||c>57) c=getchar();
    do x=(x<<1)+(x<<3)+(c^48),c=getchar();
    while(c>=48&&c<=57);
    return x;
}
const int N=1000003;
int n;
int a[N];
void solve(){
    n=read();
    for(int i=0;i<=n;++i) a[i]=0;
    for(int i=1;i<=n;++i) ++a[read()];
    for(int i=1;i<=n;++i) a[i]+=a[i-1];
    int res=0;
    for(int x=0;x<=n;++x){
        int t=a[max(x-1,0)];
        if(t==x&&(!x||a[x]==a[x-1])) ++res;
    }
    printf("%d\n",res);
}
int main(){
    int tc=read();
    while(tc--) solve();
    return 0;
}

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std; 
typedef long long ll;
typedef pair<int,int> pii;
template<typename T=int>
T read(){
    char c=getchar();T x=0;
    while(c<48||c>57) c=getchar();
    do x=(x<<1)+(x<<3)+(c^48),c=getchar();
    while(c>=48&&c<=57);
    return x;
}
const int N=1000003;
int n;
char s[N];
void solve(){
    scanf("%d%s",&n,s+1);
    vector<int> c(26,0);
    vector<pii> t(26);
    for(int i=1;i<=n;++i) ++c[s[i]-97];
    for(int i=0;i<26;++i) t[i]=pii(c[i],i);
    sort(t.begin(),t.end(),greater<pii>());
    ll res=1e18;
    int pos=0;
    for(int x=1;x<=26;++x){
        if(n%x) continue;
        ll ans=0;
        for(int i=0;i<26;++i){
            if(n/x<t[i].fi) ans+=t[i].fi-n/x;
        }
        for(int i=x;i<26;++i) ans+=t[i].fi;
        if(ans<res) pos=x,res=ans;
    }
    vector<int> pp(26,0),stk;
    for(int i=0;i<26;++i){
        if(t[i].fi>n/pos)
            pp[t[i].se]=t[i].fi-n/pos;
        else if(i>=pos)
            pp[t[i].se]=t[i].fi;
        else{
            int tt=n/pos-t[i].fi;
            while(tt--) stk.emplace_back(t[i].se);
        }
    }
    printf("%lld\n",res);
    for(int i=1;i<=n;++i){
        if(pp[s[i]-97]){
            --pp[s[i]-97];
            putchar(stk.back()+97);
            stk.pop_back();
        }
        else putchar(s[i]);
    }
    putchar('\n');
}
int main(){
    int tc=read();
    while(tc--) solve();
    return 0;
}

D

Classic +x problem. Consider differences to find invariants $a_i - a_j$. Decompose and solve all possible values of $x$ through check.

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std; 
typedef long long ll;
typedef pair<int,int> pii;
template<typename T=int>
T read(){
    char c=getchar();T x=0;
    while(c<48||c>57) c=getchar();
    do x=(x<<1)+(x<<3)+(c^48),c=getchar();
    while(c>=48&&c<=57);
    return x;
}
int A[103];
int n;
set<ll> s[103];
void proc(int x,int y){
    int t=A[y]-A[x];
    for(int i=1;i*i<=t;++i)
        if(t%i==0){
            int a=i,b=t/i;
            if((a^b)&1) continue;
            ll p=(b-a)/2;
            ll q=(b+a)/2;
            p*=p;q*=q;
            if(q>=A[y]&&p>=A[x]){
                s[y].emplace(q-A[y]);
                s[x].emplace(p-A[x]);
            }
        }
}
map<ll,int> mp;
void solve(){
    n=read();
    for(int i=1;i<=n;++i) A[i]=read(),s[i].clear();
    int res=1;
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j) proc(i,j);
    mp.clear();
    for(int i=1;i<=n;++i)
        for(ll x:s[i]) ++mp[x];
    for(pair<ll,int> cur:mp) res=max(res,cur.se);
    printf("%d\n",res);
}
int main(){
    int tc=read();
    while(tc--) solve();
    return 0;
}

E

Guess the answer is the union of rectangles.

Consider how to handle intervals in one dimension. If sorted by left/right endpoints, it's hard to extend. With arbitrary order, consider maintaining a set of left/right endpoints: each time adding an interval removes all strictly contained intervals, then adjust the interval’s left/right ends to be the predecessor’s right end +1 and successor’s left end -1.

Thus, first run the above algorithm on intervals where the second dimension is [1,2], then separately run it on [1,1], [2,2] and [1,2].

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std; 
typedef long long ll;
typedef pair<int,int> pii;
template<typename T=int>
T read(){
    char c=getchar();T x=0;
    while(c<48||c>57) c=getchar();
    do x=(x<<1)+(x<<3)+(c^48),c=getchar();
    while(c>=48&&c<=57);
    return x;
}
const int N=400003;
struct rect{
    int u,d,l,r,id;
}s[N];
bool cmp(rect x,rect y){return x.r<y.r;}
bool cmpid(rect x,rect y){return x.id<y.id;}
set<pii> o;
void solve(){
    int n=read();
    for(int i=1;i<=n;++i){
        s[i].u=read();
        s[i].l=read();
        s[i].d=read();
        s[i].r=read();
        s[i].id=i;
    }
    sort(s+1,s+n+1,cmp);
    o.clear();
    for(int i=1;i<=n;++i){
        if(s[i].u==1&&s[i].d==2){
            if(s[i].l<=s[i].r){
                set<pii>::iterator it=o.lower_bound(pii(s[i].l,0));
                while(it!=o.end()&&it->fi<=s[i].r){
                    if(s[it->se].r>s[i].r){s[i].r=it->fi-1;break;}
                    else{s[it->se].u=2;s[it->se].d=1;o.erase(it);}
                    it=o.lower_bound(pii(s[i].l,0));
                }
                it=o.lower_bound(pii(s[i].l,0));
                if(it!=o.begin()) s[i].l=max(s[i].l,s[prev(it)->se].r+1);
            }
            if(s[i].l<=s[i].r) o.emplace(s[i].l,i);
        }
    }
    o.clear();
    for(int i=1;i<=n;++i) if(s[i].u==1&&s[i].d==2&&s[i].l<=s[i].r) o.emplace(s[i].l,i);
    for(int i=1;i<=n;++i){
        if(s[i].u==1&&s[i].d==1){
            if(s[i].l<=s[i].r){
                set<pii>::iterator it=o.lower_bound(pii(s[i].l,0));
                while(it!=o.end()&&it->fi<=s[i].r){
                    if(s[it->se].r>s[i].r){s[i].r=it->fi-1;break;}
                    else{s[it->se].u=2;o.erase(it);}
                    it=o.lower_bound(pii(s[i].l,0));
                }
                it=o.lower_bound(pii(s[i].l,0));
                if(it!=o.begin()) s[i].l=max(s[i].l,s[prev(it)->se].r+1);
            }
            if(s[i].l<=s[i].r) o.emplace(s[i].l,i);
        }
    }
    o.clear();
    for(int i=1;i<=n;++i) if(s[i].u==1&&s[i].d==2&&s[i].l<=s[i].r) o.emplace(s[i].l,i);
    for(int i=1;i<=n;++i){
        if(s[i].u==2&&s[i].d==2){
            if(s[i].l<=s[i].r){
                set<pii>::iterator it=o.lower_bound(pii(s[i].l,0));
                while(it!=o.end()&&it->fi<=s[i].r){
                    if(s[it->se].r>s[i].r){s[i].r=it->fi-1;break;}
                    else{s[it->se].d=1;o.erase(it);}
                    it=o.lower_bound(pii(s[i].l,0));
                }
                it=o.lower_bound(pii(s[i].l,0));
                if(it!=o.begin()) s[i].l=max(s[i].l,s[prev(it)->se].r+1);
            }
            if(s[i].l<=s[i].r) o.emplace(s[i].l,i);
        }
    }
    sort(s+1,s+n+1,cmpid);
    long long res=0;
    for(int i=1;i<=n;++i){
        if(s[i].u<=s[i].d&&s[i].l<=s[i].r)
            res+=(s[i].d-s[i].u+1)*(s[i].r-s[i].l+1);
    }
    printf("%lld\n",res);
    for(int i=1;i<=n;++i){
        if(s[i].u<=s[i].d&&s[i].l<=s[i].r){
            printf("%d %d %d %d\n",s[i].u,s[i].l,s[i].d,s[i].r);
        }
        else puts("0 0 0 0");
    }
}
int main(){
    int tc=read();
    while(tc--) solve();
    return 0;
}

F

Avoid being a guesser.

The original process was hard to maintain, so we directly perform DP on the final bracket sequence.

We match pairs of strings inserted during the same operation, resulting in a structure similar to a valid bracket sequence in the final result.

Suppose for a final string, we simultaneously DP both character states and matching states. Then, the result should be the number of insertion orders for these matches multiplied by the number of such arrangements.

Note that these matches cannot be inserted arbitrarily. For example, in )((), the first and fourth characters must form a match before the middle pair.

These matches form a tree structure, so the number of valid insertion orders equals the number of topological orders of the tree: $n! \prod_{i=1}^n \frac{1}{size_i}$. We can incorporate $\frac{1}{size_i}$ into the DP state.

How to DP? Consider inserting a pair )( or () at the beginning and end of a bracket sequence. The impact on the middle part is equivalent to shifting the prefix sum polyline up/down.

Let $g_{i,j}$ denote the number of bracket sequences of length $2i$, starting and ending with a matching pair (not necessarily valid), with minimum prefix sum $j$.

Let $f_{i,j}$ denote the number of ways to concatenate several $g_{i,j}$ sequences into a total length of $2i$, with minimmum prefix sum $j$.

Inserting a matching pair:

• $\frac{pf_{i,x}}{i+1} \to g_{i+1,x+1}$
• $\frac{(1-p)f_{i,x}}{i+1} \to g_{i+1,x-1}$

Concatenating two sequences:

• $f_{i,x}g_{j,y} \to f_{i+j,\min(x,y)}$

Optimize with prefix sums.

Don’t forget to divide by total arrangements to get probability and multiply by $n!$.

Time complexity: $O(n^3)$.

#include <cstdio>
#include <algorithm>
using namespace std;
int read(){
    char c=getchar();int x=0;
    while(c<48||c>57) c=getchar();
    do x=(x<<1)+(x<<3)+(c^48),c=getchar();
    while(c>=48&&c<=57);
    return x;
}
const int N=503,P=998244353;
typedef long long ll;
int qp(int a,int b=P-2){
    int res=1;
    while(b){
        if(b&1) res=(ll)res*a%P;
        a=(ll)a*a%P;b>>=1;
    }
    return res;
}
int f[N][N],g[N][N],dp[N][N],h[N],inv[N];
int n,p;
void inc(int &x,int v){if((x+=v)>=P) x-=P;}
int pref[N][N],preg[N][N],res[N];
void convol(int t){
    for(int i=0;i<=t;++i)
        for(int j=0;j<=t;++j){
            pref[i][j]=f[i][j];
            preg[i][j]=g[i][j];
            if(j){
                inc(pref[i][j],pref[i][j-1]);
                inc(preg[i][j],preg[i][j-1]);
            }
        }
    for(int i=0;i<t;++i)
        for(int j=0;j<=t;++j){
            inc(f[t][j],(ll)pref[i][j]*g[t-i][j]%P);
            if(j) inc(f[t][j],(ll)preg[t-i][j-1]*f[i][j]%P);
        }
}
int main(){
    n=read();p=(ll)read()*qp(10000)%P;inv[1]=1;
    for(int i=2;i<=n;++i) inv[i]=(ll)inv[P%i]*(P-P/i)%P;
    int res=1;
    f[0][0]=1;
    for(int i=1;i<=n;++i){
        for(int j=0;j<i;++j){
            inc(g[i][max(j-1,0)],(ll)f[i-1][j]*p%P*inv[i]%P);//()
            inc(g[i][j+1],(ll)f[i-1][j]*(P+1-p)%P*inv[i]%P);//)(
        }
        convol(i);
        res=(ll)res*i%P*qp(i+i-1)%P;
    }
    res=(ll)res*f[n][0]%P;
    printf("%d\n",res);
    return 0;
}