HackerEarth The Amazing Race problem solution

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

1. X = number of drivers he can see in front of him + number of drivers he can see behind him
2. 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.

#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("%lld\n",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("%d\n", ans);
    }
    return 0;
}