Campus Cycles

Easy
0/40
Average time to solve is 15m
profile
Contributed by
4 upvotes
Asked in company
Facebook

Problem statement

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).

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
2 2
0 0
2 1
1 2
3 3
2 2
1 1
2 1 
2 2
2 1
Sample Output 1:
1 0
0 1
Explanation 1:
For the first test case, 
Distance of Student 0 from Cycle 0  = |1-0| + |2-0| = 3
Distance of Student 0 from Cycle 1  = |3-0| + |3-0| = 6
Distance of Student 1 from Cycle 0  = |1-2| + |2-1| = 2
Distance of Student 0 from Cycle 0  = |1-0| + |2-0| = 3
Student 1 grabs Cycle 0 as it is closest (without ties), and Student 0 is assigned Cycle 1. So the output is [1, 0].

For the second test case, 
Distance of Student 0 from Cycle 0  = |2-1| + |2-1| = 2
Distance of Student 0 from Cycle 1  = |2-1| + |1-1| = 1
Distance of Student 1 from Cycle 0  = |2-2| + |2-1| = 1
Distance of Student 1 from Cycle 1  = |2-1| + |2-1| = 0
Student 1 grabs Cycle 1 as it is closest and Student 0 is assigned Cycle 0. So the output is [1, 0]
Sample Input 2:
2
3 3
0 0
1 1
2 0
1 0
2 2
2 1
2 3
0 1
2 0 
0 0
1 1
2 2
Sample Output 2:
 0 2 1
 0 1
Hint

Can you solve this problem by simply sorting according to the conditions?

Approaches (2)
Brute Force Approach

 

  • 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.
Time Complexity

O(N*M*Log(N*M)), where ‘N’ is the total number of Students and ‘M’ is the total number of Cycles.


 

Since for every student in the student’s array, we are calculating manhattan distance for every cycle location in the cycle’s array which will take O(N*M) time and storing them in the array. Since there are a total of N*M pairs of (student, cycle) in the array Distance which when sorted takes O(N*M*Log(N*M)) time. So overall time complexity will be O(N*M*Log(N*M)). 

Space Complexity

O(N*M), where ‘N’ is the total number of Students and ‘M’ is the total number of Cycles.

 

Since there are a total of N*M pair of (student, worker) and each pair will be stored in the Distance array. So overall time complexity will be O(N*M).

Code Solution
(100% EXP penalty)
Campus Cycles
Full screen
Console