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