Week 9 - Assignment 1 - CS103 - Swayam

Week 9 - Assignment 1

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:

Constraints

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