Link for the contest

A. Who is happy?

Run a loop from $$$i=0$$$ to $$$i=N-1$$$ and iterate through the string $$$S$$$, maintain two variables $$$countA$$$ and $$$countB$$$ initialised to $$$0$$$. Keep incrementing $$$countA$$$ whenever you encounter letter $$$A$$$ i.e. $$$S[i]==A$$$. Similarly keep incrementing $$$countB$$$ whenever you encounter letter $$$B$$$ i.e. $$$S[i]==B$$$. In the end just check if $$$countA > countB$$$, $$$countA < countB$$$ or $$$countA == countB$$$, and print $$$Anirban$$$, $$$Biswa$$$ or $$$Samay$$$ respectively.

Time Complexity: O( N ) for each test case

Code

#include<bits/stdc++.h>
using namespace std;
int main() 
{
    int tc; cin>>tc;
    while(tc--)
    {
        int n; cin>>n;
        string s; cin>>s;
        int a=0,b=0;
        for(int i=0; i<n; i++)
        {
            if(s[i]=='A') a++;
            if(s[i]=='B') b++;
        }
        if(a>b) cout<<"Anirban"<<endl;
        else if(b>a) cout<<"Biswa"<<endl;
        else cout<<"Samay"<<endl;
    }
}

B. Remainder

We can use divisibility rules of numbers from 2 to 10 but that will be a lot of work. A simple way to solve this problem is to use modular arithmetic to find N % K.

Let's say we are given a number 4367, then 4367 % K = ( 4000 + 300 + 60 + 7 ) % K = ( ( ( ( ( 4*10 + 3) % K )*10 + 6) % K)*10 + 7) % K

We take the first digit, multiply by 10, add next digit then mod by K. Then again we multiply by 10, add next digit then mod by K. We keep on doing this until we have no more digits. At the end we will be left with N % K.

Time Complexity: O( logN ) for each test case

Code

#include<bits/stdc++.h>
using namespace std;
int main() 
{
    int tc; cin>>tc;
    while(tc--)
    {
        string s; cin>>s;
        int k; cin>>k;
        int r=0;
        for(int i=0; i<s.size(); i++)
        {
            r=r*10+(s[i]-'0');
            r%=k;
        }
        cout<<r<<endl;
    }
}

C. Tri-Prime Numbers

If a number has exactly 1 factor other than 1 and itself then it is square of a prime number. So we just need to find how many squares of prime numbers are less than N or how many prime numbers are less than √N. We can use Sieve of Eratosthenes to find and store all the prime numbers less than $$$10^6$$$ in a vector. Then we can just use lower bound on the vector to find the answer for each test case in log√N time.

Time Complexity: O( ( √N + T )log√N )

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const ll N=1e6;
vector<ll> tp;
int is_prime[N];
void sieve()
{
    for(int i=2; i<N; i++) is_prime[i]=1;
    for(ll i=2; i<N; i++)
    {
        if(is_prime[i])
        {
            tp.push_back(i*i);
            for(ll j=i*i; j<N; j+=i) 
                is_prime[j]=0;
        }
    }
}
int main() 
{
    sieve();
    int tc; cin>>tc; 
    while(tc--)
    {
        ll n; cin>>n;
        ll x = upper_bound(tp.begin(),tp.end(),n) - tp.begin();
        cout<<x<<endl;
    }
}

D. Chess is Hard

A solution of O($$$n^2$$$) will be accepted.

As Bunty cannot lose, the opponents that are valid must have a rating strictly less than Bunty's present rating. To increase his rating in the fastest way possible, we make Bunty play(and win) against the highest rated valid opponent.

The O($$$n^2$$$) approach iterates through all the elements and tries to find the opponent, which Bunty has not played yet, with maximum rating less than Bunty's current rating $$$C$$$. Bunty plays this opponent next and his rating is updated. We take the sum of all the player's ratings, Bunty has played so far, after adding 400 to all these ratings and divide this sum by the number of players Bunty has played so far to get the new rating for Bunty. If Bunty's new rating exceeds the minimum rating to be a grandmaster then we stop and print the number of players Bunty played so far otherwise we continue this process until we run out of valid opponents or Bunty's rating exceeds the Grandmaster's rating.

We can also further optimize this solution by first sorting and using a pointer to mark the element which was the largest element less than B every time we iterate, to help find the next such required element.

Time Complexity: O( $$$n^2$$$ ), optimised version O( $$$nlogn$$$ )

Code

#include<bits/stdc++.h>
using namespace std;

int main() 
{
    int n,g,b; cin>>n>>g>>b;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a.begin(),a.end());
    
    vector<int> vis(n,0);
    double c=b;
    int t=0;
    int k=0;
    while(c<=(double)g)
    {
        int nxt=-1;
        for(int i=0;i<n;i++)
        {
            if(a[i]<c && !vis[i]) nxt=i;
        }
        if(nxt==-1) break;
        else k++;
        c = (double)(t+a[nxt]+400)/k;
        vis[nxt]=1;
        t+=a[nxt]+400;
    }
    if(c>(double)g) cout<<k<<endl;
    else cout<<-1<<endl;
}