HI community I needed help in this coding problem.Any help would be appreciated, Thanks.
You are a coach of World Duo Coding championship. You want to choose the strongest team of two players from N players.Each player has some scores based on two parameters, Coordination and Problem Solving skills. The overall skill of a team is evaluated as the sum of Problem Solving Skills of both players and the absolute difference between Coordination of both players.
For example c[1] and ps [1] are Coordination and Problem Solving skills of player 1
c[2] and ps[2] are Coordination and Problem Solving Skills of Player 2
Then overall skill of the team of these two players is ps[1] + ps[2] + abs(c[1] – c[2]) The host of the contest has decided parameter K such that no team must have the absolute difference between the Coordination of both players more than K, that is, abs(c[1] — c[2]) <=K It is guaranteed that there exists at least one pair of players that satisfy the constraint abs(c[1] — c[2])<=k.
Your task is to determine the maximum possible overall skill of a team that you can send in this tournament
Input format an integer I denoting the number of test cases.
N,K denoting no of players and the parameter.
Next N lines contains c[i] and ps[i] denoting the coordination and problem solving skill of ith player.
Constraints N 10^5
k 10^8
c[i] ,ps[i] 10^8
SAMPLE INPUT
4 1
5 3
6 0
9 10
10 -10
OUTPUT
4
This is can be solved using multiset. Just sort the pair based on Ci values after that You ll have the equation in this form (ps[1] + ps[2] +cs[2] — cs[1]) . re arrange this to get (ps[2] + cs[2] + (ps[1] — cs[1]). after this push in a multiset all the points after the present point such that (cs[j]-cs[i] <= k) also use (ps[j]+cs[j]) as the sorting criteria once you have done this u ll get the largest value corresponding to i-th index. Try doing this for all i this will solve the problem in NlogN.
Also for ur practice . I attach the link to the same problem — Same problem I guess :)