Chess Tournament

Posted: 18 Dec, 2020
Difficulty: Easy


Try Problem

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.
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.
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
Approach 1
  • 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.
Try Problem