Ninja Headquarters

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
4 upvotes
Asked in company
Adobe

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
4
1
0 1 2
1 0 5
0 0 7
1 1 3
5
3
1 2 1
2 3 9
1 4 5
4 0 3
5 3 5

Sample Output 1 :

0 0
2 3

Explanation Of Sample Input 1 :

Test Case 1 :  
There are four ninja offices. The location of each office in the X-Y plane is,

1

Locations of ninja offices are marked in red color, and the location of ninja headquarters is marked in black color.
The sum of the number of services offered by each office is maximum at point (0, 0), and it is lexicographically the lowest coordinate.

Test Case 2 : 
There are five ninja offices. The location of each office in the X-Y plane is,

1

Locations of ninja offices are marked in red color, and the location of ninja headquarters is marked in black color.
The sum of the number of services offered by each office is maximum at point (2, 3), and it is lexicographically the lowest coordinate.

Sample Input 2 :

1
5
2
2 2 4
2 2 1
2 2 7
2 2 6
2 2 3

Sample Output 2 :

2 2
Explanation of Sample Input 2 :
Test Case 1 :  
There are five ninja offices. The location of each office in the X-Y plane is,

1

Locations of ninja offices are marked in red color, and the location of ninja headquarters is marked in black color.
The sum of the number of services offered by each office is maximum at point (2, 2), and it is lexicographically the lowest coordinate.
Hint

Use the fact that the number of services offered by any office decreases as the distance increases.

Approaches (2)
Brute Force

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’).
  • Return ‘answer’.
Time Complexity

O(X * Y * N), where ‘N’ denotes the number of ninja offices, and ‘X’, ‘Y’ denotes the maximum value of X - coordinate and Y - coordinate among all the coordinates where the ninja office is located.

 

We iterate through all possible coordinates and find their respective sum of the number of services offered by each office. There are X * Y different coordinates, and for each coordinate, it takes O(N) time to compute the sum of the number of services by each office.

Therefore, the total time complexity will be O(X * Y) * O(N), which is O(X * Y * N).

Space Complexity

O(1)

 

We do not take any extra space.

Code Solution
(100% EXP penalty)
Ninja Headquarters
Full screen
Console