TopCoder SRM 395 Div 1 Medium (Skyscrapers)

Problem link: http://www.topcoder.com/stat?c=problem_statement&pm=8582&rd=11129

Problem description -

The skyline of the city of Terrapin City has N buildings all in a straight line; each building has a distinct height between 1 and N, inclusive. The building at index i is considered visible from the left is there is no building with a smaller index that is taller (formally, height[j] < height[i] for all j < i). Similarly, a building is visible from the right if there is no taller building with a higher index (height[j] < height[i] for all j > i). For example, if the buildings in order are {1, 3, 5, 2, 4}, then three buildings are visible from the left (1, 3 and 5), but only two are visible from the right (4 and 5).



You will be given N, leftSide and rightSide, corresponding to the total number of buildings, the buildings visible from the left, and the buildings visible from the right, respectively. Return the number of permutations of the buildings that are consistent with these values; as this can be a large number, you should return it modulo 1000000007. N will be between 1 and 100, inclusive. leftSide and rightSide will be between 1 and N, inclusive.

It is a dynamic programming problem. Among the N elements, if we place the highest element in position i (1-based), it will be visible from both left and right. So, we now will need to know number of ways we can place buildings such that there are leftSide-1 buildings visible among the i-1 buildings on the left and rightSide-1 buildings visible among the N-i buildings on the right. You can choose the left set of buildings in nCr(N-1, i-1) ways.

Now, to calculate the number of ways in which we can place N buildings such that S are visible from left (or right), we can think in a similar way. This time, place the smallest one first. If we place it on the leftmost position, it will be visible and we have to solve the sub-problem of N-1 buildings with S-1 visible ones. Otherwise, we can place the smallest one in one of the N-1 available positions (where it will not be visible) and solve the sub problem of N-1 buildings with S visible ones.

I tried to place the largest one first in the second case, but it doesn't always work. You can find the code commented. Can you suggest what I was doing wrong?

You can find other approaches for this problem in the official match editorial.

C++ source code -

/*
Problem Name : Skyscrapers
Problem Number : TopCoder SRM 395 Div 1 Medium
Link : http://www.topcoder.com/stat?c=problem_statement&pm=8582&rd=11129
Problem Type : Dynamic Programming
Difficulty : 6 / 10
Interest : 8 / 10
Complexity : O(N^2)
Date : November 22, 2010
*/
#include<string>
#include<vector>
#include<sstream>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;

#define MAXN 100

const long long MOD = 1000000007;
long long fact[MAXN+2];

struct Skyscrapers{
 long long dp[MAXN+2][MAXN+2];
 long long ncr[MAXN+2][MAXN+2];

 long long go(int N, int S) {
  if(N <= 1) {
   if(S == N) return 1;
   return 0;
  }
  if(dp[N][S] != -1) return dp[N][S];
  long long &ret = dp[N][S];
  ret = (go(N-1,S-1) + (N-1) * go(N-1,S))%MOD;
  return ret;
  /*ret = 0;
  for(int i = 1; i <= N; i++) {
   ret = (ret + (go(i-1,S-1) * (fact[N-i] * nCr(N-1,N-i))%MOD)%MOD) % MOD;
  }
  return ret;*/
 }

 long long nCr(int n, int r) {
  if(r == 0) return 1;
  if(r > n) return 0;
  
  if(ncr[n][r] != -1) return ncr[n][r];
  long long &ret = ncr[n][r];
  ret = (nCr(n-1,r) + nCr(n-1,r-1))%MOD;
  return ret;
 }

 int buildingCount(int N, int L, int R) {
  long long res = 0;
  int i;
  memset(dp,-1,sizeof(dp));
  memset(ncr,-1,sizeof(ncr));
  fact[0] = 1;
  for(i = 1; i <= MAXN; i++) fact[i] = (fact[i-1] * (long long)i) % MOD;
  for(i = 1; i <= N; i++) {
   res = (res + ((go(i-1,L-1)*go(N-i,R-1))%MOD * nCr(N-1,i-1))%MOD) % MOD;
  }
  return (int)res;
 }
};