Uber hacktag 6 march

help
1

We want to give incentives to driver. So we need to devise a mechanism to calculate these incentives.

On the end of every trip, an Uber driver gets rating for the ride which is averaged per day. For a given period of days, the value of driver is computed as the sum of the rating of the days in the given period, multiplied by the least rating in that period.

For example
The average ratings for some 4 days are:

2, 1, 3, 4
The the value of driver over these days is (2 + 1 + 3 + 4) * 1 = 10

Let’s create a hypothesis that the incentive calculated is proportional to the greatest value over any contiguous period in drivers days on Uber. Given driver’s average ratings per day, return this greatest value.

Example
Input
Given driver’s ratings over 6 days:

[3, 1, 6, 4, 5, 2]
Output
60
Explanation
Then the period from day 3 to day 5, i.e. 6, 4, 5 has the greatest value, which is (6 + 4 + 5) * 4 = 60

[execution time limit] 1 seconds (cpp)

[input] array.integer ratings

Array of integers. a[i] represents average integer rating on i’th day. Size of array <= 10^5. 0 <= a[i] <= 10^6.

[output] integer64

The greatest value of any contiguous period throughout whole period in given array.

can anyone help me that how to solve this problem
@ssrivastava990 @ssjgz @akshitm16

2 Likes
2

Just calculate the immediate smaller element on left and right for every element (using stacks in O(n)) and then for every element you have kind of a range (left and right extreme).
Now using prefix sums you can calculate the sum of the subarray in which curr elem will be min one.

5 Likes
4

has anybody solved 2 problem of that.if yes can you explain please

5

Here is my simple implementation .
You can reference this for better understanding.

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define endl “\n”
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define sz(x) (int)((x).size())
#define fr first
#define sc second
#define pii pair<int,int>
#define vi vector
#define vpi vector<pair<int,int>>
#define mii map<int,int>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repe(i,a,b) for(int i=a;i<=b;i++)
#define mem1(a) memset(a,-1,sizeof(a))
#define mem0(a) memset(a,0,sizeof(a))
#define ppc __builtin_popcount
#define ppcll __builtin_popcountll
#define INF 100000000000000000
#define mod 1000000007
#define esp 10e-7
const int mx=2e5+7;

signed main()
{
//#ifndef ONLINE_JUDGE
//freopen(“input.txt”, “r”, stdin);
//freopen(“output.txt”, “w”, stdout);
//freopen(“error.txt” , “w” , stderr);
//#endif
IOS
int t=1,n;
// cin>>t;

while(t--)
{
  int arr[]={3, 1, 6, 4, 5, 2};
  int n=sizeof(arr)/sizeof(arr[0]);
  int next_sml[n];// next_sml[i] points to first elememt in the right of arr[i] 
                  // which is smaller than arr[i]; 
  int prev_sml[n];// prev_sml[i] points to first elememt in the left of arr[i] 
                  // which is smaller than arr[i]; 
  memset(next_sml,-1,sizeof(next_sml));// initializing next_sml and prev_sml to -1
  memset(prev_sml,-1,sizeof(prev_sml));
  stack<int>st;
  // calculating next_sml
  for(int i=0;i<n;i++)
  {
    if(st.empty()||arr[st.top()]<=arr[i])
    {
      st.push(i);
      continue;
    }
    while(!st.empty()&&arr[st.top()]>arr[i])
    {
      next_sml[st.top()]=i;
      st.pop();
    }
    st.push(i);
  }
  
  
 
  while(!st.empty())
    st.pop();

  // calculating prev_sml
  for(int i=n-1;i>=0;i--)
  {
    if(st.empty()||arr[i]>=arr[st.top()])
    {
      st.push(i);
      continue;
    }
    while(!st.empty()&&arr[i]<arr[st.top()])
    {
      prev_sml[st.top()]=i;
      st.pop();
    }
    st.push(i);
  }
  
  
  // prefix sum array
  int pf[mx]={0};
  pf[0]=arr[0];
  for(int i=1;i<n;i++)
    pf[i]=pf[i-1]+arr[i];
 
  int ans=0;// storing our final answer

  for(int i=0;i<n;i++)
  {
    int st,en;// st points to first smaller element on the left for arr[i]
    // en points to just one element before the first smaller element on the right for arr[i]
    st=prev_sml[i];

    if(next_sml[i]==-1)
      en=n-1;// if next_sml[i]==-1 which means there is no smaller element less than
             // arr[i] therefore we will initialize with n-1
    else
     en=next_sml[i]-1;// otherwise we will point to one element before the first smaller element on the right

    int tmpans=0;
    if(st==-1)
    {
      // if st ==-1 then our sum will be whole array upto en
     tmpans=arr[i]*(pf[en]);
     
    
    }else
    {
      // otherwise we will subtract pr[en] with pf[st] to get sum for arr[st+1]...arr[en];
      tmpans=arr[i]*(pf[en]-pf[st]);
      
    }
    ans=max(ans,tmpans);
  }
  cout<<ans<<endl;
}

return 0;

}