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 :



title-img


                            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++){
            d=(bikes[i][0]-men[j][0]);
            dists[i*nmen+j]=d*d;
            d=(bikes[i][1]-men[j][1]);
            dists[i*nmen+j]+=d*d;          
        }
    }
    //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;
    while(width>4){
        width/=2; mid=(left+right)/2; 
        //printf("Check %d\n",mid);
        if(!isValid(mbikes,nmen,kspots,mid,index)){ left=mid; }
        else{right=mid;}
    }
    last=right;
    for (int j=left;j<right;j++){
        //printf("Check %d\n",j);
        if(isValid(mbikes,nmen,kspots,j,index)) {last=j;break;}
    } 
    printf("%lld",dists[index[last-1]]);
    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;
        capacity[ii][250+jj]=1;
    }
    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;
    enqueue(start);
    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++  :





#include<cstdio>
#include<cstring>
#include<set>
#include<queue>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<cmath>
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;
    C[nod]=1;
    vector < int > :: iterator it;
    for(it=v[nod].begin();it!=v[nod].end();it++)
        if(pre[*it]==0)
        {
            pre[*it]=nod;
            urm[nod]=*it;
            return 1;
        }
    for(it=v[nod].begin();it!=v[nod].end();it++)
        if(cup(pre[*it]))
        {
            pre[*it]=nod;
            urm[nod]=*it;
            return 1;
        }
    return 0;
}
int cuplaj()
{
    int ok=1;
    for(i=1;i<=n;i++)
        C[i]=urm[i]=0;
    for(j=1;j<=m;j++)
        pre[j]=0;
    while(ok)
    {
        ok=0;
        for(i=1;i<=n;i++)
            C[i]=0;
        for(i=1;i<=n;i++)
            if(urm[i]==0) ok+=cup(i);
    }
    ok=0;
    for(i=1;i<=n;i++)
        ok+=(urm[i]>0);
    return ok;
}
bool ok(long long dstmx)
{
    int i;
    for(i=1;i<=n;i++)
        v[i].clear();
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(D[i][j]<=dstmx) v[i].push_back(j);
    return (cuplaj()>=k);
}
int main()
{
//freopen("input","r",stdin);
//freopen("output","w",stdout);
scanf("%d",&n);
scanf("%d",&m);
scanf("%d",&k);
for(i=1;i<=n;i++)
{
    scanf("%d",&x[i]);
    scanf("%d",&y[i]);
}
for(i=1;i<=m;i++)
{
    scanf("%d",&a[i]);
    scanf("%d",&b[i]);
}
for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
        D[i][j]=1LL*(a[j]-x[i])*(a[j]-x[i])+1LL*(b[j]-y[i])*(b[j]-y[i]);
p=0;
u=10000000000000000;
while(p<=u)
{
    mij=(p+u)/2;
    if(ok(mij))
    {
        ras=mij;
        u=mij-1;
    }
    else p=mij+1;
}
printf("%lld\n",ras);
return 0;
}
                    

                        Solution in Java :

In   Java :







import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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(
			System.in));
	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();
			source.addConnection(bikers[i]);
			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();
			bikes[j].addConnection(sink);
			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)));
			}
		}
		
		Collections.sort(bbd);
		
		
		int total = 0;
		long dist = 0;
		for(int i = 0; total < numRequired; i ++)
		{
			BikerBikeDistance cbbd = bbd.get(i);
			dist = cbbd.cost;
			bikers[cbbd.biker].addConnection(bikes[cbbd.bike]);
			if(source.dfsAndReverse(i))
			{
				total ++;
			}
		}
		System.out.println(dist);
	}
	
	
	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;
			this.bike = bike;
			this.cost = cost;
		}

		@Override
		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)
		{
			connections.add(n);
		}
		
		public boolean dfsAndReverse(int v)
		{
			if(isTerminus)
			{
				return true;
			}
			visitedNum = v;
			Iterator<Node> i = connections.iterator();
			while(i.hasNext())
			{
				Node n = i.next();
				if(n.getVisited()!=v)
				{
					if(n.dfsAndReverse(v))
					{
						n.addConnection(this);
						i.remove();
						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
                break
    
    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:
                        newLayer.setdefault(v,[]).append(u)
            layer = []
            for v in newLayer:
                preds[v] = newLayer[v]
                if v in matching:
                    layer.append(matching[v])
                    pred[matching[v]] = v
                else:
                    unmatched.append(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())
        bikers.append((a,b))
    for i in range(M):
        a, b = map(int, input().split())
        bikes.append((a,b))

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

    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
        neighbors[biker].remove(bike)

        # 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:
                print(dist)
                break

        if biker_hits[biker] == M:
            bikers.remove(biker)

if __name__ == "__main__":    
    main()
                    

View More Similar Problems

Delete duplicate-value nodes from a sorted linked list

This challenge is part of a tutorial track by MyCodeSchool You are given the pointer to the head node of a sorted linked list, where the data in the nodes is in ascending order. Delete nodes and return a sorted list with each distinct value in the original list. The given head pointer may be null indicating that the list is empty. Example head refers to the first node in the list 1 -> 2 -

View Solution →

Cycle Detection

A linked list is said to contain a cycle if any node is visited more than once while traversing the list. Given a pointer to the head of a linked list, determine if it contains a cycle. If it does, return 1. Otherwise, return 0. Example head refers 1 -> 2 -> 3 -> NUL The numbers shown are the node numbers, not their data values. There is no cycle in this list so return 0. head refer

View Solution →

Find Merge Point of Two Lists

This challenge is part of a tutorial track by MyCodeSchool Given pointers to the head nodes of 2 linked lists that merge together at some point, find the node where the two lists merge. The merge point is where both lists point to the same node, i.e. they reference the same memory location. It is guaranteed that the two head nodes will be different, and neither will be NULL. If the lists share

View Solution →

Inserting a Node Into a Sorted Doubly Linked List

Given a reference to the head of a doubly-linked list and an integer ,data , create a new DoublyLinkedListNode object having data value data and insert it at the proper location to maintain the sort. Example head refers to the list 1 <-> 2 <-> 4 - > NULL. data = 3 Return a reference to the new list: 1 <-> 2 <-> 4 - > NULL , Function Description Complete the sortedInsert function

View Solution →

Reverse a doubly linked list

This challenge is part of a tutorial track by MyCodeSchool Given the pointer to the head node of a doubly linked list, reverse the order of the nodes in place. That is, change the next and prev pointers of the nodes so that the direction of the list is reversed. Return a reference to the head node of the reversed list. Note: The head node might be NULL to indicate that the list is empty.

View Solution →

Tree: Preorder Traversal

Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's

View Solution →