Bar Arrangement
Time limit1sMemory limit256 MB
Count permutations of 1 to n with exactly l left-to-right maxima and r right-to-left maxima for each test case.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Combinatorics
- Solved
- No attempts yet
Problem
There are bars of heights placed in a row. When you look at the bars from the left or from the right, a taller bar hides any shorter bar behind it. Consider the two arrangements of bars shown below.

In both arrangements, exactly bar is visible from the left and exactly bars are visible from the right.
Given the number of bars , the number of bars visible from the left, and the number of bars visible from the right, write a program that counts how many arrangements produce this result.
Input
The first line contains the number of test cases . Each test case consists of a single line with three integers , , and . ()
Output
For each test case, print the number of arrangements corresponding to the given , , and , one per line.