Rugby Practice

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
0 upvote

Problem statement

Rugby tournament is coming up, so the ninja and his friends decided to practice for it.

They are practising their passing skills, and each player can throw up to a maximum distance of ‘K’.

There are a total of ‘N’ players. The position of the ‘X’ coordinate of ith player in the field is POSITION[i]. There can be more than one player on the same ‘X’ coordinate.

You are given a list of ‘M’ pairs of players ‘P’ determine for each pair if they can pass the ball to each other or not.

Players can pass either directly or indirectly with the help of other players.

Example: 
Input: ‘N’ = 4  ‘K’ = 2  ‘M’ = 3  ‘POSITION’ = [3, 1, 5, 10]   ‘P’ = [ [1, 4], [1, 3], [2,3] ]

Output:  No
         Yes    
         Yes

For the first pair: There is no way player 1 can pass the ball to player 4.
For the second pair: player 1 can directly pass to player 3.
For the third pair: player 2 can pass it to player 1 who can further pass it to player 3.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains ‘T’, denoting the number of test cases.    

The first line of each test case contains three integers ‘N’, ‘K’ and ‘M’ denoting the number of players, maximum throw distance and number of pairs respectively.

The second line of each test case contains ‘N’ single space-separated integers, elements of the array ‘POSITION’.

Each of the next ‘M’ lines contains two integers denoting the pair of players.
Output format : 
For each of the pairs of every test case print 'Yes' if they can pass the ball otherwise 'No'.
‘YES’, ‘yes’, ‘NO’ all are different, output is case sensitive. 
Print the answer to each pair in a new line.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1  <= T <= 10
1 <= N, M <= 105
0 <= POSITION[i], K <= 109
1 <= P[i][j] <= N   

Time Limit: 1 sec
Sample Input 1 :
2   
5 5 2
7 1 20 14 11
1 4
3 4
2 1 1
1 10
1 2

##### Sample Output 1 :

Yes
No
No
Explanation Of Sample Input 1 :
For the first test case:-   
For the first pair: Player 1 can pass the ball to player 5 who can further pass it to player 4.
For the second pair: There is no way player 3 can pass the ball to player 4.

For the second test case:-
There is no way we can pass the ball from player 1 to player 2.
Sample Input 2 :
2
6 10 4
6 10 55 26 40 19 
2 3
5 1 
2 4
4 3
3 2 1
2 1 9
1 2
Sample Output 2 :
No
No
Yes
No
Yes
Hint

Think of passing the ball to the nearest player and check if it can reach to other player or not.

Approaches (2)
Brute Force

In this approach, we will store the ‘X’ coordinate of each player along with its index in a 2D array ‘sortedPos’.

 

sortedPos[i][0] : ‘X’ coordinate of player.

sortedPos[i][1] : index of the player.

 

We will then sort ‘sortedPos’ based on ‘X’ coordinate and then store the new positions of the players in another array so that we can access the new position of players in constant time. Then for each pair, we will start passing the ball to the near-most player and check if it can reach to other player or not.

 

The steps are as follows:-

function canPairsPass(int n, int k, int m, [int] positions, [ [ int ] ] p):

  1. Declare an array of strings ‘ANS’ to store the answer for each pair.
  2. Store the given positions of players along with their indexes in a 2D array ‘sortedPos’.
  3. Sort the 2D array ‘sortedPos’ based on the ‘X’ coordinate.
  4. Store the updated positions of players in an array ‘playerPos’.
  5. playerPos[i] : position of ith player in ‘sortedPos’.
  6. For each pair
    • Declare a boolean variable ‘canPass’, denoting if the players can pass the ball to each other or not.
    • Assign true to ‘canPass’.
    • Run a for loop from the player with the leftmost coordinate to the player with the rightmost coordinate in the pair.
      • If it is not possible to pass the ball to an adjacent player.
        • Assign false to ‘canPass’.
    • If the value of ‘canPass’ is true then store 'Yes' otherwise 'No' in ‘ANS’.
  7. Return ‘ANS’.
Time Complexity

O( N * log( N ) + N * M ), Where ‘N’ is the number of players and ‘M’ is the number of pairs.

 

We are sorting the array ‘sortedPos’ and for each of the ’M’ pairs, we are traversing the ‘sortedPos’ array with a time complexity of O(N).

 

Hence the time complexity is O( N * log( N ) + N * M ).

Space Complexity

O( N ), Where ‘N’ is the number of players.

 

Extra space will be needed for storing the ‘X’ coordinates with index and updated positions of the players.

 

Hence space complexity is O( N ).

Code Solution
(100% EXP penalty)
Rugby Practice
Full screen
Console