Codeforces Round 1034 (Div. 3) - Editorial

Welcome to the editorial for Codeforces Round 1034 (Div. 3) A,B,C,D,E,F .
Below you'll find explanations, code snippets, and approaches for the problems in this contest. link to the contest -- https://codeforces.com/contest/2123

Problem A - Black Board Game

Statement:
You start with numbers 0 to n−1 on a blackboard. In each round, Alice picks a number a to erase, then Bob picks a number b such that a + b ≡ 3 (mod 4) and erases it too.

This continues in rounds, with both players alternating — if a player can't make a move on their turn, they lose.

The task is to determine who wins (Alice or Bob) assuming both play optimally.

Constraints-> (1≤t≤100); (1≤n≤100)

Approach:

Code:

if(n%4){
    cout<<"Alice"<<endl;
}else{
    cout<<"Bob"<<endl;
}

Problem B - Tournament

Statement:
Players have strengths and compete in elimination rounds. In each round, two players are chosen, and the weaker one is eliminated.

You’re given player j and asked whether it's possible for them to survive until only k players remain.

The answer depends on whether there are at least n - k players stronger than player j, because only weaker or equal players can be eliminated before them.

If fewer than n-k players are stronger, the answer in Yes or No

Constraints-> n, j, and k (2≤n≤2⋅1e5, 1≤j,k≤n); (1≤t≤1e4); (1≤ai≤n).

Approach:

Code:

void solve(){
    int n,j,k;
    cin>>n>>j>>k;

    j--;
    vi v(n);
    inp(v);

    vi temp = v;
    sort(all(temp));
    if(k==1){
        if(v[j]==temp.back()){
            yes();
        }else{
            no();
        }
        return ;
    }

    yes();
}

Problem C - Prefix Min and Suffix Max

Statement:
You're allowed to repeatedly replace a prefix of the array with its minimum, or a suffix with its maximum.

Your goal is to reduce the array to a single element equal to a[i] using these operations.

You must determine for each a[i] whether it's possible to reach [a[i]] using any sequence of valid operations.

Output a binary string of 1s and 0s, where 1 means it's possible for that a[i], otherwise 0.

Constraints-> n(2≤n≤2⋅1e5); (1≤t≤1e4)

Approach:

Code:

vi pre(n+1);
vi suf(n+1);

pre[0]= v[0];
for(int i=0;i<n;i++){
    pre[i+1]= min(v[i],pre[i]);
}

int maxx= v[n-1];
for(int i=n-1;i>=0;i--){
    maxx= max(v[i],maxx);
    suf[i+1]= maxx;
}
string ans="";
for(int i=1;i<=n;i++){
    if(pre[i]==v[i-1] || suf[i]==v[i-1]){
        ans+='1';
    }else{
        ans+='0';
    }

}
cout<<ans<<endl;

Problem D - Binary String Battle

Statement:
Alice and Bob play a game on a binary string. Alice can turn any subsequence of length k into 0s, and Bob can turn any substring of length k into 1s.

They alternate turns (Alice first), and Alice wins if the string becomes all zeros at any point.

Determine which player wins assuming both play optimally.

Alice wins if she can force the string to all zeros before Bob can undo her progress indefinitely.

Constraints-> n(2≤n≤2⋅1e5); (1≤t≤1e4)

Approach:

Code:

vi v(n);
for(int i=0;i<n;i++){
    v[i]= s[i]-'0';
}
vi pre(n+1);
for(int i=0;i<n;i++){
    pre[i+1]= pre[i]+v[i];
}
if(pre[n]<=k){
    cout<<"Alice"<<endl;
    return ;
}
if(n>=2*k){
    cout<<"Bob"<<endl;
    return ;
}

for(int i=0;i<=n-k;i++){
    if((pre[i+k]-pre[i])>=pre[n]-k){
        cout<<"Alice"<<endl;
        return ;
    }
}
cout<<"Bob"<<endl;

Problem E - MEX Count

Statement:
You are given an array and asked to compute how many different MEX values (minimum excluded integers) are possible after removing exactly k elements, for every k from 0 to n.

For each possible number of deletions, you consider all ways to remove k elements and compute the resulting MEX.

The goal is to count how many distinct MEX values are possible for each k.

You need to output this count for every k from 0 to n.

Constraints-> n(1≤n≤2⋅1e5); (1≤t≤1e4)

Approach:

Code:

multiset<int> st;

    vi freq(n+2);
for(int i:v){
    freq[i]++;

    st.insert(i);
}

int mexx=0;
while(st.count(mexx)){
    mexx++;
}



vi vec(n+2,0);

for(int i=0;i<=mexx;i++){
    int temp = st.count(i);
    if(temp < n-i+1){
        vec[temp]++;
        vec[n-i+1]--;
    }
}

int s=0;

for(int i=0;i<=n;i++){
    s+= vec[i];
    cout<<s<<" ";
}
cout<<endl;

Problem F - Minimize Fixed Points

Statement:
You must construct a permutation of numbers 1 to n such that for every i ≥ 2, gcd(p[i], i) > 1.

Additionally, minimize the number of fixed points, where p[i] = i.

The challenge is to ensure this GCD condition while arranging elements so that as few numbers as possible remain in their original position.

You must output any such permutation that satisfies both conditions.

Constraints-> (2≤n≤1e5); (1≤t≤1e4)

Approach:

Code:

set<int> vis;
vi vec(n);

for(int i=0;i<n;i++){
        vec[i] = i+1;

}

for(int i=prime.size()-1;i>=0;i--){
    vi temp;
    for(int j=prime[i];j<=n;j+=prime[i]){
        if(!vis.count(j)){
            vis.insert(j);
            temp.pb(j);
        }
    }

    if(temp.size()<2){
        continue;
    }

    int m= temp.size();
    for(int k=0;k<m;k++){
        int val= temp[(k+1)%m];
        vec[temp[k]-1]= val;
    }
}


display(vec);

Closing Notes

If you have any questions or suggestions about the solutions, feel free to leave a comment below!