PROBLEM SETTER -
ZCO 2013
PROBLEM LINK -
DIFFICULTY –
Medium
PREREQUISITES –
Dynamic Programming, Mathematics
PROBLEM IN SHORT –
Just don’t read the first paragraph. The problem statement can’t be shorter.
SOLUTION IN SHORT –
Find out the reachable nodes for every point in the range of every blaster with mathematical formulae described below and mark them 0 in a 2-D array and the rest of elements as 1. The classic DP can be formulated to find if a path from the top left to the bottom right corner, which only consists of 0, exists. If the path exists, then the answer is “YES”, or else the answer is “NO”.
KEY OBSERVATIONS –
- Spaceman Spiff always arrives at coordinate/point (x,y) at time x+y-2, irrespective of the path taken.
- If the answer is YES, the time taken is always N+M-2, in accordance with observation one.
- Spaceman Spiff has always 2 choices, to move down or right and thus, after eliminating those points (x,y) where pulse crosses at time x+y-2 and marking them specially, we have to find if there exists a path from top left to the bottom right corner of the grid.
FIRST SUBTASK SOLUTION –
Since there is only one blaster, we can easily brute out the points(x,y) where pulse crosses at time x+y-2. It can be done by iterating on frequency i from 0 while t + i*f <= N + M - 2, since this is the maximum time spaceman spiff can spend in the grid. We have created a 2-D array in which a[i][j] is 1 if (i,j) is not accessible and 0 if it is accessible. This has to be checked for (N+M-2) points, and it is trivial to check since we know that i^{th} pulse will reach (p, q) from (X, Y) at time T + i*f + {\lvert}p-X{\rvert} if q = Y and T + i*f + {\lvert}q-y{\rvert} if p = X. One of the conditions, q = Y and p = X, will be true as the pulse can travel only horizontally or vertically, not diagonally.
TIME COMPLEXITY OF CHECKING ACCESSIBILITY -
Since i can be at most max(N, M), and for each i, we iterate on (N+M) points, the time complexity is
O(Max(N,M) * (N+M))).
After this, a DP solution can be formulated to check if a safe path (consisting of only 0s) exists. dp(i,j) is 1 if there exists a path from (i,j) to (N,M) and 0 otherwise. So, dp(i,j) = ( dp(i+1,j) || dp(i,j+1) ), meaning (N,M) is reachable from (i,j) if it is reachable from either of (i+1,j) or (i,j+1). This is a well known DP recurrence. Please learn Dynamic Programming from here, and you can read more about this specific recurrence from here.
Here is the recurrence pseudo-code –
dp(int i,int j)
{
if(i>n || j>m) // out of bounds check
return 0
if(a[i][j] = 1)
return 0
else
return dp(i+1,j) || dp(i,j+1)
}
Answer is “YES” if dp(1,1) is 1, or else the answer is “NO”.
TIME COMPLEXITY OF DP PART -
O(N*M)
TOTAL TIME COMPLEXITY -
O(2*N*M)
SECOND SUBTASK SOLUTION –
The DP part of the previous solution is also used in this solution. Change is only in the part of finding unreachable nodes. The previous algorithm of checking the accessibility can’t work as it requires a time of O(Max(N, M) * (N+M))) per blaster and 2500 * 2500 * 2500 = 15625000000, which is simply not feasible. We can have at most 2500 blasters, and there can be (N+M-2) possible points for each blaster to be unreachable. Thus, we need to check for every blaster, whether every point in its range (total N+M) is unreachable in O(1). Let us apply a little math here –
Let us assume we are checking for a blaster with time T, frequency F, and coordinates(X, Y). Also, we are checking the reach ability of coordinates (p, q). Then, for vertical pulses,
has to be valid if it is unreachable. u is a constant non-negative integer which represents the cardinal number of the pulse which will reach (p, q). u = 0 represents the first pulse at time T. Remember, q will be same as Y, as pulses can travel only horizontally or vertically and not diagonally.
Rearranging the terms,
\frac{p + q – 2 –T - {\lvert}p-X{\rvert}}{F} = u, u must be a non-negative integer for coordinates (p, q) to be reachable. If it is not, then (p, q) are reachable because the frequency is fixed and cardinal number cannot be non-integral. So, we just need to check for this condition –
If the above condition is true, mark a[p][q] as 1, or else do nothing.
For horizontal pulses,
has to be valid if (p, q) is unreachable. u is a constant non-negative integer which represents the cardinal number of the pulse which will reach (p, q). u = 0 represents the first pulse at time T. Remember, p will be same as X, as pulses can travel only horizontally or vertically and not diagonally.
Rearranging the terms, \frac{p + q – 2 –T – {\lvert}q-Y{\rvert}}{F} = u, u must be a non-negative integer for coordinates (p, q) to be reachable. If it is not, then (p, q) are reachable because the frequency is fixed and cardinal number cannot be non-integral. So, we just need to check for this condition –
If the above condition is true, mark a[p][q] as 1, or else do nothing.
TIME COMPLEXITY OF CHECKING ACCESSIBILITY –
O(K * (N+M))
Now that we have marked all the points, which are reachable and which are not, we can use the same DP recurrence as used in subtask 1 to arrive at the final solution.
TOTAL TIME COMPEXILY -
O(K*(N+M) + N*M)