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

1 Like

1 Like

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.

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

1 Like