 # Uber HackTag 6 March second task

There are n drivers and k batteries (k>=n) .They lie on x axis such that no two Drivers and No two batteries lie at same Point. A battery and A Driver may lie at the same point.There is also a Pickup Location “p”.

Each driver needs to take a Battery and go to the pickup location. A battery once taken cannot be used by other Driver.Assume drivers move unit distance per second. If two drivers reach a Battery at the same Time then only one person can Take it.A driver can pass through battery without taking it.

You need to Determine the minimum time needed for all n drivers to go to the pickup location after taking the battery.
Input:
n,k ,p,array a[i] containing n locations of driver and array b[i] containing k locations of battery
n<=1000
n<=k<=2000
1<=a[i],b[i],p<=1e9
Note: no two drivers or battery is at same point but a driver and a battery can be at the same point.

Can somebody help with this task? ,if anything is unclear feel free to ask in comments

Seems to be the same question : Problem - 830A - Codeforces
Here’s my solution for reference : Submission #109214474 - Codeforces

1 Like

Thanks a lot!

1 Like

How did you search it bro?

It was one of the questions in galen_colin’s Dynamic Programming Mashup Contest. Galen_Colin orz.

2 Likes

can you please help me that why

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

const int maxm = 2 * 1e3 + 5;
int a[maxm], b[maxm];
int n, k, p;
int dp[maxm][maxm];

int checker(int pos, int key)
{
if (pos >= n) return 0;
if (key >= k) return 1e9;
if (dp[pos][key] != -1) return dp[pos][key];
int ans = INT_MAX;

for (int i = key; i < k; i++) {
int temp = abs(a[pos] - b[i]) + abs(b[i] - p);
int temp2 = checker(pos + 1, i + 1);
int temp3 = max(temp, temp2);
ans = min(ans, temp3);
}
return dp[pos][key] = ans;
}

void solve()
{

cin >> n >> k >> p;
memset(dp, -1, sizeof dp);
for (int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n);
for (int i = 0; i < k; i++) cin >> b[i];
sort(b, b + k);
cout << checker(0, 0) << endl;
}

int32_t main()
{

ios_base:: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

solve();
return 0;
}
``````

this is showing me tle

Has anyone received any mail after that test on the 6th March?