HackerEarth The Amazing Race problem solution YASH PAL, 31 July 2024 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. #include<iostream>#include<cstdio>#include<vector>#include<cstdlib>#include<algorithm>#include<climits>#include<cstring>#include<set>#include<stack>using namespace std;#define MOD 1000000007int 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 1000000007int 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