1
$\begingroup$

This question comes from the HackerRank's "20/20 Hack February" contest which has now ended (problem link).

There are N bikers present in a city (shaped as a grid) having M bikes. All the bikers want to participate in the HackerRace competition, but unfortunately only K bikers can be accommodated in the race. Jack is organizing the HackerRace and wants to start the race as soon as possible. He can instruct any biker to move towards any bike in the city. In order to minimize the time to start the race, Jack instructs the bikers in such a way that first K bikes are acquired in the minimum time.

Every biker moves with a unit speed and one bike can be acquired by only one biker. A biker can proceed in any direction. Consider distance between bike and bikers as euclidean distance.

Jack would like to know the square of required time to start the race as soon as possible.

Input Format The first line contains three integers - N,M,K separated by a single space. Following N lines will contain N pairs of integers denoting the co-ordinates of N bikers. Each pair of integers is separated by a single space. The next M pairs of lines will denote the co-ordinates of M bikes.

Output Format A single line containing the square of required time.

Constraints 1 <= N <= 250 1 <= M <= 250 1 <= K <= min(N,M) 0 <= xi,yi <= 107

Sample Input #00:

    3 3 2
    0 1
    0 2
    0 3
    100 1
    200 2 
    300 3

Sample Output #00:

  40000

Explanation #00: There’s need for two bikers for the race. The first biker (0,1) will be able to reach the first bike (100,1) in 100 time units. The second biker (0,2) will be able to reach the second bike (200,2) in 200 time units. This is the most optimal solution and will take 200 time units. So output will be 2002 = 40000.

$\endgroup$
3
  • $\begingroup$ Hmm... which programming competition does it come from? ;-) $\endgroup$ Feb 17, 2014 at 2:16
  • $\begingroup$ I think I remember seeing this on Hackerrank.com $\endgroup$
    – Nitish
    Feb 17, 2014 at 2:18
  • $\begingroup$ Why ask a programing contests question? The purpose of challenges is to exercise your own brain. $\endgroup$ Feb 17, 2014 at 9:23

1 Answer 1

1
$\begingroup$

First find distance between all possible pairs of bikers and bikes. Now sort this distances.

Now run a loop through all the distances, and create edges only between bikes and bikers whose cost is less than current distance you are considering. Now run Hopcroft-Karp algorithm on that sub graph and compare the max cardinality given by algorithm to K. If they match, then the distance you are considering currently is the required answer.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .