Last Updated: 9 Apr, 2021
Ninja Headquarters
Moderate
Asked in company
Coding ninjas are planning to build their very first ninja headquarters. There are a total of ‘N’ different ninja offices, where the i-th office is located at the (‘X[i]’, ‘Y[i]’) coordinate in the X-Y plane and has ‘val[i]’ value associated with it. Let an integer ‘range’ denotes the maximum distance in which each office can provide its services.
The number of services offered by each office decreases as the distance increases. For any coordinate (X, Y) in the X-Y plane, suppose the distance of this coordinate from the i-th office is ‘dist’, then the number of services offered by the i-th office at (X, Y) is the floor of ‘val[i] / (1 + dist)’ if ‘dist’ is less than or equal to ‘range’, and 0 services otherwise.
Coding ninjas want to build their ninja headquarters on a coordinate where the sum of the number of services offered by each office is the maximum. As a member of the technical staff, your task is to find the required coordinate on the X-Y plane.
Note :
1) All the coordinates are integral coordinates on the X-Y plane.
2) The distance between any two coordinates is the euclidean distance.
3) There can be multiple offices located on the same coordinate.
4) You are allowed to build the ninja headquarters on the coordinate having ninja offices.
Input Format :
The first line of input contains an integer 'T' representing the number of test cases.
The first line of each test case contains a single integer, ‘N’, where ‘N’ denotes the number of ninja offices.
The second line of each test case contains a single integer, ‘range’, where ‘range’ denotes the maximum distance in which each office can provide its services.
The next ‘N’ lines of each test case contain three space-separated integers, ‘X’, ‘Y’, and ‘val’, where (‘X’, ‘Y’) denotes the coordinate where the ninja office is located, and ‘val’ denotes the value associated with that office.
Output Format :
For each test case, print the integral coordinate where the sum of the number of services offered by each office is the maximum.
If there are multiple coordinates with the same number of services, print the lexicographically minimum coordinate.
A coordinate (X1, Y1) is lexicographically smaller than (X2, Y2) if either X1 is less than X2 or X1 is the same as X2 and Y1 is less than Y2.
The output of each test case will be printed in 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 <= 5
1 <= N <= 25
0 <= X[i], Y[i] <= 25
0 <= val[i] <= 10 ^ 5
1 <= range <= 30
Time Limit: 1Sec
Approaches
The idea here is to use the fact that the number of services offered by any office decreases as the distance from the office increases. Firstly, we will find the maximum value of X - coordinate and Y - coordinate among all the coordinates where the ninja office is located, say ‘maxX’ and ‘maxY’, respectively. Now we will compute the sum of the number of services offered by each office for all the coordinates whose X - coordinate is from 0 to ‘maxX’ inclusive and Y - coordinate is from 0 to ‘maxY’ inclusive. Among all coordinates, we will take the coordinate having the maximum sum of the number of services offered by each company and is lexicographically smallest.
Algorithm:
- Declare an integer, say ‘maxSum’, to store the maximum sum of the number of services offered by each office, and initialize it with -1.
- Declare an array of integers, say ‘answer’ of size two, to store the required coordinate.
- Declare two integers, ‘maxX’ and ‘maxY’, to store the maximum value of X - coordinate and Y - coordinate among all the coordinates where the ninja office is located, and initialize them with 0.
- Run a loop for ‘i’ from 0 to ‘N’ - 1
- Update ‘maxX’ as the maximum of ‘maxX’ and X - coordinate of the i-th office.
- Update ‘maxY’ as the maximum of ‘maxY’ and Y - coordinate of the i-th office.
- Run a loop for ‘allX’ from 0 to ‘maxX.’
- Run a loop for ‘allY’ from 0 to ‘maxY’.
- Declare an integer, say ‘sum’ to store the sum of the number of services offered by each office at (‘allX’, ‘allY’) coordinate.
- Run a loop for ‘i’ from 0 to ‘N’ - 1.
- Declare a variable, say ‘dist’ to store the distance between the i-th office and the (‘allX’, ‘allY’) coordinate.
- Compute the Euclidean distance between i-th office and (‘allX’, ‘allY’) coordinate and store it in ‘dist’.
- If ‘dist’ is less than or equal to ‘range’.
- Add ‘val[i] / (1 + dist)‘ in ‘sum’, as this number of services are offered by the i-th office at a distance ‘dist’.
- If ‘sum’ is greater than ‘maxSum’.
- Update ‘maxSum’ as ‘maxSum’ = sum.
- Store this coordinate into ‘answer,’ i.e., do ‘answer’ = (‘allX’, ‘allY’).
- Run a loop for ‘allY’ from 0 to ‘maxY’.
- Return ‘answer’.
The idea here is to do a Breadth-first search from all the coordinates where ninja offices are located. As the number of services offered by any office decreases as the distance from the office increases, we will start our BFS from all the coordinates of ninja offices. Now, for each coordinate in our BFS, we will compute the sum of the number of services offered by each office at that coordinate. If the computed sum is the maximum sum so far, we will consider that coordinate as our potential answer and do a BFS on its neighbor coordinates.
Algorithm:
- Declare an integer, say ‘maxSum’, to store the maximum sum of the number of services offered by each office, and initialize it with 0.
- Declare an array of integers, say ‘answer’ of size two, to store the required coordinate.
- Declare an empty queue of an array of integers.
- Run a loop for ‘i’ from 0 to ‘N’ - 1
- Insert the coordinates of the i-th office into the queue
- Run a loop until the queue is not empty:
- Store the front of the queue in ‘currCoordinate’ and remove it from the queue.
- Declare two integers, ‘currX’ and ‘currY’ to store the X - coordinate and Y - coordinate of ‘currCoordinate’
- Assign ‘currCoordinate[0]’ to ‘currX’ and ‘currCoordinate[1]’ to ‘currY’
- Declare an integer, say ‘sum’ to store the sum of the number of services offered by each office at (‘currX’, ‘currY’) coordinate.
- Run a loop for ‘i’ from 0 to ‘N’ - 1
- Declare a variable, say ‘dist’ to store the distance between the i-th office and the (‘currX’, ‘currY’) coordinate.
- Compute the Euclidean distance between i-th office and (‘currX’, ‘currY’) coordinate and store it in ‘dist’.
- If ‘dist’ is less than or equal to ‘range’.
- Add ‘val[i] / (1 + dist)‘ in ‘sum’, as this number of services are offered by the i-th office at a distance ‘dist’.
- If ‘sum’ is greater than ‘maxSum’.
- Update ‘maxSum’ as ‘maxSum’ = sum.
- Store this coordinate into ‘answer,’ i.e., do ‘answer’ = (‘currX’, ‘currY’).
- Run a loop for all neighbors of (‘currX’, ‘currY’)
- Insert it into the queue.
- Else if ‘sum’ equals ‘maxSum’.
- Update ‘answer’ as the lexicographically minimum of ‘answer’ and (‘currX’, ‘currY’).
- Return ‘answer’.