Codeforces Round 1037 (Div. 3) - Editorial

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

Problem A - Only One Digit

Statement:
You are given an integer x. You need to find the smallest non-negative integer y such that the numbers x and y share at least one common digit.

In other words, there must exist a decimal digit d that appears in both the representation of the number x and the number y.

Constraints:- t(1≤t≤1000); x (1≤x≤1000)

Code:

int n;
cin>>n;

string s= to_string(n);

char minn= *min_element(all(s));

cout<<minn<<endl;

Problem B - No Casino in the Mountains

Statement:

You're given an array a of length n, where a[i] = 0 means good weather and a[i] = 1 means rain. Jean wants to hike to as many peaks as possible.
Each hike takes exactly k consecutive days of good weather (0s). Additionally, Jean must take a rest day after each hike, meaning no overlapping hikes are allowed.
Find the maximum number of hikes Jean can make.

Constraints:- (1 ≤ t ≤ 10⁴); (1 ≤ n ≤ 10³); (1 ≤ k ≤ n)

Code:

int n,k;
cin>>n>>k;

vi v(n);
inp(v);

vi pre(n+1,0);

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

int c=0;
for(int i=0;i<=n-k;i++){
    if(pre[i+k]-pre[i]==0){
        c++;
        i+=k;
    }
}

cout<<c<<endl;

Problem C - A Good Problem

Statement:
You are given n,l,r,k You need to find the lexicographically smallest array a of length n, consisting of integers, such that:

For every 1≤i≤n , l≤ai≤r
a1&a2&…&an=a1⊕a2⊕…⊕an ,where & denotes the bitwise AND operation and ⊕ denotes the bitwise XOR operation

Constraints-> (1≤k≤n≤1e18,1≤l≤r≤1e18); (1≤t≤1e4)

Approach:
Intuition

You need an array where all numbers are between l and r, and doing AND and XOR over the whole array gives the same result.

This only happens when the extra 1s in XOR (from differing bits) don’t mess up the AND — so mostly, the array needs to be kind of uniform or cleverly bit-aligned.

Steps

If n==1: return l;
If n==2: not possible return -1;
If n is odd, we can pick all values as l — the XOR and AND will match — return l;
If n is even:

-- we need to find two values like [l, l, ..., x, x] where the bit alignment allows AND == XOR.

-- So you find the smallest number x in [l, r] such that it's a power of two or nicely aligned for the condition.

-- If such x exists and k falls into the position of x, return it; otherwise, return l.

Code:

// s = sum(v)
// maxv = max(v);
// then the possible squared distance between start and end lies in [(2×maxv−s)², s²].

int maxx= *max_element(all(v));
int s= accumulate(all(v),(int)0);

int val=0;
val= max(2*maxx-s,val);
s*=s;
val*=val;

int dx= px-qx;
int dy = py-qy;

int sq= dx*dx + dy*dy;

if(sq>=val && sq<= s){
    yes();
    return ;
}
no();

Problem D - Token Removing

Statement:
You're given sequences a of length n where each a[i] is between 0 and i.

For each sequence, you perform n steps where, if a[i] ≠ 0, you remove a token from any position in [a[i], i] (if it hasn't been removed yet).

The "weight" of the sequence is the number of valid ways to remove tokens without conflicts, following those rules.

You're asked to find the sum of weights of all valid sequences, modulo m.

Constraints-> (1≤n≤5000,108≤m≤1.01⋅109); (1≤t≤1000)

Approach:
Intuition

We want to count how many ways tokens can be removed for all valid sequences without generating them explicitly.

since removal depends on available positions and past choices, we use dp to track how many tokens are used at each step.

Approach

Use dp[i][j] = number of ways to handle steps i..n with j tokens already removed.

At each step i, carry forward dp[i+1][j] (do nothing), or

try removing a token using available positions (n - i + 1 - j), multiplied by i (possible a[i] choices).

Sum up all dp[1][*] to get the total number of ways, mod m.

Code:

vvi dp(n+2,vi(n+2,0));
dp[n+1][0]=1;

for(int i=n;i>=1;i--){
    for(int j=0;j<=n;j++){
        dp[i][j]= (dp[i][j]+dp[i+1][j])%m;

        if(j==n){
            continue;
        }

        int temp = n-i+1-j;

        if(temp>0){
            int val= (dp[i+1][j]* temp) % m;
            val = (val*i)%m;

            dp[i][j+1]= (dp[i][j+1]+val)%m;
        }

    }
}

// sum of all the element in dp[1] is the answer;

int res = accumulate(all(dp[1]),(int)0) % m;
cout<< res<<endl;

//the code can be improved by using a 1d dp instead of 2d

Closing Notes

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