This happened to me too, when I was in Gold. Now I'm in Plat and I solve exactly zero problems each contest.

Same! except generally I get luckier on the us open. I wish us both good luck :D

By not asking the solution when the contest is going on :))

Hi, I solved it so maybe I can help you, but I've now forgotten which was the second lol. Was it the one where you were given two strings with letters from a to r and had to answer some queries and say yes if the strings were the same taking into account only the letters given in the query? For that problem, the observation I made was that, for a string to be equal with letters abc, it also has to be equal for ab, ac and bc (maybe it could be further simplified but I'm not sure). With that observation it sufficed to check if the strings were equal for each pair of letters from a to r, which can be done in O(18^2 * n) where n is the size of the largest string.

After precomputation, for each query just check if for every pair of letters of the query, both strings were equal, using the precomputed information.

I hope it helped, I'm not sure if I've explained myself clearly.

(I've checked thrice and I think the contest has ended but if it's still going on pls tell me soon so I can delete all of this lol)

precomputation on all 18^2 pairs of letters

If you can change any letter to the other two letters, that means that those two letters = the first letter (WO = C, WC = O, CO = W). Same letter pairs can be ignored, so you skip them or use another letter to represent a "void" and then take it into account when joining letters(so you won't join a letter with a void). So the brute-force approach would be to divide the length of the string by two each time, by transforming two letters into one until there's only one letter left, if it's C then answer is YES, if not then answer is NO. That would pass for tests 1-5 or something like that.

The same approach could be optimized by using data structures as segment tree (and probably sparse table too).

That approach is the one I used, but I've got the feeling that there's probably a better one, if anyone has another approach pls comment it down :)

UPD: From a comment that I've seen down below, the order of operations doesn't matter so you can just keep joining letters and there's no need of data structures. Now I feel dumb lol :(

If you notice the operation between two characters in the string was nothing but the XOR of them. Since C(1) ≡ O(2)W(3) , CC ≡ ""(0) , also the order of operation doesn't matter here , so we can just check if XOR of S[L..R] == 1(C) or not.

For any two adjacent letters, we can always swap them using some operations:

XY -> XZX -> YX

(where X, Y, Z are letters among C, O, W)

so the order of the string doesn't matter because we can always arrange it in the order: "CC..C OO...O WW...W" What matters is the number of C's and O's and W's. Since the same adjacent letters can be deleted, all we need to consider is the parity of the number of C's and O's, and W's, and this quantity can be easily computed using prefix sum for each query.

For each query, there are 8 cases: C, O, W, CO, CW, OW, COW, and void. (order in each string doesn't matter)

CO is equivalent to W

CW is equivalent to O

OW is equivalent to C

COW -> WW -> void

We also need to ensure that C, O, W, and void each can't reach other letters. My proof is below:

During each operation, the parity of the number of C and O doesn't change, because the ways to lose and gain O or C are OO -> void, CC -> void, OC -> W, OW -> C, CW -> O. We can see that the parity doesn't change. same for O and W, and W and C. We don't need to worry too much about void because there is no reverse operation of it. Knowing these, we'll prove the statement by contradiction:

If C can reach W in some operations, the parity of the number of C and O in C is 1, but the parity of the number of C and O in W is 0, which contradicts what we proved above, and the same proof for C O and W O.

My C++ code below:

#include <bits/stdc++.h>
using namespace std;
int pre[(int)2e5+1][3];
int main(){
	string s; int q;
	cin>>s>>q;
	for(int i=1;i<=s.length();i++){
		pre[i][0]=pre[i-1][0];
		pre[i][1]=pre[i-1][1];
		pre[i][2]=pre[i-1][2];
		if(s[i-1]=='C') pre[i][0]++;
		else if(s[i-1]=='O') pre[i][1]++;
		else pre[i][2]++;
	}
	while(q--){
		int l,r; cin>>l>>r;
		bool c=(pre[r][0]-pre[l-1][0])%2;
		bool o=(pre[r][1]-pre[l-1][1])%2;
		bool w=(pre[r][2]-pre[l-1][2])%2;
		if(w&&o&&c||!w&&o&&c||w&&!o&&c||!w&&o&&!c||w&&!o&&!c||!w&&!o&&!c) cout<<"N";
		else cout<<"Y";
	}
}

We can answer each query in O(1) with O(n) pre-computation.

I hope this helps you.

P2 :

First , you need to calculate the scc of the graph. (If one scc has only one vertex , then it is impossible to win ).

Second , if there is a vertex whose out degree is 1 , then merge the vertex and the vertex it can go to .

Keep doing the second step until every vertex's out degree is not equal to 1.

Each query is to check whether u,v is the same vertex.

/**
 *    author:  gary
 *    created: 25.03.2022 21:43:48
**/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define rep(a,b) for(int a=0;a<b;++a)
#define LL long long
#define PB push_back
#define POB pop_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
const int MAXN=1e5+10;
vector<int> rg[MAXN],g[MAXN];
set<int> s[MAXN],rs[MAXN];
int n,m,vis[MAXN],ok[MAXN],fa[MAXN];
stack<int> sta;
void dfs1(int now){
    vis[now]=1;
    for(auto it:g[now]) if(!vis[it]) dfs1(it);
    sta.push(now);
}
void dfs2(int now,vector<int> &v){
    vis[now]=1;
    v.PB(now);
    for(auto it:rg[now]) if(!vis[it]) dfs2(it,v);
}
int root(int x){return fa[x]=(fa[x]==x? x:root(fa[x]));}
queue<int> q;
bool inq[MAXN];
int called[MAXN];
void domerge(int u,int v){
    rs[v].erase(u);
    if(rs[u].size()<rs[v].size()){
        for(auto it:rs[u]){
            rs[v].insert(it);
            s[it].erase(called[u]);
            s[it].insert(called[v]);
            if(s[it].size()==1&&!inq[it]) q.push(it);
        }
    }
    else{
        for(auto it:rs[v]){
            rs[u].insert(it);
            s[it].erase(called[v]);
            s[it].insert(called[u]);
            if(s[it].size()==1&&!inq[it]) q.push(it);
        }
        called[v]=called[u];
        rs[v].swap(rs[u]);
    }
    fa[u]=v;
}
int main(){
    scanf("%d%d",&n,&m);
    vector<mp> edge;
    rb(i,1,m){
        int u,v;
        scanf("%d%d",&u,&v);
        edge.PB(II(u,v));
        g[u].PB(v);
        rg[v].PB(u);
    }
    rb(i,1,n) if(!vis[i]) dfs1(i);
    memset(vis,0,sizeof(vis));
    while (!sta.empty()){
        int now=sta.top();
        sta.pop();
        if(!vis[now]){
            vector<int> comp;
            dfs2(now,comp);
            if(comp.size()>1){
                for(auto it:comp) ok[it]=1;
            }
        }
    }
    rb(i,1,n) if(ok[i]) q.push(i);
    while (!q.empty()){
        int now=q.front();
        q.pop();
        for(auto it:rg[now]) if(!ok[it]) ok[it]=1,q.push(it);
    }
    for(auto it:edge){
        int u,v;
        tie(u,v)=it;
        if(ok[u]&&ok[v]){
            s[u].insert(v);
            rs[v].insert(u);
        }
    }
    rb(i,1,n) fa[i]=i,called[i]=i;
    rb(i,1,n) if(s[i].size()==1) inq[i]=1,q.push(i);
    while (!q.empty()){
        int now=q.front();
        inq[now]=0;
        q.pop();
        if(root(now)!=now) continue;
        if(s[now].size()==1&&root(now)!=root(*s[now].begin())) domerge(root(now),root(*s[now].begin()));
    }
    int Q;
    scanf("%d",&Q);
    while (Q--){
        int u,v;
        scanf("%d%d",&u,&v);
        if(!ok[u]||!ok[v]) putchar('B');
        else if(root(u)==root(v)) putchar('B');
        else putchar('H');
    }
    putchar('\n');
    return 0;
}

I got 800 points in the silver division. But why doesn't the information change?