Skyline Problem

Problems and Contests
#1

Hi, I tried hard to solve Skyline Problem that is the question as an application of Catalan Numbers, here Catalan Numbers USACO Guide, and I looked at the solution source code provided by USACO Guide but I wasn’t able to understand the recurrence formula. Why and how does it work, can you explain please? I got stuck here for a day now :frowning:

1 Like
#2

x-posted: [Editorial] Catalan numbers by brebenelmihnea · Pull Request #4501 · cpinitiative/usaco-guide · GitHub

1 Like
#3

Thank you Benq for your effort and taking your time! I asked this because I thought there was a meaningful state definition of recurrence relation in solution code that I didn’t notice but it seems author just calculates Catalan Numbers. Because there exists an O(n) implementation of Catalan Numbers, I expected a different logic behind the solution code being that way.

#4

The modulus is unusual. Also, the states in the solution do actually correspond to the number of permutations satisfying a certain property.

1 Like