Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Chess Tournament

Easy
0/40
Average time to solve is 20m
118 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 )
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 
Full screen
Console