Last Updated: 14 Aug, 2022
Rugby Practice
Moderate
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.
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
Approaches
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):
- Declare an array of strings ‘ANS’ to store the answer for each pair.
- Store the given positions of players along with their indexes in a 2D array ‘sortedPos’.
- Sort the 2D array ‘sortedPos’ based on the ‘X’ coordinate.
- Store the updated positions of players in an array ‘playerPos’.
- playerPos[i] : position of ith player in ‘sortedPos’.
- 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 it is not possible to pass the ball to an adjacent player.
- If the value of ‘canPass’ is true then store 'Yes' otherwise 'No' in ‘ANS’.
- Return ‘ANS’.
In this approach, we will precompute the maximum distance reachable from every player.
First, 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 sort ‘sortedPos’ in ascending order of x coordinate and store the new index of each player in another array so that we can access them in constant time.
We will use the simple recurrence DP[i] = DP[i+1] ( when player at sortedPos[i][0] can pass to player at sortedPos[i+1][1]).
DP[i]: maximum distance reachable by player standing at sortedPos[i][0].
Now at last for each pair, we will check the maximum distance reachable by them. If it is the same then they can pass the ball to each other. As if the ball can reach to the other player they must be having same maximum distance to the right.
The steps are as follows:-
function canPairsPass(int n, int k, int m, [int] positions, [ [ int ] ] p):
- Declare an array of strings ‘ANS’ to store the answer for each pair.
- Store the given positions of players along with their indexes in a 2D array ‘sortedPos’.
- Sort the 2D array ‘sortedPos’ based on the ‘X’ coordinate.
- Store the updated positions of players in an array ‘playerPos’.
- playerPos[i] : position of ith player in ‘sortedPos’.
- Declare an array ‘DP’.
- DP[N-1] = sortedPos[N-1][0] + K.
- Run a for loop from i = N-2…0
- If sortedPos[i][0]+k >= sortedPos[i+1][0].
- Then DP[i]=DP[i+1].
- Otherwise DP[i] = k+sortedPos[i][0].
- If sortedPos[i][0]+k >= sortedPos[i+1][0].
- For each pair:
- Check from the DP table if the maximum distance reachable is same for both players then store ‘Yes’ otherwise ‘No’ in ‘ANS’
- Return ‘ANS’.