Last Updated: 10 Apr, 2021
Campus Cycles
Easy
Asked in company
A school campus is represented as a 2D grid. The campus has N students and M cycles, and the number of students are less than or equal to the number of cycles. Each student and cycle is represented as a 2D coordinate (X, Y) on this grid.
Our goal is to assign exactly one cycle to each student. Among the available cycles and students, we choose the (student, cycle) pair with the shortest Manhattan distance between each other, and assign the cycle to that student. If there are multiple (student, cycle) pairs with the same shortest Manhattan distance, we choose the pair with the smallest student index; if there are multiple ways to do that, we choose the pair with the smallest cycle index. We repeat this process until a cycle is assigned to each student.
Given the description of the school campus, your task is to find the index (0-based) of the cycle that is assigned to each student.
The Manhattan distance between two points P1 and P2 is defined as D = |P1.X - P2.X| + |P1.Y - P2.Y| where X, Y represents the location of a point in both horizontal as well as vertical direction respectively from the origin(0,0).
Input format:
The first line of input contains an integer ‘T’, denoting the number of test cases.
The first line of each test case contains two space-separated integers ‘N’ and ‘M’, where ‘N’ represents the number of students and ‘M’ represents the number of cycles.
Then the next ‘N’ lines of each test case contains two space-separated integers denoting the ‘X’ and ‘Y’ coordinates of students one in each line.
Then the next ‘M’ lines of each test case contains two space-separated integers denoting the ‘X’ and ‘Y’ coordinates of cycles one in each line.
Output format:
For each test case, print N space-separated integers denoting the index of the cycle that each student on the campus is assigned to.
Output for each test case is printed on a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N , M <= 1000
0 <= Student[i][j] , Cycle[i][j] <= 10^4
All student and bike locations are distinct.
Where ‘T’ represents the number of test cases, ‘N’ represents the number of students, ‘M’ represents the number of cycles, ‘Student[i][j]’ represents the location of each student on the campus, and ‘Cycle[i][j]’ represents the location of each cycle in the campus.
Time Limit: 1 sec
Approaches
- This is a brute force approach where we will first store the manhattan distance along with the indices of each student and cycle in an array and then sort it according to the following conditions:
- First, sort the array according to the smallest manhattan distance.
- If their manhattan distances are equal then sort the array according to the smallest index in the student array.
- If the pairs that have the same manhattan distances also have the same index in the student’s array then sort it according to the smallest index in the cycle’s array.
Algorithm:
- Create an array Distances in which each index will store three things - Manhattan distance, index from the student’s array and corresponding index from the cycle’s array.
- For every ‘Student’ in the Students array, we will traverse over all the locations of the ‘Cycles’ in the Cycles array and calculate the manhattan distance given by:
- Distance = |Student.X - Cycle.X| + |Student.Y = Cycle.Y|.
- Now we will insert a tuple of {Distance, Student’s index, Cycle’s index} in the Distances array.
- Now sort the Distances array.
- Create a boolean array isCycleGiven to mark cycles that are already allotted of size equal to Cycles array and intialised with false.
- Also, create an array Ans of size equal to the size of the Students array to store the index of the cycle allotted to each student’s index. Ans array is initialized with -1 in order to check which student has been encountered and which is not.
- Now we will traverse over the Distances array and for every tuple of (distance, student, cycle) at that index, we will check two conditions:
- If the cycle is already not allotted.
- Or if the value at the index in the array Ans is not equal to -1.
- If the above two conditions are false then we will insert the index of the cycle at the index of the student in the Ans array.
- Also, we will make the index of the cycle in the isCycleGiven as True.
- Finally, we will return the Ans array.
- Since the maximum manhattan distance will be 20000. So we will make an array of size 20001 and store a pair of indexes of Student and Cycle at that index in the array which is equal to their manhattan distance.
- We will also make a boolean array to keep a check that which cycle has been allocated to a student already.
- We will traverse over the array from the beginning and for every student which is not allocated a cycle, we will allocate a cycle to that student and add the index of the cycle allotted in our result array.
Algorithm:
- Create an array Distances of size 20001 which will store the indices of the student and cycle as a pair at the index equal to their manhattan distance.
- For every student in the Students array, we will traverse over all the locations of the Cycles and calculate the manhattan distance given by:
- Distance = |Student.X - Cycle.X| + |Student.Y = Cycle.Y|.
- Now we will insert the pair of {Student’s index, Cycle’s index} at the index equal to the Distance calculated above in the Distances array.
- Now create a boolean array isCycleGiven of size equal to the Cycles array to keep the track of cycles that are already allotted. The array isCycleGiven is initialized with false.
- Also, create an array Ans of size equal to the Students array to store the index of the cycle allotted to each student’s index. Ans array is initialized with -1 in order to check which student has been encountered and which is not.
- Create an integer variable countCycles initialized to 0 to count the number of cycles allotted.
- Now we will traverse over all the distances from 0 to 20000 and for every pair of (student, cycle) at that index we will check two conditions:
- If the cycle is already allotted or not.
- And if the value at the index in the array Ans is equal to -1 or not.
- If the above two conditions are false then we will insert the index of the cycle at the index of the student in the Ans array.
- Also, we will make the index of the cycle in the isCycleGiven as True.
- Increment countCycles by one.
- Also, check that if countCycles become equal to the number of students then simply break the loop as we don’t have to further traverse the Distances array unnecessary because all the students have been allotted one cycle each.
- Finally, we will return the Ans array.