Space Exploration Mission
A space exploration mission has been launched by a company called SpaceZ. The spaceships they have are limited in number. They only have N spaceships which have no acceleration, only speed. The universe is huge, and with unlimited number of resources they may explore much of it but since the resources SpaceZ has, is limited, they have set a goal to explore M planets.
Each of the spaceship can reach any of the M planets, but once a spaceship arrives at a particular planet, it is closed off to everyone and cannot be explored by any other spaceship. This has been done so that there is no duplicated effort by their spaceships.
The board of directors have decided that the mission may be deemed successful when K spaceships have completed their exploration.
You have been hired as an analyst who is provided the coordinates of N spaceships in the form (x, y) and M planets in the form (p, q), along with the speed S of each spaceship.
Time for a spaceship to go to a planet, is defined as:
$$t=⌈\frac{(p-x)^2+(q-y)^2}{S^2}⌉$$ in minutes.
You need to find the value of the minimum time needed to complete the space exploration mission, i.e., the minimum time to reach the goal set by the board of directors of SpaceZ if possible.
Input
The first line contains a single integer t, the number of test cases. Description of the test cases is as follows:
- The next line of input contains 3 space-separated integers N, M, and K.
- The next N lines, each have 2-space separated integers x and y.
- The next M lines, each have 2-space separated integers p and q.
- The final line contains N space-separated integers indicating S.
Constraints
- $1 \leq t \leq 10$
- $1 \leq N \leq 200$
- $1 \leq M \leq 200$
- $1 \leq K \leq N$
- $0 \leq x, y, p, q \leq 10^6$
- $1 \leq S \leq 50$
Output
For each test case, get the minimum time needed to complete the space exploration mission, i.e., the minimum time to reach the goal set by the board of directors of SpaceZ in minutes and display it in seconds. If it is not possible to complete the space exploration, print −1.
Example
Input: 1 3 2 1 1 1 2 2 3 3 34 59 14 20 1 2 3 Output: 2760
Explanation
To complete the exploration as decided by the board of directors, 1 spaceship must reach a planet. We see that the spaceship at coordinate (3, 3) gets this goal done in the minimum time of 2760 seconds by reaching the planet at coordinate (14, 20) using the following formula:
$$t=⌈\frac{(3-14)^2+(3-20)^2}{3^2}⌉ \text{min} = 2760\text{s}$$
Solution
import sys # Provides access to system-related parameters and functions, used for faster input
import threading # Used to run the main function on a separate thread to avoid Python's recursion limits
import math # Provides access to mathematical functions like ceiling
from collections import deque # For future use in some graph-related problems, though not used here
def main(): # Main function to handle multiple test cases
t = int(sys.stdin.readline()) # Read the number of test cases
for _ in range(t): # Loop over each test case
# Read input values for the current test case
N, M, K = map(int, sys.stdin.readline().split()) # N: number of spaceships, M: number of planets, K: required matches
spaceship_coords = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)] # Read coordinates of spaceships
planet_coords = [tuple(map(int, sys.stdin.readline().split())) for _ in range(M)] # Read coordinates of planets
speeds = list(map(int, sys.stdin.readline().split())) # Read the speed of each spaceship
times = [] # This list will store the time required for each spaceship to reach each planet
time_map = [] # Matrix to store the time for spaceship i to reach planet j
for i in range(N): # Iterate through each spaceship
x_i, y_i = spaceship_coords[i] # Get the coordinates of spaceship i
S_i = speeds[i] # Get the speed of spaceship i
row_times = [] # Row to store times for spaceship i to each planet
for j in range(M): # Iterate through each planet
p_j, q_j = planet_coords[j] # Get the coordinates of planet j
dist_sq = (p_j - x_i) ** 2 + (q_j - y_i) ** 2 # Calculate the square of the distance between spaceship and planet
t_ij = math.ceil(dist_sq / (S_i ** 2)) # Time required for spaceship i to reach planet j
times.append(t_ij) # Add time to the list of times
row_times.append(t_ij) # Add time to the row
time_map.append(row_times) # Add the row to the time_map matrix
times = sorted(set(times)) # Sort and remove duplicates from the times list
# Binary search over possible times to find the minimum time
left = 0 # Left index for binary search
right = len(times) - 1 # Right index for binary search
result = -1 # Variable to store the final result, initialized to -1 (not found)
while left <= right: # Binary search loop
mid = (left + right) // 2 # Midpoint of current range
T = times[mid] # Set current time to be checked
# Build the graph for this time T
graph = [[] for _ in range(N)] # Create an empty adjacency list for spaceships
for i in range(N): # Iterate through spaceships
for j in range(M): # Iterate through planets
if time_map[i][j] <= T: # If spaceship i can reach planet j within time T
graph[i].append(j) # Add an edge from spaceship i to planet j
# Try to find maximum matching using bipartite matching algorithm
match_to = [-1] * M # Array to keep track of which planet is matched to which spaceship
result_matching = 0 # Counter for the number of successful matches
for u in range(N): # Try to match each spaceship
visited = [False] * M # Keep track of visited planets for each spaceship
if bpm(u, visited, match_to, graph): # If matching is possible for spaceship u
result_matching += 1 # Increase the match count
if result_matching >= K: # If the required number of matches is achieved
result = T # Set the current time T as a valid result
right = mid - 1 # Try to find a smaller time by searching the left half
else:
left = mid + 1 # If not enough matches, search the right half
if result == -1: # If no valid time was found
print(-1) # Output -1
else:
print(result * 60) # Output the result in seconds (since the time is calculated in minutes)
def bpm(u, visited, match_to, graph): # Function to perform bipartite matching (DFS-based)
for v in graph[u]: # Iterate through all planets that spaceship u can reach
if not visited[v]: # If planet v is not visited yet
visited[v] = True # Mark planet v as visited
# If planet v is not matched or if the previous match can be reassigned
if match_to[v] == -1 or bpm(match_to[v], visited, match_to, graph):
match_to[v] = u # Assign spaceship u to planet v
return True # Return true, indicating a successful match
return False # Return false if no match is found
# Run the main function in a separate thread to avoid recursion limits
threading.Thread(target=main).start()
Explanation
The problem can be solved using a binary search over the possible times to find the minimum time needed to complete the space exploration mission. The main idea is to build a graph for each time T and try to find the maximum matching using a bipartite matching algorithm. The binary search is performed over the possible times, and the time is checked by building the graph and finding the maximum matching. If the required number of matches is achieved, the current time is considered as a valid result. The binary search continues until the minimum time is found.
Complexity Analysis
The time complexity of the solution is $O(NM\log(NM))$ where N is the number of spaceships, and M is the number of planets. The solution involves a binary search over the possible times, and for each time, a graph is built and maximum matching is found using a bipartite matching algorithm. The binary search has a time complexity of $O(\log(NM))$, and building the graph and finding the maximum matching has a time complexity of $O(NM)$. Therefore, the overall time complexity is $O(NM\log(NM))$.
Sample Solution Provided by Instructor