Fastest Ninja

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
1 upvote
Asked in company
Visa

Problem statement

After the pandemic ended, Alice and Bob finally got the chance to play some outdoor games. They decided to play “Fastest Ninja” along with their ‘N’ other friends. The game is as follows,

1. Bob and Alice are standing at coordinates (0, 0) and (‘X’, ‘Y’), respectively, in the X-Y plane.

2. All the other ‘N’ friends are standing at some coordinates in the X-Y plane. The starting positions of all the ‘N’ friends are given as a 2 - Dimensional array of integers ‘positions’, where ‘position[i]’ denotes the starting position of the i-th friend.

3. In one move, Bob and his ‘N’ friends can independently choose to do one of the following two things:

    1. Stay at their current position.

    2. Move to any of the four neighboring positions, i.e., for any (x, y) move to north(x, y + 1), south(x, y - 1), east(x + 1, y), or west(x - 1, y).

To win the game, Bob has to reach Alice before any of his ‘N’ friends catches him. As Bob’s friend, your task is to tell him whether he can win the game or not.

Note: 
All the coordinates are integral coordinates on the X-Y plane

There can be multiple friends with the same starting position(including Alice and Bob).

Bob and his ‘N’ friends move simultaneously.

Bob loses if he reaches any coordinate(including Alice’s position) at the same time as any of his ‘N’ friends.
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains a single integer, ‘N’, where ‘N’ denotes the number of other friends of Alice and Bob.

The second line of each test case contains two space-separated integers, ‘X’ and ‘Y’, where (‘X’, ‘Y’) denote Alice’s position.

The next ‘N’ lines of each test case contain two space-separated integers, ‘position[i][0]’  and ‘position[i][1]’, where (‘position[i][0]’, ‘position[i][1]’) denotes the starting position of the i-th friend.
Output Format: 
For each test case, print 1 if Bob can win the game, else print 0.

The output of each test case will be printed in a separate line.
Note: 
 You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 5
1 <= N <= 5000
-10 ^ 7 <= X, Y <= 10 ^ 7
-10 ^ 7 <= position[i][0], position[i][1] <= 10 ^ 7

Time Limit: 1 sec
Sample Input 1:
2
3
2 2
0 1
1 0
1 1
4
3 0
-1 0
-5 2
5 5
0 1
Sample Output 1:
0
1
Explanation For Sample Input 1:
Test Case 1 :

1

Starting positions of Bob and his three friends are marked in orange and red color, respectively. The position of Alice is marked with green color.

Bob cannot win, as his friend at (1, 1) can reach Alice before him.

Test Case 2 :

1 

Starting positions of Bob and his four friends are marked in orange and red color, respectively. The position of Alice is marked with green color.

No one can reach Alice before Bob. Hence he will win the game.

Sample Input 2:

1
4
0 0
1 -1
1 2
3 -4
0 1

Sample Output 2:

1
Hint

Try to think about the scenarios when Bob cannot win the game. What happens if any of Bob’s ‘N’  friends can reach Alice before him?

Approaches (1)
Maths

The idea here is to consider all those scenarios when Bob cannot win the game. There are two possible scenarios:

 

  • When any of his ‘N’ friends reaches Alice before or at the same time as Bob. Since the friend who reaches Alice before Bob can wait at that position for Bob.
  • When any of his ‘N’ friends catch him before reaching Alice.

 

Let’s consider the 2nd scenario with a diagram,

 

 

Point A denotes the starting position of Bob, point D denotes the starting position of any of Bob’s ‘N’ friends, point C denotes the position of Alice, and point B denotes the position where Bob’s friend catches him before reaching Alice.

 

It is clear from the figure above that points B, D, and C form a triangle. Moreover, for his friend to catch him, AB must be equal to DB.

 

By the triangle inequality, DB + BC must be greater than or equal to DC, which is AB + BC must be greater than or equal to DC. Hence, AC must be greater than or equal to DC.

 

This means that for Bob’s friend to catch him before reaching Alice, the distance between Alice and Bob must be greater than or equal to the distance between Alice and his friend, which is the same as the 1st scenario as his friend can reach Alice before him. So we just need to check if any of Bob’s ‘N’ friends can reach Alice before him or not.

 

Algorithm:

 

  • Declare an integer, say ‘minMoves’ to store the minimum number of moves that Bob requires to reach Alice.
  • Do ‘minMoves’ = absolute(X - 0) + absolute(Y - 0), As the minimum number of moves that Bob requires to reach Alice is equal to the Manhattan distance between them.
  • Run a loop for ‘i’ from 0 to ‘N’ - 1.
    • Declare an integer, say ‘currMoves’, to store the minimum number of moves that i-th friend requires to reach Alice.
    • Do ‘currMoves’ = absolute(X - position[i][0]) + absolute(Y - position[i][1]), similarly the minimum number of moves that i-th friend requires to reach Alice is equal to the Manhattan distance between them.
    • If ‘currMoves’ is less than or equal ‘minMoves’
      • Return false, as Bob cannot win the game, since his i-th friend can reach Alice before him.
  • Return true, as Bob can reach Alice before any of his ‘N’ friends.
Time Complexity

O(N), where ‘N’ denotes the number of other friends of Alice and Bob.

 

We iterate through all the starting positions of Bob’s ‘N’ friends, which takes O(N) time.

 

Therefore, the total time complexity will be O(N).

Space Complexity

O(1)

 

We do not take any extra space.

Code Solution
(100% EXP penalty)
Fastest Ninja
Full screen
Console