In this HackerRank Bike Racers problem solution, 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 the 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 the 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.
Problem solution in Python.
from collections import deque
debug = False
def show(matrix):
if False:
for row in matrix:
print(str(row))
def cost(r,b):
dx = b[0]-r[0]
dy = b[1]-r[1]
return dx*dx+dy*dy
def check(limit): # can we connect k riders to k bicycles with only segments less than limit?
rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
# assign as many as we can, stop if we can get to k of them
assd_r = {}
assd_b = {}
assd = 0
arb = False
assdnow = True
while assdnow:
if debug:
print("Looping through")
assdnow = False
for r in range(n):
if r not in assd_r:
# node isn't assigned yet; try and find an augmenting path (DFS)
# leads from this r to any unassigned b, possibly going through current assignations
paths = deque() # contains candidate augmenting paths
visited_r = set()
visited_r.add(r)
for b in reversed(rtob[r]):
paths.append([(r,b)])
while paths:
path = paths.pop()
rc, b = path[-1] # last tuple, try and expand from here
# candidate: rc -> b
if b not in assd_b:
# b isn't assigned; this is an augmenting path
if debug:
print("assigning", path)
for rc, b in path:
assd_r[rc] = b
assd_b[b] = rc
assd += 1
if assd >= k:
if debug:
print("Success! Assigned %d nodes of %d"%(assd,k))
return True
assdnow = True
break # augmenting path found
else: # b is assigned; follow the assigment back to an r (but not the same one) and try again
if debug:
print("continuing", path)
rc = assd_b[b]
if rc not in visited_r:
visited_r.add(rc)
for bc in reversed(rtob[rc]):
if b != bc:
np = path[:]
np.append((rc,bc))
paths.append(np)
if debug:
print("Failure! Assigned %d nodes of %d"%(assd,k))
return False
n,m,k = map(int,input().split())
rs = [tuple(map(int,input().split())) for _ in range(n)] # riders
bs = [tuple(map(int,input().split())) for _ in range(m)] # bicycles
c = [[cost(r,b) for b in bs] for r in rs] # adjacency graph - dense
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
# binary search using check function
lo = 0
hi = len(segs) - 1
while lo < hi:
# invariant: smallest to succeed is x | lo <= x <= hi
mid = (hi + lo) // 2
if debug:
print("examining (%d,%d,%d) (%d)"%(lo,mid,hi,segs[mid]))
if check(segs[mid]):
# succeeded, make mid highest in range (keep it since it might be target)
hi = mid
else:
# failed, try more edges (mid can't be target)
lo = mid + 1
# lo <- smallest to succeed
print(segs[lo])
Problem solution 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;
}
}
}
Problem solution in C++.
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <string>
#define FOR(a,b,c) for (int a=b,_c=c;a<=_c;a++)
#define FORD(a,b,c) for (int a=b;a>=c;a--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; ++i)
#define REPD(i,a) for(int i=(a)-1; i>=0; --i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(a) int(a.size())
#define reset(a,b) memset(a,b,sizeof(a))
#define oo 1000000007
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn=257;
vector<int> a[maxn];
int mX[maxn],mY[maxn],dis[maxn],myq[maxn];
ll X0[maxn],Y0[maxn],X1[maxn],Y1[maxn];
int n,m,k;
bool findpath(){
int first=1, last=0;
FOR(i,1,n) if(mX[i]==0){
myq[++last]=i;
dis[i]=0;
}else dis[i]=oo;
dis[0]=oo;
int u,v;
while(first<=last){
u=myq[first++];
REP(i,sz(a[u])){
v=a[u][i];
if(dis[mY[v]]!=oo) continue;
dis[mY[v]]=dis[u]+1;
myq[++last]=mY[v];
}
}
return dis[0]!=oo;
}
bool dfs(int u){
if(u==0) return 1;
int v;
REP(i,sz(a[u])){
v=a[u][i];
if(dis[mY[v]]==dis[u]+1 && dfs(mY[v])){
mX[u]=v;
mY[v]=u;
return 1;
}
}
dis[u]=oo;
return 0;
}
bool check(ll v){
FOR(i,1,n){
a[i].clear();
FOR(j,1,m) if((X0[i]-X1[j])*(X0[i]-X1[j])+(Y0[i]-Y1[j])*(Y0[i]-Y1[j]) <= v) a[i].pb(j);
}
reset(mX,0); reset(mY,0);
int res=0;
while(findpath())
FOR(u,1,n) if(mX[u]==0 && dfs(u)){
++res;
if(res>=k) return 1;
}
return 0;
}
//#include <conio.h>
int main(){
//freopen("test.txt","r",stdin);
scanf("%d%d%d",&n,&m,&k);
FOR(i,1,n) scanf("%lld%lld",&X0[i],&Y0[i]);
FOR(i,1,m) scanf("%lld%lld",&X1[i],&Y1[i]);
ll res,left=0,right=100000000,mid;
right=right*right*2;
while(left<=right){
mid=(left+right)/2;
if(check(mid)){
res=mid;
right=mid-1;
}else left=mid+1;
}
printf("%lld\n",res);
//getch();
return 0;
}
Problem solution 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;
}
0 Comments