Table of Contents
Bike Racers – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Bike Racers HackerRank Solution
#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;
}
Java Bike Racers HackerRank Solution
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;
}
}
}
Python 3 Bike Racers HackerRank Solution
# 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()
Python 2 Bike Racers HackerRank Solution
import math
import numpy
from bisect import bisect_left
#checks if we can get matching of bikes to bikers in time less than k
def isThereAmatching(dist, m, n, k, time):
graphDict = {}
#we start by converting our dist array into a dict
for i in xrange(n):
graphDict[str(i)]=[]
for i in xrange(n):
for j in xrange(m):
if(dist[i][j]<=time):
graphDict[str(i)].append(str(j))
newDict = bipartiteMatch(graphDict)
return len(newDict[0])>=k
########################## Bipartite matching alg ##############################
#source http://code.activestate.com/recipes/123641-hopcroft-karp-bipartite-matching/
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)
################################################################################
class MyPoint(object):
def __init__(self, xyArray):
self.x=int(xyArray[0])
self.y=int(xyArray[1])
def pdist(self, otherPoint):
return (self.x-otherPoint.x)**2 + (self.y-otherPoint.y)**2
def __str__(self):
return "{0}, {1}".format(self.x, self.y)
nmk = raw_input().strip().split(' ')
n = int(nmk[0])
m = int(nmk[1])
k = int(nmk[2])
nArray = []
for i in xrange(n):
nArray.append(MyPoint(raw_input().strip().split(' ')))
mArray = []
for i in xrange(m):
mArray.append(MyPoint(raw_input().strip().split(' ')))
dist = numpy.zeros((n,m))
for i in xrange(n):
for j in xrange(m):
dist[i][j] = nArray[i].pdist(mArray[j])
#print dist
#put dist into one array
oneArray = []
for i in xrange(n):
oneArray.extend(dist[i].tolist())
oneArray = list(set(oneArray))
oneArray.sort()
#print oneArray
#from http://code.activestate.com/recipes/81188-binary-search/
minV = 0; maxV = len(oneArray) - 1
if(isThereAmatching(dist, m, n, k, oneArray[minV])):
print oneArray[0]
elif(not isThereAmatching(dist, m, n, k, oneArray[maxV])):
print "something's wrong something's wrong something's very wrong"
#right now we know that 0 is too short a time and maxV definitely works
else:
while 1:
if maxV < minV:
print "something's wrong something's wrong something's super wrong"
break
if minV == maxV-1:
print int(oneArray[maxV])
break
z = (minV + maxV) / 2
#print 'minV: {0}, maxV: {1}, m: {2}'.format(minV, maxV, z)
zresult = isThereAmatching(dist, m, n, k, oneArray[z])
if zresult:
maxV = z
else:
minV = z
C Bike Racers HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
int f(long long x);
void trace(int*edge_left,int*edge_right,int*match,int*list_left,int*list_right,int*right_edge_left,int*right_edge_right,int edge_size,int flag,int index,int*break_flag,int*path,int path_idx,int*index_list,int*track,int N);
void sort_a(int*a,int*b,int*c,int size);
void merge(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size, int right_size);
int *edge_left,*edge_right,*match,*list_left,*list_right,*path,*right_edge_left,*right_edge_right,*index_list,*track,N,M,K;
long long **d;
int main(){
int i,j;
long long *rl,*rr,*bl,*br,high=0,low=0;
scanf("%d%d%d",&N,&M,&K);
rl=(long long*)malloc(N*sizeof(long long));
rr=(long long*)malloc(N*sizeof(long long));
bl=(long long*)malloc(M*sizeof(long long));
br=(long long*)malloc(M*sizeof(long long));
d=(long long**)malloc(N*sizeof(long long*));
edge_left=(int*)malloc(N*M*sizeof(int));
edge_right=(int*)malloc(N*M*sizeof(int));
right_edge_left=(int*)malloc(N*M*sizeof(int));
right_edge_right=(int*)malloc(N*M*sizeof(int));
match=(int*)malloc(N*M*sizeof(int));
list_left=(int*)malloc(N*sizeof(int));
list_right=(int*)malloc(M*sizeof(int));
path=(int*)malloc((N+M)*sizeof(int));
track=(int*)malloc((N+M)*sizeof(int));
index_list=(int*)malloc(N*M*sizeof(int));
for(i=0;i<N;i++)
d[i]=(long long*)malloc(M*sizeof(long long));
for(i=0;i<N;i++)
scanf("%lld%lld",rl+i,rr+i);
for(i=0;i<M;i++)
scanf("%lld%lld",bl+i,br+i);
for(i=0;i<N;i++)
for(j=0;j<M;j++){
d[i][j]=(rl[i]-bl[j])*(rl[i]-bl[j])+(rr[i]-br[j])*(rr[i]-br[j]);
if(d[i][j]>high)
high=d[i][j];
}
while(high-low>1)
if(f((high+low)/2))
high=(high+low)/2;
else
low=(high+low)/2;
printf("%lld",high);
return 0;
}
int f(long long x){
int i,j,edge_size=0,flag=0,break_flag;
for(i=0;i<N;i++,flag=0)
for(j=0;j<M;j++)
if(d[i][j]<=x){
edge_left[edge_size]=right_edge_left[edge_size]=i;
edge_right[edge_size]=right_edge_right[edge_size]=j;
match[edge_size]=0;
if(flag==0)
list_left[i]=edge_size;
flag=1;
index_list[edge_size]=edge_size;
edge_size++;
}
sort_a(right_edge_right,right_edge_left,index_list,edge_size);
for(i=0;i<edge_size;i++)
if(i==0||right_edge_right[i]!=right_edge_right[i-1])
list_right[right_edge_right[i]]=i;
for(i=0;i<N;i++){
break_flag=0;
for(j=0;j<N+M;j++)
track[j]=0;
trace(edge_left,edge_right,match,list_left,list_right,right_edge_left,right_edge_right,edge_size,0,i,&break_flag,path,0,index_list,track,N);
}
for(i=0,j=0;i<edge_size;i++)
if(match[i])
j++;
if(j>=K)
return 1;
else
return 0;
}
void trace(int*edge_left,int*edge_right,int*match,int*list_left,int*list_right,int*right_edge_left,int*right_edge_right,int edge_size,int flag,int index,int*break_flag,int*path,int path_idx,int*index_list,int*track,int N){
int i,j,k;
if(flag==0){
if(track[index])
return;
track[index]=1;
j=0;
for(i=list_left[index];i>=0&&i<edge_size&&edge_left[i]==index&&(*break_flag)==0;i++)
if(match[i]==0){
j=1;
path[path_idx]=index;
trace(edge_left,edge_right,match,list_left,list_right,right_edge_left,right_edge_right,edge_size,1,edge_right[i],break_flag,path,path_idx+1,index_list,track,N);
}
if(j==0)
return;
}
else{
if(track[index+N])
return;
track[index+N]=1;
j=0;
for(i=list_right[index];i>=0&&i<edge_size&&right_edge_right[i]==index&&(*break_flag)==0;i++)
if(match[index_list[i]]==1){
j=1;
path[path_idx]=index;
trace(edge_left,edge_right,match,list_left,list_right,right_edge_left,right_edge_right,edge_size,0,right_edge_left[i],break_flag,path,path_idx+1,index_list,track,N);
}
if(j==0){
path[path_idx]=index;
for(i=0;i<path_idx;i++)
if(i%2==0){
for(k=list_left[path[i]];k>=0&&k<edge_size&&edge_left[k]==path[i];k++)
if(match[k]==0&&edge_right[k]==path[i+1])
match[k]=1;
}
else{
for(k=list_right[path[i]];k>=0&&k<edge_size&&right_edge_right[k]==path[i];k++)
if(match[index_list[k]]==1&&right_edge_left[k]==path[i+1])
match[index_list[k]]=0;
}
(*break_flag)=1;
}
}
return;
}
void sort_a(int*a,int*b,int*c,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int*left_a,*left_b,*left_c,*right_a,*right_b,*right_c;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
left_c=(int*)malloc(m*sizeof(int));
right_c=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
left_c[i]=c[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
right_c[i]=c[i+m];
}
sort_a(left_a,left_b,left_c,m);
sort_a(right_a,right_b,right_c,size-m);
merge(a,left_a,right_a,b,left_b,right_b,c,left_c,right_c,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
free(left_c);
free(right_c);
return;
}
void merge(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size, int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else if (left_a[i] <= right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
}
}
return;
}
Leave a comment below
