Travelyoka

general
1

Can anyone share “traveloka” hackereaeth hiring challenge “Top speed” and “divide array” solution.

Need help with code because I was getting TLe

1 Like
2

Devide Array Solution :

Top Speed Solution :

Edit : In top speed problem use binary search to avoid tle

1 Like
3

Can you please explain your Top Speed solution?:sweat_smile:

4

@aman0077
Example : 5 4 3 2 1
right most vehicle always runs at her maximum speed in this case vehicle 1 runs at max
after vehicle 1 any vehicle have lesser speed than vehicle 1 runs at max speed if not than run at max speed of previous vehicle than array looks like this 1 1 1 1 1 then just apply binary search for each i th vehicle any previous vehicle runs at her max speed and has greater than or equals speed to i th vehicle than just stop and you got index of that prev vehicle than calculate ans using index.

2 Likes
5

Understood! Thanks for the explanation. :smiley: :smiley:

1 Like
6

Bro please explain Approach the logic for Divide Array

7

@rishabhjha708
Example :
I - 0 0 0 3 3 3
O - 0 1 3 0 0 3
bro just use simple mapping & code according to above example.

8

TOP SPEED

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
lli arr[200009];
lli tree[200009];
lli brr[200009];
lli crr[200009];
unordered_map<lli,lli>mp;
lli maxi=INT_MIN;

void update(lli index,lli val,lli n)
{
while(index<=n)
{
tree[index]=max(tree[index],val);
index+=index&(-index);
}
}

lli query(lli index)
{
maxi=INT_MIN;

while(index>0)
{
    maxi=max(maxi,tree[index]);
    index-=index&(-index);
}

return maxi;

}

int main()
{
lli i,j,k,n,m,t,ans;

cin>>t;

while(t--)
{
    cin>>n;
    
    mp.clear();
    
    for(i=1;i<=n;i++)
    {
        cin>>arr[i];
        crr[i]=arr[i];
    }
    
    sort(crr+1,crr+n+1);
    
    for(i=1;i<=n;i++)
    {
        if(mp[crr[i]]==0)
        {
            mp[crr[i]]=i;
        }
    }
  
    for(i=1;i<=n;i++)
    tree[i]=INT_MIN;
    
    for(i=n;i>=1;i--)
    {
        ans=query(mp[arr[i]]-1);
        
         if(ans==INT_MIN)
          brr[i]=0;
         else
          brr[i]=ans-i;
          
        update(mp[arr[i]],i,n);
    }
    
    for(i=1;i<=n;i++)
    {
         cout<<brr[i]<<" ";
    }
    
    cout<<"\n";
}

}