We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
def bikeRacers(bikers, bikes, k):
# Generate all unique squared distances between bikers and bikes
distances = []
for biker in bikers:
for bike in bikes:
dist = squared_distance(biker, bike)
distances.append(dist)
distances = sorted(set(distances)) # Unique sorted distances
# Binary search on the possible distances
left, right = 0, len(distances) - 1
while left < right:
mid = (left + right) // 2
max_dist = distances[mid]
# Check if we can match `k` bikers with `k` bikes within this max_dist
if can_match_with_distance(bikers, bikes, k, max_dist):
right = mid # Try a smaller maximum distance
else:
left = mid + 1 # Try a larger maximum distance
return distances[left]
def can_match_with_distance(bikers, bikes, k, max_dist):
n, m = len(bikers), len(bikes)
graph = [[] for _ in range(n)]
# Create bipartite graph edges within max_dist
for i in range(n):
for j in range(m):
if squared_distance(bikers[i], bikes[j]) <= max_dist:
graph[i].append(j)
# Bipartite matching using DFS
matched_bikes = [-1] * m
def dfs(biker, visited):
for bike in graph[biker]:
if not visited[bike]:
visited[bike] = True
if matched_bikes[bike] == -1 or dfs(matched_bikes[bike], visited):
matched_bikes[bike] = biker
return True
return False
match_count = 0
for biker in range(n):
visited = [False] * m
if dfs(biker, visited):
match_count += 1
if match_count >= k:
return True
return False
Input Handling
if name == 'main':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
first_multiple_input = input().rstrip().split()
n = int(first_multiple_input[0])
m = int(first_multiple_input[1])
k = int(first_multiple_input[2])
bikers = [tuple(map(int, input().rstrip().split())) for _ in range(n)]
bikes = [tuple(map(int, input().rstrip().split())) for _ in range(m)]
result = bikeRacers(bikers, bikes, k)
fptr.write(str(result) + '\n')
fptr.close()
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
An unexpected error occurred. Please try reloading the page. If problem persists, please contact support@hackerrank.com
Bike Racers
You are viewing a single comment's thread. Return to all comments →
import os
def squared_distance(biker, bike): return (biker[0] - bike[0]) ** 2 + (biker[1] - bike[1]) ** 2
def bikeRacers(bikers, bikes, k): # Generate all unique squared distances between bikers and bikes distances = [] for biker in bikers: for bike in bikes: dist = squared_distance(biker, bike) distances.append(dist) distances = sorted(set(distances)) # Unique sorted distances
def can_match_with_distance(bikers, bikes, k, max_dist): n, m = len(bikers), len(bikes) graph = [[] for _ in range(n)]
Input Handling
if name == 'main': fptr = open(os.environ['OUTPUT_PATH'], 'w')