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

Need help with code because I was getting TLe

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

Need help with code because I was getting TLe

1 Like

Devide Array Solution :

Top Speed Solution :

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

1 Like

Can you please explain your Top Speed solution?

@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

Understood! Thanks for the explanation.

1 Like

Bro please explain Approach the logic for Divide Array

@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.

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";
}
```

}