Count the Buildings

Computer Science Level 5

There are $N=100$ buildings arranged in a row.
Each has a distinct integer height ranging from $1$ to $N$ inclusive.
If you look from the first building, you can see 56 buildings;
if you look from the last building, you can see 2 buildings.

As an explicit example, suppose there is a configuration of 5 buildings with heights 1, 3, 2, 5, 4.
If you look from the first building, you can see 3 buildings (with heights 1, 3, 5) respectively.
If you look from the last building, you can see 2 buildings (with heights 4, 5) respectively.

Let $S$ be the number of possible configurations of buildings such that the above is true. What are the last three digits of $S$ ?

Assume that you can only see a building if all buildings in front of it are strictly lower than it.

Source : HangZhou DianZi University Online Judge Problem .

The answer is 968.

1 solution

David Hammond
Apr 30, 2019

from functools import lru_cache
import time
from scipy.special import comb, perm

# k-permutations of n
#  n!/(n - k)!
@lru_cache(maxsize=None)
def P(n, k):
  return perm(n, k, exact=True)

@lru_cache(maxsize=None)
def select_peak(peaks_remaining, less_than_last_peak, greater_than_last_peak):
  if (peaks_remaining == 1):
    return 1 if (less_than_last_peak == 0 and greater_than_last_peak == 1) else 0
  else:
    total = 0
    for i in range(1, greater_than_last_peak - peaks_remaining + 2):
      total += select_valley(peaks_remaining - 1, less_than_last_peak + i - 1, 
        greater_than_last_peak - i)
    return total

@lru_cache(maxsize=None)
def select_valley(peaks_remaining, less_than_last_peak, greater_than_last_peak):  
  total = 0
  for i in range(0, less_than_last_peak + 1):
    total += P(less_than_last_peak, i) * select_peak(peaks_remaining, 
      less_than_last_peak - i, greater_than_last_peak)
  return total

def building_configurations(left, right, N):
  # Iterate over all possible number of total buildings on the left. The number
  # of configurations resulting from each total number (i) is equal to the number
  # of ways of selecting i - 1 elements from N - 1 (element N always divides left 
  # and right) multiplied by the number of allowable ways of arranging left 
  # multiplied by the number of allowable ways of arranging right.
  total = 0
  for i in range(left, (N - right + 1) + 1):
    configurations = (comb((N - 1), (i - 1), exact=True) * 
      select_peak(left, 0, i) * 
      select_peak(right, 0, N - i + 1))
    total += configurations
  return total

if __name__ == "__main__":
  start = time.time()
  print("Answer:", building_configurations(56, 2, 100))
  print("Time: %.2fs" % (time.time() - start))

# Output
# Answer: 142659594651663280168474007320516110554197195392948025080760160338524951342467243698753464982052011968
# Time: 0.55s

Count the Buildings

Source : HangZhou DianZi University Online Judge Problem .

The answer is 968.

1 solution

0 pending reports