Bike Racers

Problem Statement :

There are  bikers present in a city (shaped as a grid) having  bikes. All the bikers want to participate in the HackerRace competition, but unfortunately only  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 the first  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 bikes 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, , , and , separated by a single space.
The following  lines will contain  pairs of integers denoting the co-ordinates of  bikers. Each pair of integers is separated by a single space. The next  lines will similarly denote the co-ordinates of the  bikes.

Output Format

A single line containing the square of required time.

Solution :


                            Solution in C :

In   C  :

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

long long *array;
int cmp(const void *a, const void *b){
    long long ia = *(long long *)a;
    long long ib = *(long long *)b;
    return array[ia] < array[ib] ? -1 : array[ia] > array[ib];
int isValid(int mbikes, int nmen, int k, int z, long long index[]);

int main() {
    //find the k shortes edges "in the bipartite graph" between men & bikes
    //performance metric is the max distance among the k pairs
    //this is a min max problem, minimizing the max distance
    int nmen,mbikes,kspots;
    scanf("%d %d %d",&nmen,&mbikes,&kspots);
    long men[nmen][2], bikes[mbikes][2];
    for(int i=0;i<nmen;i++){scanf("%ld %ld",&men[i][0],&men[i][1]);}
    for(int i=0;i<mbikes;i++){scanf("%ld %ld",&bikes[i][0],&bikes[i][1]);}
    long long d,dists[mbikes*nmen];
    for(int i=0;i<mbikes;i++){
        for(int j=0;j<nmen;j++){
    //sort distances, only really need k smallest from each bike
    //discard those that are larger (but not those that are equal)
    long long index[mbikes*nmen];//use malloc to large size array
    for(long i=0;i<mbikes*nmen;i++){index[i] = i;}
    array = dists;
    qsort(index, mbikes*nmen, sizeof(*index), cmp);
    //for(long i=0;i<mbikes*nmen;i++){printf("%lld ",dists[index[i]]);} printf("\n");
    int last=kspots;   
    //do binary search to find out minimum dist that allows a valid assignment
    int left=0, right=mbikes*nmen, width=mbikes*nmen, mid;
        width/=2; mid=(left+right)/2; 
        //printf("Check %d\n",mid);
        if(!isValid(mbikes,nmen,kspots,mid,index)){ left=mid; }
    for (int j=left;j<right;j++){
        //printf("Check %d\n",j);
        if(isValid(mbikes,nmen,kspots,j,index)) {last=j;break;}
    return 0;

#define WHITE 0
#define GRAY 1
#define BLACK 2
#define MAX_NODES 1000
#define oo 1000000000
int n;  // number of nodes
int e;  // number of edges
int capacity[MAX_NODES][MAX_NODES]; // capacity matrix
int flow[MAX_NODES][MAX_NODES];     // flow matrix
int color[MAX_NODES]; // needed for breadth-first search               
int pred[MAX_NODES];  // array to store augmenting path
int max_flow (int source, int sink);
int isValid(int mbikes, int nmen, int k, int z, long long index[]){
    //check if we can pick k unique row/col pairs among the first z
    //this is a matching of cardinality k in the bipartite ii-jj graph
    if(z<k) return 0;
    //capacity rows 0-249, cols 250-499, source as 500, sink as 501
    for(int i=0;i<500;i++){
        for(int j=0;j<500;j++){capacity[i][j]=0;}
    for(int i=0;i<250;i++){capacity[500][i]=1;}
    for(int i=0;i<250;i++){capacity[250+i][501]=1;}
    for(int i=0;i<z;i++){
        int ii=index[i]/nmen;
        int jj=index[i]%nmen;
    n=502; e=z+2; 
    int maxflow=max_flow(500,501);
    //printf("Max flow for z= %d\n",maxflow);
    if(maxflow>=k) return 1;
    else return 0;
// below follows Ford-Fulkerson algorithm for max matching via max flow

int min (int x, int y) {
    return x<y ? x : y;  // returns minimum of x and y
int head,tail;
int q[MAX_NODES+2];
void enqueue(int x){q[tail] = x; tail++; color[x] = GRAY;}
int dequeue(){int x = q[head]; head++; color[x] = BLACK; return x;}
int bfs (int start, int target) {
    int u,v;
    for (u=0; u<n; u++) { color[u] = WHITE; }   
    head = tail = 0;
    pred[start] = -1;
    while (head!=tail) {
		u = dequeue();
        // Search all adjacent white nodes v. If the capacity
        // from u to v in the residual network is positive, enqueue v.
		for (v=0; v<n; v++) {
			if (color[v]==WHITE && capacity[u][v]-flow[u][v]>0) {
				enqueue(v); pred[v] = u;
    // If the color of the target node is black now, it means that we reached it.
    return color[target]==BLACK;
int max_flow (int source, int sink) {
    int i,j,u;
    // Initialize empty flow.
    int max_flow = 0;
    for (i=0; i<n; i++) {
		for (j=0; j<n; j++) {
			flow[i][j] = 0;
    // While there exists an augmenting path, increment the flow along this path.
    while (bfs(source,sink)) {
        // Determine the amount by which we can increment the flow.
		int increment = oo;
		for (u=n-1; pred[u]>=0; u=pred[u]) {
			increment = min(increment,capacity[pred[u]][u]-flow[pred[u]][u]);
        // Now increment the flow.
		for (u=n-1; pred[u]>=0; u=pred[u]) {
			flow[pred[u]][u] += increment; flow[u][pred[u]] -= increment;
		max_flow += increment;
    // No augmenting path anymore. We are done.
    return max_flow;

                        Solution in C++ :

In  C++  :

using namespace std;
int i,j,n,m,k,x[259],y[259],a[259],b[259],C[259],urm[259],pre[259];
long long p,u,mij,ras,D[259][259];
vector < int > v[259];
int mod(int x)
    if(x<0) return -x;
    return x;
int cup(int nod)
    if(C[nod]==1) return 0;
    vector < int > :: iterator it;
            return 1;
            return 1;
    return 0;
int cuplaj()
    int ok=1;
            if(urm[i]==0) ok+=cup(i);
    return ok;
bool ok(long long dstmx)
    int i;
            if(D[i][j]<=dstmx) v[i].push_back(j);
    return (cuplaj()>=k);
int main()
    else p=mij+1;
return 0;

                        Solution in Java :

In   Java :

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;

public class Solution {
	static BufferedReader in = new BufferedReader(new InputStreamReader(;
	static StringBuilder out = new StringBuilder();

	private static Node source;
	private static Node sink;
	private static Node[] bikers;
	private static Node[] bikes;
	public static void main(String[] args) throws IOException {
		String line = in.readLine();
		String[] data = line.split("\\s+");
		int numBikers = Integer.parseInt(data[0]);
		int numBikes = Integer.parseInt(data[1]);
		int numRequired = Integer.parseInt(data[2]);

		source = new Node();
		sink = new Node(true);
		bikers = new Node[numBikers];
		bikes = new Node[numBikes];
		Coordinate[] bikerPos = new Coordinate[numBikers];
		for(int i = 0; i < numBikers; i ++)
			bikers[i] = new Node();
			line = in.readLine();
			data = line.split("\\s+");
			bikerPos[i] = new Coordinate(Integer.parseInt(data[0]), Integer.parseInt(data[1]));
		ArrayList<BikerBikeDistance> bbd = new ArrayList<>();
		for(int j = 0; j < numBikes; j ++)
			bikes[j] = new Node();
			line = in.readLine();
			data = line.split("\\s+");
			int bx = Integer.parseInt(data[0]);
			int by = Integer.parseInt(data[1]);
			for(int i = 0; i < numBikers; i ++)
				bbd.add(new BikerBikeDistance(i, j, getCost(bx, by, bikerPos[i].x, bikerPos[i].y)));
		int total = 0;
		long dist = 0;
		for(int i = 0; total < numRequired; i ++)
			BikerBikeDistance cbbd = bbd.get(i);
			dist = cbbd.cost;
				total ++;
	private static long getCost(long x1, long y1, long x2, long y2)
		return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
	private static class Coordinate
		final int x;
		final int y;
		public Coordinate(int x, int y)
			this.x = x;
			this.y = y;
	private static class BikerBikeDistance implements Comparable<BikerBikeDistance>
		final int biker;
		final int bike;
		final long cost;
		String name;
		public BikerBikeDistance(int biker, int bike, long cost)
			this.biker = biker; = bike;
			this.cost = cost;

		public int compareTo(BikerBikeDistance o) {
			if(cost < o.cost)
				return -1;
			if(cost > o.cost)
				return 1;
			return 0;
	private static class Node
		private LinkedList<Node> connections;
		private int visitedNum;
		private boolean isTerminus;
		public Node()
			connections = new LinkedList<Node>();
			visitedNum = -999;
			isTerminus = false;
		public Node(boolean terminus)
			connections = new LinkedList<Node>();
			visitedNum = -999;
			isTerminus = terminus;
		public int getVisited()
			return visitedNum;
		public void addConnection(Node n)
		public boolean dfsAndReverse(int v)
				return true;
			visitedNum = v;
			Iterator<Node> i = connections.iterator();
				Node n =;
						return true;
			return false;

                        Solution in Python : 
In   Python3  :

# from sets import Set
def bipartiteMatch(graph):
    '''Find maximum cardinality matching of a bipartite graph (U,V,E).
    The input format is a dictionary mapping members of U to a list
    of their neighbors in V.  The output is a triple (M,A,B) where M is a
    dictionary mapping members of V to their matches in U, A is the part
    of the maximum independent set in U, and B is the part of the MIS in V.
    The same object may occur in both U and V, and is treated as two
    distinct vertices if this happens.'''
    # initialize greedy matching (redundant, but faster than full search)
    matching = {}
    for u in graph:
        for v in graph[u]:
            if v not in matching:
                matching[v] = u
    while 1:
        # structure residual graph into layers
        # pred[u] gives the neighbor in the previous layer for u in U
        # preds[v] gives a list of neighbors in the previous layer for v in V
        # unmatched gives a list of unmatched vertices in final layer of V,
        # and is also used as a flag value for pred[u] when u is in the first layer
        preds = {}
        unmatched = []
        pred = dict([(u,unmatched) for u in graph])
        for v in matching:
            del pred[matching[v]]
        layer = list(pred)
        # repeatedly extend layering structure by another pair of layers
        while layer and not unmatched:
            newLayer = {}
            for u in layer:
                for v in graph[u]:
                    if v not in preds:
            layer = []
            for v in newLayer:
                preds[v] = newLayer[v]
                if v in matching:
                    pred[matching[v]] = v
        # did we finish layering without finding any alternating paths?
        if not unmatched:
            unlayered = {}
            for u in graph:
                for v in graph[u]:
                    if v not in preds:
                        unlayered[v] = None
            return (matching,list(pred),list(unlayered))

        # recursively search backward through layers to find alternating paths
        # recursion returns true if found path, false otherwise
        def recurse(v):
            if v in preds:
                L = preds[v]
                del preds[v]
                for u in L:
                    if u in pred:
                        pu = pred[u]
                        del pred[u]
                        if pu is unmatched or recurse(pu):
                            matching[v] = u
                            return 1
            return 0

        for v in unmatched: recurse(v)

def main():
    N, M, K = map(int, input().split())
    bikers = []
    bikes = []
    for i in range(N):
        a, b = map(int, input().split())
    for i in range(M):
        a, b = map(int, input().split())

    edges = []
    for (a,b) in bikers:
        for (c,d) in bikes:
            dist = (a - c)**2 + (b - d)**2

    edges = sorted(edges, reverse = True)
    removed_bikers = 0
    removed_bikes = 0
    biker_hits = dict([(biker, 0) for biker in bikers])
    bike_hits = dict([(bike, 0) for bike in bikes])
    # biker_critical = False
    # bike_critical = False

    bikers = set(bikers)
    bikes = set(bikes)

    # G = dict([(biker, [bike for bike in bikes]) for biker in bikers])
    # (matching, A, B) = bipartiteMatch(G)
    # matching = Set(matching)
    # print "matching = " + str(matching)
    # print "len(matching) = " + str(len(matching))
    # print edges
    # for i in range(len(edges)):
    neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
    G = dict([(biker, neighbors[biker]) for biker in bikers])
    (matching, A, B) = bipartiteMatch(G)
    matching_pairs = set([(bike, matching[bike]) for bike in matching])
    # print "len(matching) = " + str(len(matching))

    for (dist, biker, bike) in edges:
        # (dist, biker, bike) = edges[i]
        biker_hits[biker] += 1
        bike_hits[bike] += 1

        # if len(matching) >= K:
        if (bike, biker) in matching_pairs:
            G = dict([(biker, neighbors[biker]) for biker in bikers])
            (matching, A, B) = bipartiteMatch(G)
            matching_pairs = set([(bike, matching[bike]) for bike in matching])
            # print "len(matching) = " + str(len(matching))
            if len(matching.keys()) < K:

        if biker_hits[biker] == M:

if __name__ == "__main__":    

View More Similar Problems

Insert a Node at the Tail of a Linked List

You are given the pointer to the head node of a linked list and an integer to add to the list. Create a new node with the given integer. Insert this node at the tail of the linked list and return the head node of the linked list formed after inserting this new node. The given head pointer may be null, meaning that the initial list is empty. Input Format: You have to complete the SinglyLink

View Solution →

Insert a Node at the head of a Linked List

Given a pointer to the head of a linked list, insert a new node before the head. The next value in the new node should point to head and the data value should be replaced with a given value. Return a reference to the new head of the list. The head pointer given may be null meaning that the initial list is empty. Function Description: Complete the function insertNodeAtHead in the editor below

View Solution →

Insert a node at a specific position in a linked list

Given the pointer to the head node of a linked list and an integer to insert at a certain position, create a new node with the given integer as its data attribute, insert this node at the desired position and return the head node. A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is e

View Solution →

Delete a Node

Delete the node at a given position in a linked list and return a reference to the head node. The head is at position 0. The list may be empty after you delete the node. In that case, return a null value. Example: list=0->1->2->3 position=2 After removing the node at position 2, list'= 0->1->-3. Function Description: Complete the deleteNode function in the editor below. deleteNo

View Solution →

Print in Reverse

Given a pointer to the head of a singly-linked list, print each data value from the reversed list. If the given list is empty, do not print anything. Example head* refers to the linked list with data values 1->2->3->Null Print the following: 3 2 1 Function Description: Complete the reversePrint function in the editor below. reversePrint has the following parameters: Sing

View Solution →

Reverse a linked list

Given the pointer to the head node of a linked list, change the next pointers of the nodes so that their order is reversed. The head pointer given may be null meaning that the initial list is empty. Example: head references the list 1->2->3->Null. Manipulate the next pointers of each node in place and return head, now referencing the head of the list 3->2->1->Null. Function Descriptio

View Solution →