Sumanto's blog

Hackerank Intermediate certification test problem.
By Sumanto, 5 years ago, In English

A coach of a school chess club wants to start a mentoring program for newer players. Each player has an integer rating representing skill level. The coach would like to pair up students whose ratings differ by no less than a given minimum. What is the maximum number of pairs that can be formed?

for ex: n=6; rating=[1,2,3,4,5,6]; minDiff=4; ans: 2; explaination: There are Two pairs of players have a difference of 4 or more; those ratinggs are (1,5) and (2,6)

Constraints: 1<=n<=2*10^5 0<=rating[i]<=10^9 0<=minDiff<=10^9

This was asked in Hackerank intermediate certification Test.I failed to come up with a solution better than quadratic.

  • Vote: I like it
  • -23
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please specify reason before downvoting the post? whether information is missing or i asked the wrong way? This will myself to ask in better manner in future posts.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe it's because you pasted the question into a coding block... Use plain text format for question.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The solution would be to sort the array in ascending order and then for each player find the next player with the least skill that satisfies the minimum criteria. Use binary search to find the next optimal player.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Sort the array in ascending order.
for ex: n=8; rating=[14,18,30,45,43,2,8,3]; minDiff=4;
After sorting [2,3,8,14,18,30,43,45]
Answer is in bold: [2,3,8,14,18,30,43,45]

It can be solved with greedy approach
Pseudo Code:
Array is sorted in ascending order.
int i=0; int Pairs=0;
while(i+1 < n)
{
if(abs(A[i]-A[i+1]) <= minDiff)
Pairs++; i+=2;
else
i++;
} PS: Sorry I understood question in wrong way.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It is a minDiff, not a maxDiff. You need a second pointer and solve it with 2 pointers after sorting the array.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Codeforces also got almost same question. It can be solved by using binary search. Here is the link of question

https://mirror.codeforces.com/contest/1156/problem/C

And editorial link:

https://mirror.codeforces.com/blog/entry/66827

→ Reply