Saving the city

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
0 upvote
Asked in companies
ShareChatBarclays

Problem statement

The avengers have the responsibility to save the world. To perform this task they have divided their responsibility such that each one takes the responsibility of one city. Mr. Stark aka Iron Man got the responsibility of the city Malibu. The only safe place in the city is the Stark tower. Now, Iron Man has to shift trapped people from different parts of the city to the Stark tower.

But he can only shift one person at a time. Due to less time he wants to take the shortest possible path. Help him to find the minimum distance that he had to cover to rescue all the trapped people.

Note:

1. Positions are represented by the cells in a 2D grid.
2. The positions of people don’t overlap.
3. Iron Man can move only up, down, left, and right to the adjacent cell.
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line contains a single integer ‘T’ representing the number of test cases. Then the test cases follow.

The first line of each test case contains two integers ‘HEIGHT’ and ‘WIDTH’ denoting the dimensions of the city. 

The second line contains two integers ‘X1’ and ‘Y1’ denoting the position of Stark Tower.

The third line contains two integers ‘X2’ and ‘Y2’ denoting the initial position of Iron Man.

The next line contains an integer ‘N’ denoting the number of trapped people.

The next ‘N’ line contains a 2D matrix ‘PERSONS’ of order ‘N’ x 2 denoting the position of ‘N’ people.
Output Format 
 For each test case, print the minimum possible distance Iron Man has to cover.

 Output for every test case will be printed in a separate line.
Note: 
You don’t need to print anything; It has already been taken care of.
Constraints 
1 <= T <= 50
1 <= HEIGHT <= 10^4
1 <= WIDTH <= 10^4
3 <= HEIGHT * WIDTH <= 10^4
1 <= N <= 10^4
0 <= X1, X2 < HEIGHT
0 <= Y1, Y2 <  WIDTH
1 <= PERSONS[i][j] <= 10^4

Where ‘HEIGHT’ and ‘WIDTH’ are the dimensions of the city, ‘X1’, ‘Y1’ represents the position of the tower, ‘X2’, ‘Y2’ represents the position of Iron Man, ‘N’ represents the number of trapped people and ‘PERSONS[i][j]’ represents the position of trapped people.


Time limit: 1 sec
Sample input 1:
2
5 7
2 2
4 4
2
3 0
2 5
1 3
0 1
0 0
1
0 2
Sample output 1:
12 
3
Explanation:
In the first test case, if we look at the positions, it will look like this


Here triangle represents the Stark tower, the rhombus represents the trapped persons and the stick figure represents the iron man.

We can see the path covered by Iron man (represented by the blue line). The distance covered by the Iron man is 12 units.

In the second test case, there is only one person but Iron Man has to go through the Stark tower then come back. So the minimum distance would be 3 units.

Sample Input 2
2
5 5
0 0
4 4
2
1 3
2 3
3 1
0 0
0 1
1
0 2
Sample Output 2
16
3
Hint

Can you analyze if the distance traveled by Iron man for every person follows the same pattern or is different for some people?

Approaches (1)
Mathematics

For rescuing trapped people firstly Iron Man will go to one person and shift him to the Stark Tower. Then move from Stark tower he will go to the next trapped person and shift him to the tower. After the first person, for every person, he is traveling the distance 2 * ‘D’ ( where ‘D’ be the distance between the tower and the person).

Here all people will be alike except the first one. So to minimize the distance covered, we need to find the person for which the value of ‘D’ - ‘X’ (where ‘D’ is the distance between the tower and the person, and  ‘X’ be the distance between the person and Iron Man) is maximum.

 

Our final answer will be Σ 2* ‘Di’ -  max (‘Di’ - ‘Xi’).

 

The steps are as follows:

 

  1. In the ‘HELPER’ function
    1. Find the distance between 2 points. This function will take ‘X1’, ‘Y1’, ‘X2’, ‘Y2’ as coordinates of 2 points.
    2. Return the absolute value of (‘X1’ - ‘X2’) + absolute value of ( ‘Y1’ - ‘Y2’).
  2. In the given function
    1. Declare a variable ‘SUM’ to store the sum of the distance from the tower to the person. It will be of type int, and its initial value will be 0.
    2. Declare another variable ‘MAX_DIFF’ to find the maximum value of the difference of distance from the tower to the person and the person to Iron man. It will be of type int and its initial value will be INT_MAX.
    3. Now iterate on every person in the ‘PERSONS’ matrix. (say iterator be ‘i’ )
      1. Store the distance between the ‘i-th’ person and the tower in a temporary variable ‘DIST’
      2. Increase ‘SUM’ as ‘SUM’ += 2 * ‘DIST’
      3. Let's say the distance between the ‘i-th’ person and Iron Man is stored in a temporary variable ‘X’.
      4. Find the maximum value of the difference of distance between the tower and person and the person and Iron man, by maximizing the ‘MAX_DIFF’ as ‘MAX_DIFF’ = max(‘MAX_DIFF’, ‘DIST’ - ‘X’).
    4. Return ‘SUM’ - ‘MAX_DIFF’
Time Complexity

O(N), where ‘N’ is the number of trapped persons.

 

We are iterating over every row in the ‘PERSONS’ array/list. So the complexity will be O(N).

Space Complexity

O(1).


Constant extra space is required.

Code Solution
(100% EXP penalty)
Saving the city
Full screen
Console