# 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++){
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 q[MAX_NODES+2];
void enqueue(int x){q[tail] = x; tail++; color[x] = GRAY;}
int bfs (int start, int target) {
int u,v;
for (u=0; u<n; u++) { color[u] = WHITE; }
enqueue(start);
pred[start] = -1;
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.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;

public class Solution {
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[] 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();
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();
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;
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 int visitedNum;
private boolean isTerminus;

public Node()
{
visitedNum = -999;
isTerminus = false;
}

public Node(boolean terminus)
{
visitedNum = -999;
isTerminus = terminus;
}

public int getVisited()
{
return visitedNum;
}

{
}

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))
{
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()```
```

## 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

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

## 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

## 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

## 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