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

Problem

Submissions

Hints & solutions

Discuss

Chess Tournament

Easy

0/40

Average time to solve is 20m

121 upvotes

Asked in companies

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 :

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)

Approach 1

Approach 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).

(75% EXP penalty)

(100% EXP penalty)

Chess Tournament

Siddhartha Bharali

Interview problems

Java Binary Search

import java.util.* ;
import java.io.*; 
public class Solution {

    public static int focus(int p[],int d){
      int players=1,currd=p[0];
      for(int i=1;i<p.length;i++){
        if(p[i]-currd>=d){
          players++;
          currd=p[i];
        }
      }
      return players;
    }
    public static int chessTournament(int[] positions, int n,  int c) 
	{
        // Write your code here.   
        Arrays.sort(positions);
        int l=0,r=positions[n-1]-positions[0];
        while(l<=r){
         int mid=(l+r)/2;
         if(focus(positions,mid)<c) r=mid-1;
         else l=mid+1;
        }
        return r;
    }

}

234 views

0 replies

1 upvote

Ankesh kushwaha

Interview problems

best optimised solution using binary search.....

#include <bits/stdc++.h>

bool ispossible(vector<int> positions, int n, int c,int mid){

int studentcount=1;

int lastpos=positions[0];

for(int i=0;i<n;i++){

if(positions[i]-lastpos>=mid){

studentcount++;

if(studentcount==c){

return true;

}

lastpos=positions[i];

}

return false;

}

int chessTournament(vector<int> positions, int n, int c) {

sort(positions.begin(), positions.end());

int start = 0;

int maxi = -1;

for (int i = 0; i < n; i++){

maxi=max(maxi,positions[i]);

}

int end=maxi;

int mid=start+(end-start)/2;

int ans=-1;

while(start<=end){

if(ispossible(positions,n,c,mid)){

ans=mid;

start=mid+1;

}

else {

end=mid-1;

}

mid=start+(end-start)/2;

}

return ans;

}

620 views

0 replies

0 upvotes

Aryan Solanki

Interview problems

Python Binary Search Most Optimal Solution

from os import *
from sys import *
from collections import *
from math import *

def canStay(mid,positions,c):
    count=1
    prev=0
    for i in range(1,len(positions)):
        if positions[i]-positions[prev]>=mid:
            count+=1
            prev=i
        if count==c:
            return True
    return False

def chessTournament(positions, n , c):
    positions.sort()
    low=1
    high=positions[-1]
    while low<=high:
        mid=(low+high)//2
        if canStay(mid,positions,c):
            low=mid+1
        else:
            high=mid-1
    return high

python

147 views

0 replies

0 upvotes

Jay

Interview problems

Best Solution Ever | Production level Code

#include <bits/stdc++.h>

int isPossible(vector<int> &positions,int totalPlayers,int minDist){

int currPlayers = 1 , prevPosition = positions[0];

for(int currPosition : positions){

if(currPosition-prevPosition >= minDist){

++currPlayers;

prevPosition = currPosition;

}

return currPlayers >= totalPlayers;

}

int chessTournament(vector<int> positions , int n , int c){

sort(positions.begin(),positions.end());

int minDist = 0 ;

int maxDist = positions[n-1] - positions[0];

int maxFocus = maxDist;

while(minDist <= maxDist){

int currDist = minDist + (maxDist - minDist) / 2;

if(isPossible(positions,c,currDist)){

maxFocus = currDist;

minDist = currDist + 1;

}

else{

maxDist = currDist - 1;

}

return maxFocus;

}

226 views

0 replies

2 upvotes

Shubhanshu Jain

Interview problems

C++ || binary Search

#include <bits/stdc++.h> 
bool check(long long dis,vector<int> &arr,int c,int n){
	int player=1;
	long long pre_pos = arr[0];
	for(int i=0;i<n;i++)
	{
		if(arr[i]-pre_pos>=dis)
		{
			pre_pos=arr[i];
			player++;
		}
		if( player==c) return true;

	}
	return false; 
}
int chessTournament(vector<int> positions , int n ,  int c)
{
	sort(positions.begin(),positions.end());
	long long i=0;
	long long j=positions[n-1]-positions[0];
	long long ans=-1;
	while(i<=j)
	{
		long long m=i+(j-i)/2;
		if(check(m,positions,c,n))
		{
			i=m+1;
			ans=m;
		}
		else j=m-1;
	}
	return ans;
}

557 views

0 replies

0 upvotes

Husain Champawala

Interview problems

Similar to aggressive cows

#include <bits/stdc++.h>
bool canAssign(int c, int mid, vector<int> &positions) {
  int allot = 1, player = positions[0];
  for (int i = 1; i < positions.size(); i++) {
    if (positions[i] - player >= mid) {
      allot++;
      player = positions[i];
    }

    if (allot == c)
      return true;
  }

  return false;
}

int chessTournament(vector<int> &positions, int n, int c) {
  sort(positions.begin(), positions.end());
  int low = 1, high = positions[n - 1] - positions[0];
  int ans = -1;

  while (low <= high) {
    int mid = low + (high - low) / 2;
    if (canAssign(c, mid, positions)) { // minimum distance
      ans = mid;
      low = mid + 1;
    } else
      high = mid - 1;
  }
  return ans;
}

273 views

1 reply

1 upvote

Shivam Khandelwal

Interview problems

done by me, thought process is easier.

#include <bits/stdc++.h>

bool ispossible(int mid,vector<int> &positions,int c){

int cnt=1,res=positions[0];

for(int i=0;i<positions.size();i++){

//our target is to reach cnt ==c so if diff is greater than mid we try to split it

if(positions[i]-res>=mid){

cnt++;

//if our cnt reaches to c then we can adjust this last student to last index that'whywe return true

if(cnt==c)return true;

res=positions[i];

}

return false;

}

int chessTournament(vector<int> positions , int n , int c){

int low=1;

sort(positions.begin(),positions.end());

int maxi=INT_MIN;

int mini=INT_MAX;

for(int i=0;i<n;i++){

maxi=max(maxi,positions[i]);

mini=min(mini,positions[i]);

}

int high=maxi-mini;

while(low<=high){

int mid=(low+high)/2;

//if mid is possible minimum difference for students

if(ispossible(mid,positions,c)){

//if it is possible minimum then we want to maximize it

low=mid+1;

}

//we cant divide diff(mid) among students so reduce this mid

else high=mid-1;

}

return high;

// Write your code here

}

325 views

0 replies

0 upvotes

Abhi shikth

Interview problems

Simple Java Code (Problem similar to Aggressive Cows)

import java.util.* ;
import java.io.*;
public class Solution {

public static int chessTournament(int[] arr, int n, int c)
{
// Write your code here.
Arrays.sort(arr);
int startPosi = 0;
int endPosi = arr[n-1];

int ans = -1;

while(startPosi <= endPosi)
{
int mid = startPosi + (endPosi - startPosi) /2;

if(isPossible(arr, mid, c, n))
{
ans = mid;
startPosi = mid +1;
}
else{
endPosi = mid - 1;
}
}

return ans;
}

static boolean isPossible(int[] positions, int maxSpace, int players, int n)
{
//who got allocated room
int Currplayers = 1;
//last position of the room which was allocated by player
int lastPos = positions[0];
for(int i=0; i<n; i++)
{
if(positions[i] - lastPos >= maxSpace)
{
Currplayers++;
if(Currplayers > players) return false;
if(Currplayers == players) return true;
lastPos = positions[i];
}

}
return false;
}

}

223 views

0 replies

0 upvotes

Aman Karn

Interview problems

C++ | Using Binary search 🎉🎉

#include <bits/stdc++.h>

bool isdivided(vector<int> positions , int n , int c,int mid)

{

int rmcnt=positions[0];

int player=1;

for(int i=0;i<n;i++)

{

//is distnace mid enough and all players are allocated with rtheir room or not

if(positions[i]-rmcnt>=mid)

{

player++;

if(player==c)

{

return true;

}

rmcnt=positions[i];

}

return false;

}

int chessTournament(vector<int> positions , int n , int c){

// Write your code here

sort(positions.begin(),positions.end());

int maxi=-1;

for(int i=0;i<n;i++)

{

maxi=max(maxi,positions[i]);

}

int ans=-1;

int s=1;

int e=maxi;

//FUNCTION TO CHECK THAT IS IT POSSIBLE KEEP THE PLAYER MID DISTANCE AHEAD

//IF YES THEN CHECK FOR IS MID CAN BE MORE

//IF NO THEM REDUCE THE DISTANCE BETWEEN TWO PLAYER

while(s<=e)

{

//start with maximum seperation btwn 2 players

int mid=s+(e-s)/2;

if(isdivided(positions,n,c,mid))

{

ans=mid;

s=mid+1;

}

//if dist mid is not satisfied then we reduce it

else

{

e=mid-1;

}

return ans;

}

284 views

0 replies

0 upvotes

Hritik Das

Interview problems

cpp solution

#include <bits/stdc++.h>

bool ispossible(vector<int> positions , int n , int c, int mid){

int players = 1;

int roomcnt = positions[0];

for(int i =0;i<positions.size();i++){

if (positions[i] - roomcnt >= mid) {

players++;

if (players == c) {

return true;

}

roomcnt = positions[i];

}

return false;

}

int chessTournament(vector<int> positions , int n , int c){

if(positions.size() < c) return -1;

sort(positions.begin() , positions.end());

int s = 1;

int maxi = -1;

for(int i=0;i<positions.size();i++){

maxi=max(maxi ,positions[i]);

}

int e = maxi;

int ans =-1;

while(s<=e){

int mid = s+(e-s)/2;

if(ispossible(positions , n , c, mid)){

ans = mid ;

s = mid+1;

}

else{

e = mid-1;

}

return ans;

}

113 views

0 replies

0 upvotes

Console