Uber HackTag 6 March second task

help
1

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

2

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

1 Like
3

Thanks a lot!

1 Like
4

How did you search it bro?

6

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

2 Likes
7

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

8

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