Codeforces Round 927 (Div. 3) Solution and Explanation

 Codeforces Round 927 Div. 3 Problem Solution

Problem A Solution

Algorithm Explanation:

• Input Reading: The program reads a single integer t from the input representing the number of test cases. For each test case, it reads an integer n followed by a string s of length n.

• Function rifat():

• It initializes four variables n, tcnt, cnt, and dcnt as integers. n represents the length of the string, tcnt counts consecutive occurrences of '*', cnt counts occurrences of '@', and dcnt seems to be unused.
• It reads a string s of length n.
• It iterates through the characters of the string s.
  • If the current character is '*', it increments tcnt.
  • If the current character is '@', it increments cnt and resets tcnt to 0.
  • If the current character is neither '*' nor '@', it resets tcnt to 0.
  • If tcnt becomes greater than or equal to 2, the loop breaks.
• It prints the value of cnt, which represents the count of occurrences of '@'.
• Main Function (main()):

• It sets up input/output optimizations using FR.
• It runs the test cases using the test macro, which calls the rifat() function for each test case.
1. 
   

// solved by Md. Rashedul Islam (Rashedul Islam Rifat)
// Youtube: https://www.youtube.com/@rashedul.ririfat/
// Facebook: https//:facebook.com/rashedul.ririfat
// Instagram: https://www.instagram.com/rashedul.ririfat/
// Website: https://rashedulislamrifat.com
#include <bits/stdc++.h>
using namespace std;
//---------------Basic--------------------
#define FR  ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ll long long
#define dbl double
#define sz size()
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
#define Yes cout<<"Yes\n"
#define No cout<<"No\n"
#define yes cout<<"yes\n"
#define no cout<<"no\n"
#define emt empty()
#define sp " "
#define e '\n'
#define for0(x,y,z) for(x y=0;y<z;y++)
#define for1(x,y,z) for(x y=1;y<=z;y++)
#define mapdec(x,y,mp) map<x,y>mp
#define setdec(x,st) set<x>st
#define vecdec(x,v) vector<x>v
#define arrin(x,i,y,z) for(x i=0;i<y;i++) cin>>z[i];
#define arrout(x,i,y,z) for(x i=0;i<y;i++) cout<<z[i]<<sp;
void rifat();
#define test long long t; cin>>t; while(t--){rifat();}
#define even(x) x%2==0
#define odd(x) x%2!=0
#define pb(x,y) x.push_back(y)

void rifat()
{
    ll n,tcnt=0,cnt=0,dcnt=0; cin>>n;
    string s; cin>>s;
    for(ll i=0;i<n;i++){
        if(s[i]=='*') {
            tcnt++;
        }
        else if(s[i]=='@') {
            cnt++;
            tcnt=0;
        }
        else tcnt=0;
        if(tcnt>=2) break;
    }
    cout<<cnt<<e;
}
int main()
{
    FR;
    test;
    //rifat();
    return 0;
}

Problem B Solution

Algorithm Explanation:

• Input Reading: The program reads a single integer t from the input representing the number of test cases. For each test case, it reads an integer n followed by an array a of n elements.

• Main Function:

• It initializes variables for counting, such as i, j, k, c1, c2, cnt, mx, and mn, as well as variables for storing various calculations like ans, sum, ans1, and ans2.
• It runs a loop for each test case.
  • Inside the loop, it reads the value of n.
  • It initializes an array a of size n and reads its elements.
  • It initializes a variable p with the first element of the array.
  • It then iterates over the array from the second element onward.
    • For each element, it finds the minimum number mn such that multiplying it with the current element is greater than p. This is done using binary search.
    • It updates p with the found minimum.
  • Finally, it prints the value of p.
• Uncommented Sections:

• There are several commented-out sections in the code that provide additional functionality for number theory operations, such as finding the greatest common divisor (GCD), working with linear Diophantine equations, converting between strings and integers, building permutations of strings, and performing operations in a harmonic series. However, these sections are not utilized in the main program.
1. 
   

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define e '\n'
#define pb push_back
#define yes "YES"
#define no "NO"
#define F first
#define S second
//#define srt(a) sort(a,a+n)
//#define srt(v) sort(v.begin(),v.end())
//#define srt(u) sort(u.begin(),u.end())
#define loop  for(i=1;i<=n;i++)
const int mod=1e9+7;
const int MOD=998244353;
const int lx=1e5+25;

int main()
{
//   ios_base::sync_with_stdio(0); cin.tie(0);
   int t;
   cin>>t;
   while(t--){
        ll l,i=0,j=0,k,c1=0,c2=0,cnt=0,mx=0,mn=1e18+7;
        ll n,m,ans=0,sum=0,ans1=0,ans2=0;
        cin>>n;
        ll a[n];
        for(i=0;i<n;i++)
            cin>>a[i];
        ll p=a[0];
        for(i=1;i<n;i++){
            ll l=0,r=1e8,mid;
            mn=1e9;
            while(l<=r){
                mid=(l+r)/2;
                if(mid*a[i]>p){
                    mn=a[i]*mid;
                    r=mid-1;
                }
                else
                    l=mid+1;
            }
            p=mn;
        }
        cout<<p<<e;
    }
    return 0;
}

Problem C Solution

• Algorithm Explanation:
• Input Reading: The program reads a single integer t from the input representing the number of test cases. For each test case, it reads two integers n and m, followed by an array a of length n and a string s of length n.

• Main Function:

• It initializes variables and arrays needed for processing.
• For each test case:
  • It reads the size of the array n, the modulo m, the elements of the array a, and the string s.
  • It initializes two pointers L and R representing the left and right ends of the array.
  • It constructs two vectors v and u.
  • It iterates through the string s and depending on whether the character is 'L' or 'R', it pushes the appropriate end value (either L or R) into vector v.
  • It calculates the value of ans using the elements of vector v and array a modulo m and pushes it into vector u.
  • Finally, it prints the elements of vector u in reverse order followed by a newline.
• Preprocessor Directives:

• The program includes preprocessor directives for commonly used operations such as push_back, YES, NO, sort, etc. These directives are commented out.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define e '\n'
#define pb push_back
#define yes "YES"
#define no "NO"
#define F first
#define S second
//#define srt(a) sort(a,a+n)
//#define srt(v) sort(v.begin(),v.end())
//#define srt(u) sort(u.begin(),u.end())
#define loop  for(i=1;i<=n;i++)
const int mod=1e9+7;
const int MOD=998244353;
const int lx=1e5+25;
//pair<ll,ll>p[222222];
//map<ll,ll>mp;
//typedef pair<int, int> pi;
//sort(p,p+n,greater<pair<ll,ll>>());-sort vector pair decending order
//priority_queue<pi,vector<pi>,greater<pi>>pq;
//priority_queue<int,vector<int>,greater<int>>pq;-minheap
//priority_queue<pair<int,int>>pq;
//s.erase(position,length)
int main()
{
//   ios_base::sync_with_stdio(0); cin.tie(0);
   int t;
   cin>>t;
   while(t--){
        ll l,i=0,j=0,k,c1=0,c2=0,cnt=0,mx=0,mn=1e18+7;
        ll n,m,ans=0,sum=0,ans1=0,ans2=0;
        cin>>n>>m;
        ll a[n+1],L,R;
        for(i=1;i<=n;i++)
            cin>>a[i];
        string s;
        cin>>s;
        L=1,R=n;
        vector<ll>v,u;
        for(i=0;i<n;i++){
            if(s[i]=='L'){
                v.pb(L);
                L++;
            }
            else{
                v.pb(R);
                R--;
            }
        }
        ans=1;
        for(i=n-1;i>=0;i--){
            ans=(ans*a[v[i]])%m;
            u.pb(ans);
        }
        reverse(u.begin(),u.end());
        for(i=0;i<n;i++)
            cout<<u[i]<<" ";
        cout<<e;
    }
    return 0;
}

Problem D  Solution

Algorithm Explanation:

• Input Reading: The program reads a single integer t from the input representing the number of test cases. For each test case, it reads an integer n followed by a character ch, and then reads 2n strings.
• Main Function:
• It initializes variables and vectors needed for processing.
• For each test case:
• It reads the size of the hand n and the character ch.
• It reads 2n strings representing the cards in the hand.
• It categorizes the cards into different vectors based on their suits (C, D, H, S) and whether they have the target suit (ch).
• It sorts the vectors.
• It constructs pairs of cards from the categorized vectors, ensuring that at least one card has the target suit (ch) in each pair.
• It handles edge cases where it might be impossible to construct pairs satisfying the conditions.
• Finally, it prints either "IMPOSSIBLE" if it's impossible to construct pairs, or it prints the constructed pairs.
• Preprocessor Directives:
• The program includes preprocessor directives for commonly used operations such as push_back, YES, NO, sort, etc. These directives are commented out.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define e '\n'
#define pb push_back
#define yes "YES"
#define no "NO"
#define F first
#define S second
//#define srt(a) sort(a,a+n)
//#define srt(v) sort(v.begin(),v.end())
//#define srt(u) sort(u.begin(),u.end())
#define loop  for(i=1;i<=n;i++)
const int mod=1e9+7;
const int MOD=998244353;
const int lx=1e5+25;
//pair<ll,ll>p[222222];
//map<ll,ll>mp;
//typedef pair<int, int> pi;
//sort(p,p+n,greater<pair<ll,ll>>());-sort vector pair decending order
//priority_queue<pi,vector<pi>,greater<pi>>pq;
//priority_queue<int,vector<int>,greater<int>>pq;-minheap
//priority_queue<pair<int,int>>pq;
//s.erase(position,length)
int main()
{
//   ios_base::sync_with_stdio(0); cin.tie(0);
   int t;
   cin>>t;
   while(t--){
        ll l,i=0,j=0,k,c1=0,c2=0,cnt=0,mx=0,mn=1e18+7;
        ll n,m,ans=0,sum=0,ans1=0,ans2=0;
        char ch;
        cin>>n>>ch;
        vector<string>c,d,h,s,tump;
        vector<pair<string,string>>p;
        for(i=0;i<2*n;i++){
            string t;
            cin>>t;
            if(t[1]==ch)
                tump.pb(t);
            if(t[1]=='C')
                c.pb(t);
            if(t[1]=='D')
                d.pb(t);
            if(t[1]=='H')
                h.pb(t);
            if(t[1]=='S')
                s.pb(t);
        }
        sort(tump.begin(),tump.end());
        sort(c.begin(),c.end());
        sort(d.begin(),d.end());
        sort(h.begin(),h.end());
        sort(s.begin(),s.end());

        while(c.size()>0){
            string t=c[0];
            if(t[1]==ch)
                break;
            if(c.size()>1){
                string x,y;
                x=c[0];
                y=c[1];
                p.push_back({x,y});
                c.erase(c.begin());
                c.erase(c.begin());
            }
            else if(c.size()==1 && tump.size()>0){
                string x,y;
                x=c[0];
                y=tump[0];
                p.push_back({x,y});
                c.erase(c.begin());
                tump.erase(tump.begin());
            }
            else{
                cnt++;
                break;
            }
        }

        while(d.size()>0){
            string t=d[0];
            if(t[1]==ch)
                break;
            if(d.size()>1){
                string x,y;
                x=d[0];
                y=d[1];
                p.push_back({x,y});
                d.erase(d.begin());
                d.erase(d.begin());
            }
            else if(d.size()==1 && tump.size()>0){
                string x,y;
                x=d[0];
                y=tump[0];
                p.push_back({x,y});
                d.erase(d.begin());
                tump.erase(tump.begin());
            }
            else{
                cnt++;
                break;
            }
        }

        while(h.size()>0){
            string t=h[0];
            if(t[1]==ch)
                break;
            if(h.size()>1){
                string x,y;
                x=h[0];
                y=h[1];
                p.push_back({x,y});
                h.erase(h.begin());
                h.erase(h.begin());
            }
            else if(h.size()==1 && tump.size()>0){
                string x,y;
                x=h[0];
                y=tump[0];
                p.push_back({x,y});
                h.erase(h.begin());
                tump.erase(tump.begin());
            }
            else{
                cnt++;
                break;
            }
        }

        while(s.size()>0){
            string t=s[0];
            if(t[1]==ch)
                break;
            if(s.size()>1){
                string x,y;
                x=s[0];
                y=s[1];
                p.push_back({x,y});
                s.erase(s.begin());
                s.erase(s.begin());
            }
            else if(s.size()==1 && tump.size()>0){
                string x,y;
                x=s[0];
                y=tump[0];
                p.push_back({x,y});
                s.erase(s.begin());
                tump.erase(tump.begin());
            }
            else{
                cnt++;
                break;
            }
        }

        while(tump.size()>0){
            if(tump.size()>1){
                string x,y;
                x=tump[0];
                y=tump[1];
                p.push_back({x,y});
                tump.erase(tump.begin());
                tump.erase(tump.begin());
            }
            else{
                cnt++;
                break;
            }
        }

        if(cnt>0)
            cout<<"IMPOSSIBLE"<<e;
        else{
            for(i=0;i<p.size();i++){
                string x,y;
                x=p[i].F;
                y=p[i].S;
                cout<<x<<" "<<y<<e;
            }
        }

    }
    return 0;
}

Problem E  Solution