Bob and Alice have teamed up on a game show. After winning the first round, they now have access to a maze with hidden gold. If Bob can collect all the gold coins and deliver them to Alice's position, they can split the gold. Bob can move horizontally or vertically as long as he stays in the maze, and the cell is not blocked.
The maze is represented by an n xm array. Each cell has a value, where 0 is open, 1 is blocked, and 2 is open with a gold coin. Bob starts at the top left in cell in (row, column) = (0, 0). Alice's position is given by (x,y). Determine the shortest path Bob can follow to collect all gold coins and deliver them to Alice. If Bob can't collect and give all the gold coins, return -1.
Example: maze = [[0,2,1],[1,2,0],[1,0,0]] with Alice at (2,2) is represented as follows:
B represents Bob's starting position at (0,0), and A represents Alice's position (which will also be Bob's final position). As Bob starts at (0,0), he has two possible paths to collect the gold and deliver to Alice: (0, 0) -> (0, 1) -> (1, 1) -> (2, 1) -> (2, 2) and (0, 0) -> (0, 1) -> (1, 1) -> (1, 2) -> (2, 2). Both paths have a length of 4 and could represent the shortest path.
Function Description
Complete the function minMoves in the editor below. The function must return the integer length of Bob's shortest path, or -1 if it's not possible.
minMoves has the following parameter(s):
maze[maze[0][0]...maze[n-1][m-1]]: a 2D array of integers
x: an integer denoting Alice's row coordinate
y: an integer denoting Alice's column coordinate
Constraints:
There are n players. They have to collect m points. All the players and coins are in 1-D space i.e on a number line. The initial location of all the players is given as the array players where player[i] denotes the location of the ith player. The location of all the points is given as another array point where point[i] denotes the location of the ith point. In one second a player can either move 1 step left or 1 step right or not move at all. A point is considered collected if any of the n players had visited the point's location. The players can move simultaneously and independently of each other every second.
The task is to find the minimum time (in seconds) required to collect all the points if players act optimally.
Note: Locations of players and points are not necessarily given in sorted order.
Example
n = 3, players = [3, 6, 7]
m= 4, points = [2,4,7,9]
All the points can be collected in 2 seconds:
It can be proved that we can't collect all the points in less than 2 seconds. Hence the answer is 2.
Function Description
Complete the function getMinimumTime in the editor below. The function must return an integer, the minimum time required to collect all the points
getMinimumTime has the following parameters:
players[players[0]....players[n-1]]: an array of integers denoting the locations of players
points(points[0]....points[m-1]]: an array of integers denoting the locations of points
Constraints
In many real world applications the problem of finding a pair of closest points arises. In the real world, data is usually distributed randomly. Given n points on a plane that are randomly generated with uniform distribution, find the squared shortest distance between pairs of these points.
Example
There are 3 points with x coordinates x = [0, 1, 2] and y = [0, 1, 4]. The points have the xy coordinates (0, 0), (1, 1) and (2, 4). The closest points are (0, 0) and (1, 1), and their squared shortest distance is ((1-0)^2) + ((1-0)^2) = 2.
Function Description
Complete the function closestSquaredDistance in the editor below.
closestSquaredDistance has the following parameter(s):
int x[n]: each x[i] denotes the x coordinate of the ith point int y[n]: each y[i] denotes the y coordinate of the ith point
Returns:
long: a long integer that denotes the squared shortest distance between the pairs of points
Constraints
Question 1:
Overview
c
coins. Bob has to start from (0,0)
, collect all the coins, and reach Alice at (x,y)
.Approach:
(0,0)
,(x,y),
and points that have coins as vertices for the TSP graph(0,0)
and (x,y)
corresponds to the same starting vertex, such that we get the outgoing edges from (0,0)
and incoming edges from (x,y).
O(no of coins * size of matrix)
=10*100*100
O(K!)
, where k is the number of vertices, in our case, c+1
10!=3628800
(this is in 1 sec range)(2^K)*(K^2)
-Complexity:
O((C+1)!+C*N*M)
O((2^(c+1))*((c+1)^2 + C*N*M)
C
, no of coins.N*M
, dimension's of the gridQ2)
int find_right(int point_pos,int player_pos,int max_time)
{
int R=point_pos;
while((R<m) and ((points[R]-players[player_pos])<=max_time))
R++;
return R;
}
bool F(int max_weight)
{
int i=0,j=0;
while((i<n) and (j<m))
{
if(points[j]>=players[i])
{
while((j<m) and (points[j]-players[i] does not exceed max_time))
j=j+1
i=i+1;
}
else
{
int required_time_left=players[i]-points[j];
if(required_time_left<=max_time)
{
//cover all points <=players[i] from j to right
while((j<m) and (points[j]<=players[i]))
j++;
if(j==m)// covered all return 1
return 1;
int ch1=j,ch2=j;
//go left then go right
//point(j)<------------player(i)
//|
//|
//|------------------------------------>
//round trip takes 2*(player(i)-point(j))
//remaining=max_time-2*(player(i)-point(j))
if(2*required_time_left<=max_time)
{
int move_right=max_time-2*required_time_left;
//find maximum position you could go if move_right time you have
int max_right=find_right(i,j,move_right);
ch1=max_right;
}
//go right then go left
//point(j) player(i)----------->
// |
// |
// <---------------------------------------
//Since you have to cover j so first use that time
//and check how much you can go to right with
//remaining time that is max_time-(player(i)-point(j))
//Since you have to do round trip let's suppose you go R towards right
//then total distance=player(i)-point(j)+2*R
//and player(i)-point(j)+2*R<=max_time
//R<=floor((max_time-(player(i)-point(j)))/2);
if(max_time>=required_time_left)
{
int move_right=(max_time - required_time_left)/2;
//find maximum position you could go if move_right time you have
int max_right=find_right(i,j,move_right);
ch2=max_right;
}
j=max(ch1,ch2);
//now move pointer i because player i had covered all the points
//that it can.
i=i+1;
}
else
return 0;
}
}
}