HackerEarth The Amazing Race problem solution

YASH PAL, 31 July 202414 February 2026

In this HackerEarth The Amazing Race problem solution As the Formula One Grand Prix was approaching, the officials decided to make the races a little more interesting with a new set of rules. According to the new set of rules, each driver will be given a vehicle with a different height and the driver with maximum SIGHT would win the race.

Now, the SIGHT of a driver is defined by (X * P), where

X = number of drivers he can see in front of him + number of drivers he can see behind him
P = position of the driver in a given scenario ( index of the driver array is 1 – N indexed )

As all the drivers are moving in a straight line, a driver i cannot see beyond another driver j if height of j >= height of driver i.

HackerEarth The Amazing Race problem solution

HackerEarth The Amazing Race problem solution.

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<algorithm>
#include<climits>
#include<cstring>
#include<set>
#include<stack>

using namespace std;

#define MOD 1000000007

int main()
{
    int t, n;

    vector <int> H;

    cin>>t;
    while(t--)
    {
        scanf("%d",&n);
        H.resize(n+1);

        for(int i = 1 ; i <= n ; i++)
        {
            scanf("%d",&H[i]);
        }

        vector <int> rear(n+1);

        stack<int> str;

        str.push(1);

        rear[1] = 0;

        for(int i = 2; i <= n ; i++)
        {
                while( (str.size() > 0) && ( H[ str.top() ] < H[i]) )
                {
                    str.pop();
                }

                if( str.size() > 0 )
                {
                    rear[i] = i - str.top();
                }
                else
                    rear[i] = i - 1;

                str.push(i);
        }

        vector <int> front(n+1);

        stack<int> stf;

        stf.push(n);

        front[n] = 0;

        for(int i = n; i >= 1 ; i--)
        {
                while( (stf.size() > 0) && ( H[ stf.top() ] < H[i] ) )
                {
                    stf.pop();
                }

                if( stf.size() > 0 )
                {
                    front[i] =  stf.top() - i;
                }
                else
                    front[i] = n-i;

                stf.push(i);
        }

        long long x , p, sight = -1,ans ;

        for(int i = 1; i<= n ; i++)
        {
            x = front[i]+rear[i];
            p = i;
            x = (x * p) % MOD;

            if(sight < x)
            {
                sight = x;
                ans = i;
            }

        }

        printf("%lldn",ans);
    }


    return 0;
}

Second solution

#include <cstdio>
#include <cassert>

using namespace std;

#define MAX 100010
#define INF 1000000000
#define MOD 1000000007

int H[MAX], X[MAX], P[MAX], left[MAX], right[MAX];

int main(){
    int T, N, temp;
    scanf("%d", &T);
    assert(T>0 and T<=50);
    while(T--){
        scanf("%d", &N);
        assert(N>0 and N<=100000);
        for(int i=1;i<=N;i++){
            scanf("%d", &H[i]);
            assert(H[i]>=0 and H[i]<=1000000);
        }

        H[0] = INF;
        left[0] = 0;
        left[1] = 0;
        X[1] = 0;
        temp = H[1];
        H[1] = INF;
        for(int i=2;i<=N;i++){
            if(H[i]<=H[i-1]){
                X[i] = 1;
                left[i] = i-1;
            }else{
                int j = i-1;
                while(H[j]<H[i]){
                    j = left[j];
                }
                left[i] = j;
                X[i] = i-j;
            }
        }
        H[1] = temp;
        H[N+1] = INF;
        right[N+1] = N+1;
        right[N] = N+1;
        P[N] = 0;
        H[N] = INF;
        for(int i=N-1;i>0;i--){
            if(H[i]<=H[i+1]){
                P[i] = 1;
                right[i] = i+1;
            }else{
                int j = i+1;
                while(H[j]<H[i]){
                    j = right[j];
                }
                right[i] = j;
                P[i] = j-i;
            }
        }
        int ans, val;
        long long t;
        val = -1;
        for(int i=1;i<=N;i++){
            t = X[i] + P[i];
            t = t*i;
            t = t%MOD;
            if(t>val){
                val = t;
                ans = i;
            }
        }
        printf("%dn", ans);
    }
    return 0;
}

coding problems solutions HackerEarth HackerEarth

Leave a Reply