I am trying to solve a problem which is a single row variant of skyscraper puzzle. The problem statement is:
Consider a single row of a skyscraper puzzle of size nxn. If we know how many buildings can be seen from the left, and from the right, of the row, how many different ways are there of populating that row with buildings of heights 1..n? (1<=n<=5000)
I am solving it with bottom up dynamic programming. Recurrence relation is following:
f(n,left,right)=(n-2)*f(n-1,left,right) + f(n-1,left-1,right) +f(n-1,left,right-1)
f[1][1][1]=1;
Don't worry about big numbers in answer as I am supposed to show modulo result. I am able to get correct answer from this but the memory requirement for this algorithm is very high. Space Complexity for this will be O(n^3) which is too much for given problem since n can be upto 5,000.
Can you please suggest me some alternate algorithm?
Edit:
For explanation of my recurrence relation:
consider all combination with (n-1) height and now add 1 height to all the building. This will give us buildings from 2,3 to n. Now only building with height 1 has to be adjusted. It can be adjusted on either sides which is second and third term int addition.
If it is inserted in not on the sides, then that is represented by first term in addition. Please let me know if it is still unclear, I would really appreciate any help
Ok, to solve this problem we need to make several observations:
First, the highest building will separate the view from left and right, so, if we can decide the position of the highest building, we can solve the left and right view problem separatedly.
Assuming that we have a function f(x, n) which calculate the number of ways we can see x buildings out of n building from one side. So, after we decide the position of the highest building, the result will be f(left - 1, a - 1)*f(right - 1, n - a - 1)*c(a - 1, n - 1) with a is the position of the highest building, a - 1 will be the number of buildings at the left side of the highest building, and function c(a - 1,n - 1) calculates number of way to pick a - 1 buildings out of n - 1 buildings (Because we need to pick randomly a - 1 buildings to put to the left side).
So, we can create a dp[n][n] table to store result of function f(x, n). And for each position a of the highest building:
we have answer += dp[left - 1][a - 1]*d[right - 1][n - a - 1]*c[a - 1][n - 1].
To calculate table dp[n][n] in O(n^2) time complexity, we need to make some other observations:
- For each
dp[x][y], we have dp[x][y] = sum of dp[x - 1][y - z - 1]*P(z, y - 1) , which means we select z buildings and hide them randomly after the highest building (the highest building is always counted in those seen buildings). Function P is to calculate the permutation.
As P(a,b) = b! / (b - a)!, so, we can see that if we use an extra array total , which store total[x] += dp[x][y]/ y!, we have:
dp[x][y] = total[x - 1]* (y - 1)!
= (dp[x - 1][0]/0! + dp[x -1][1]/1! + ... + dp[x - 1][y - 1]/ (y -1)!)*(y - 1)!
= dp[x - 1][0]*P(y - 1, y - 1) + dp[x - 1][1]*P(y - 2, y - 1) + ...
thus, we can calculate dp in O(n^2):
for(int y = 1; y <= n; y++){
for(int x = 1; x <= y; x++){
dp[x][y] = total[x - 1]*(y - 1)!;
total[x] += dp[x][y]/y!;
}
}
And with this, we complete our problem, keeping both time and space complexity in O(n^2).
Note: after going through the problem statement, we need to calculate the number of way mod 1000,000,007, so you should use modulus inverse for this problem, which also help to avoid precision problem.
I will try to explain a potential solution in pseudocode, hopefully I don't mix up some indices; if the solution works, the space complexity can be reduced to O(n*n). Supposing that the recurrence relation given above
f[1][1][1]=1;
f(n,left,right)
=(n-2)*f(n-1,left,right)+f(n-1,left-1,right)+f(n-1,left,right-1)
is evaluated as
let f:int[N][N][N];
f(1,1,1) = 1;
for ( int n = 0; i < N; n++ )
for ( int left = 0; left < N; left++ )
for ( int right = 0; right < N; right++ )
f(n,left,right)
= (n-2)*f(n-1,left,right)+f(n-1,left-1,right) +f(n-1,left,right-1);
the evaluation can be changed by using only two "slices" for the outermost dimension as follows.
let slice1:int[N][N];
let slice2:int[N][N];
slice1(1,1) = 1;
for ( int n = 0; i < N; n++ )
for ( int left = 0; left < N; left++ )
for ( int right = 0; right < N; right++ )
slice2(left,right)
= (n-2)*slice1(left,right)+slice1(left-1,right)+slice2(left,right-1);
exchange slice1 and slice2
Hopefully the idea becomes clear in this notation. The basic idea is to note that for generation of the n-th slice, only the n-1-th slice is necessary. The idea is similar to the fact that Pascal's triangle can also be evaluated in linear space, as for the generation of the 'n'-th row only the n-1-th row is necessary; in total, for both problems, a naive evaluation can be improved in terms of space complexity by not storing all intermediate results.
