Chess Tournament

Easy
0/40
Average time to solve is 20m
123 upvotes
Asked in companies
OlaMicrosoftInfo Edge India (Naukri.com)

Problem statement

Chess tournament is going to be organized in Ninjaland. There will be C chess players going to attend the tournament. All the players will be staying in a hotel. The hotel has N free rooms available for the players, where one player will choose one room to live in. The ith room is at position[i] in the hotel. All rooms are in distinct positions.

Focus level of a chess player is defined as the minimum distance between his room and the room of another player. The overall focus of a tournament is defined as the minimum focus level among all players. You as an organizer obviously want the overall focus as high as possible so you assign the rooms to players such that the overall focus is as high as possible.

For example, 
let say we have 3 players and 5 rooms available and the rooms are at positions:  1 2 3 4 6
Here the optimal allocation is in rooms 1 3 6 and the overall focus level is 2.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains a single integer T, representing the number of test cases or queries to be run. 

Then the T test cases follow.

The first line of each test case contains two positive integers N and C, which represent the number of rooms in the hotel and the number of chess players.

The next line contains N space-separated positive integers representing the position of available room in the hotel.
Output Format : 
For each test case, print a single integer, representing the maximum overall focus of the tournament.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraint : 
1 <= T <= 10
2 <= N <= 10 ^ 4
2 <= C <= N
1 <= positions[i] <= 10 ^ 9

Time Limit: 1 sec
Sample input 1 :
1
5 3
1 2 3 4 6
Sample output 1 :
2
Sample input 2 :
2
4 2
5 4 2 1
6 4
6 7 9 13 15 11
Sample output 2 :
4
2
Explanation for Sample Output 2:
In test case 1, 
we only have to allocate rooms to 2 players so we can assign rooms that are first and last which are 1 and 5, so our answer is 5 - 1 = 4.

In test case 2, 
there is no way by which we can allocate rooms such that every player will have the 3 or more as its least distance to other players. So the answer is 2 and one possible allocation of rooms is as follows.
    Player1 = 6
    Player2 = 9
    Player3 = 11
    Player4 = 13
Approaches (2)
Bruteforce
  • The possible answer can be from 1 to max( positions[i] ) so we select one integer at a time form 1 to max( positions[i] ) and see if it is possible for that integer to be our answer.
  • Now how will we find whether an integer X is our possible answer or not? We can try to add the maximum number of players such that the distance between any two players is more than one equal to X.
  • How can we implement this? We can sort the positions first and can assume the first player is in the room first that is empty( positions[0] ). Now we will give a new room positions[i] to the next player only if the difference between the current room ( positions[i] ) and the previous allocated room is greater than or equal to X.
  • If by doing this we can allocate rooms to at least C players, the answer exists otherwise not.
  • Optimization: once we find  X for which the answer does not exist then we can simply stop our search because the answer will be possible for all X’s greater than current X.
  • The answer is the maximum possible X.
Time Complexity

O(N * max), where N is the total number of rooms and max is the maximum possible position for any room.

 

As we have to traverse all the possible answers and the answers are up to max. For each possible answer, we have to traverse all the positions of the room which is N. Hence, the overall Time Complexity is O(N * max).

Space Complexity

O(1).

 

Constant space is being used. Hence, the overall Space Complexity is O(1).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Chess Tournament
Full screen
Console