Hi guys. I was upsolving OI problems, when I stumbled upon this:
Statement: There are $$$n$$$ soldiers standing in a line, whose heights are distinct. A dude can be seen from the left side if there are no other dude to the left of him that is taller than him, and the same goes for the right side. Given $$$n$$$, $$$p$$$, $$$q$$$ ($$$n \leq 2000$$$), count how many way to arrange these dudes such that there are exactly $$$p$$$ dudes that can be seen from the left side, and $$$q$$$ dudes that can be seen from the right side. TL = $$$1$$$ second on a judge that runs as fast as Codeforces.
My idea: First we solve the case $$$q = 1$$$. For the sake of simplicity, we will assume the heights of these soldiers as a permutations of integers from $$$1$$$ to $$$n$$$. We can use dp: $$$f[i][j][k] = $$$ number of way to assign soldiers for the first $$$i$$$ position, such that the tallest soldiers that we assigned has the height $$$j$$$, and you can see $$$k$$$ dudes from the left side. From there it's just simple dp. For the general case, the answer is simply $$$\sum_{t = 1}^n (f[t-1][t-1][p-1] * f[n-t][n-t][q - 1] * C_{n-1} ^ {i-1})$$$. Sadly, this runs in $$$O(n^3)$$$, since our dp table has $$$n^3$$$ states.
I've discussed this problem with another dude who ranked Master on Codeforces, and we are proud to say that we can not cook, so any help would be appreciated. Thanks!
Assume you have a way to arrange $$$n$$$ soldiers such that $$$p$$$ are seen from the left and $$$q$$$ are seen from the right, then in between the soldiers that are seen there may exists some soldiers that are overshadowed.
In each arrangements, we could arrange all soldiers along with the soldiers they overshadowed to one side, and they will still be equivalent.
Now the problem becomes count number of ways to arrange n soldiers, such that k soldiers can be seen from $$$1$$$ side, which could be done with a simple dp, $$$dp[i][j]$$$ is number of ways to arrange with $$$i$$$ tallest soldiers and $$$j$$$ soldiers are seen, calculate it by going through all $$$n$$$ values in decreasing order.
Now observe that the tallest soldier is always seen, and the tallest soldiers is seen from both side thus we can reduce the problem to the soldiers $$$[1, n - 1]$$$ and $$$p - 1$$$ soldiers on the left, $$$q - 1$$$ on the right.
Now the answer is $$$dp[n - 1][p + q - 2] * C(p + q - 2, q - 1)$$$, which means that each ordering for one side, we could choose $$$q - 1$$$ seen soldiers and move them to the right, thus making it a valid arrangement.
My man didn't just cook, he delivered !!!!!!