Hello Everyone,

After successful completion NITS Hacks 5.0, we would like to make the problems of NITS Hacks 5.0 Finals public through a mirror contest. Anyone can participate in it individually or in a team of 3 members.

Number of Problems: 9 (not sorted by difficulty)

Contest Duration: 3.5 hours

Contest Time: 27th October, 6 pm to 9:30 pm IST

Contest Link: https://codeforces.com/contestInvitation/94509f62591f76afe546707ad1c471829412c9f5

Two problems remained unsolved during the contest.
I would like to see someone solving them during the mirror contest.

Finally, I'd like to thank my friends Jo3kerR, jac_nikola, Noobabhi, and agarwala2512 for coming up with such interesting problem ideas, and my seniors amit_dwivedi, invictus_123, and harshit15 for testing the problems.

I hope you all would love the problems.

See you on the leaderboard.

Editorial: https://docs.google.com/document/d/15MPZUwlar8QDPSHr5I3lOUdX7e7G10LjPm53baH9L9Q/edit?usp=sharing

UPD1: Link to the Onsite Final Contest — https://codeforces.com/contestInvitation/f55fc20a56189ec881f16145a27550de7ee207d7

UPD2: Editorials will be out soon.

UPD3: Editorial is out.

Link for the contest

A. Points and Square

As the sides of the square must be parallel to $$$X$$$-axis and $$$Y$$$-axis, the side parallel to $$$X$$$-axis must be at least as long as the difference between highest and lowest $$$X$$$ coordinates and the side parallel to $$$Y$$$-axis must be at least as long as the difference between highest and lowest $$$Y$$$ coordinates. Whichever of these two is bigger will be the side of our square.

So the length of the smallest square that contains all the given points is MAX( Highest X coord — Lowest X coord, Highest Y coord — Lowest Y coord).

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

int main()
{
	ll n;
	cin>>n;
	ll x1=100000000, x2=-100000000, y1=100000000, y2=-100000000, x, y;
	while (n--)
	{
		cin>>x>>y;
		x1 = min(x1, x);
		x2 = max(x2, x);
		y1 = min(y1, y);
		y2 = max(y2, y);
	}
	ll L = max(x2-x1, y2-y1);
	cout<<L;
    return 0;
}

B. Single Digit

As $$$N\le10^{21}$$$ it can have at most $$$21$$$ digits, so if we take the sum of all odd place's digits or even place's digits then the sum can be at most $$$99$$$. So when we do the operation first time N will be reduced to a $$$1$$$ or $$$2$$$ digit number and after doing the operation second time it will be reduced to a $$$1$$$ digit number for sure. So there can be at most $$$4$$$ possible digits to which $$$N$$$ can be reduced. We can find these $$$4$$$ possible digits and check if $$$D$$$ is one of them or not.

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
 
int main() 
{
    int tc; cin>>tc;
    while(tc--)
    {
        string s; cin>>s;
        int d; cin>>d;

        ll n1=0,n2=0;
        for(int i=0; i<s.size(); i++)
        {
            if(i%2) n1+=s[i]-'0';
            else n2+=s[i]-'0';
        }

        ll d1=n1%10;
        ll d2=n2%10;
        ll d3=n1/10;
        ll d4=n2/10;

        if(d1==d || d2==d || d3==d || d4==d) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}

C. Greatest Prime Function

The gap between any two consecutive prime number is very small, it is estimated that the largest gap is of the order $$$log(N)^2$$$ only. In fact, for $$$N$$$ up to $$$10^{10}$$$, the largest gap is less than $$$400$$$. So we can just iterate backwards from $$$N$$$ and check if the number is prime or not. If we find a prime number, we break the loop and we would get the nearest prime number smaller than $$$N$$$. To check if a number $$$n$$$ if prime or not, we can iterate from $$$i=2$$$ to $$$i*i \le n$$$ and if any of the $$$i$$$ divides $$$n$$$ then it's not a prime otherwise it's a prime.

Time Complexity: $$$O(√N (log N)^2)$$$

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

bool prime(ll n)
{
    for(ll i=2; i*i<=n; i++)
        if(n%i==0) return false; 
    return true;
}
ll gpf(ll n)
{
    while(1)
    {
        if(prime(n)) return n;
        n--;
    }
    return n;
}
int main() 
{
    ll x,y; cin>>x>>y;
    cout<<gpf(x)-gpf(y)<<endl;
}

D. Secret Floor

We can first teleport to different floors at a large interval, in order to narrow down the floors which can be the secret floor. And when we get attacked by lasers, our shield will protect us but our shield will break so it can't protect us next time. Then we start checking the floors in between the intervals one by one. For example $$$N=100$$$, and our interval is $$$10$$$ then we can start teleporting to floor $$$10, 20, 30,...,100$$$ until we get attacked by lasers. Let's say we get attacked by the laser on floor $$$40$$$, so now we know that the secret floor must be above $$$30$$$ and below $$$40$$$. As the shield can no longer protect us we will have to check floors $$$31,32,33,...39$$$ one by one until we get to the secret floor. Let's say $$$38$$$ is the secret floor, so it will take us $$$12$$$ teleportations in this case. But if we use this strategy, it can take us $$$19$$$ steps in the worst case, i.e. when the secret floor is $$$99$$$.

But can we have a better strategy?

If we don't fix our interval but instead keep decreasing by 1 then we can do better. Let's see how, if $$$N=10$$$ then we can start teleporting to floor $$$4,7,9,10$$$ until we get attacked by the lasers. The intervals here are $$$4,3,2,1$$$. If we get attacked by lasers on floor $$$4$$$ then it would take $$$3$$$ at max more teleportations to find the secret floor by checking floor $$$1,2,3$$$ one by one. If we get attacked by lasers on floor $$$7$$$ then it can take us 2 more teleportations, if we get attacked at floor $$$9$$$ then it can take us 2 more teleportations. So we can be sure that within $$$4$$$ teleportations we can reach the secret floor.

So we need to find minimum $$$K$$$ such that $$$K+(K-1)+(K-2)+...+1 \ge N$$$ or $$$K*(K+1)/2 \ge N$$$ and we can be sure that within K steps we can get to the secret floor. This is the best strategy.

For example if $$$N=100$$$, then $$$K$$$ will be $$$14$$$. So We can have our intervals as $$$14, 13, 12, 11,...$$$ and we can first start by checking floors $$$14, 27, 39, 50,...$$$ until we get hit by the lasers. And using this strategy we can be sure to get to the secret floor in $$$14$$$ teleportations.

We can find the value of K using a loop which would take $$$O(√N)$$$ time complexity or we can solve the quadratic equation $$$K^2 + K - 2N = 0$$$ and take the ceil of the positive root of $$$K$$$ to find the solution in $$$O(1)$$$.

You can watch this youtube video to get better understanding: https://www.youtube.com/watch?v=NGtt7GJ1uiM

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main() 
{
    ll N; cin>>N;
    ll k=1;
    while(k*(k+1)/2 < N) k++;
    cout<<k<<endl;
}

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

#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

#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 upper bound on the vector to find the answer for each test case in log√N time.

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

#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$$$ )

#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;
}