players arm-wrestlers sit in a row on a long bench. A bout is always between two neighbours on the bench; the loser leaves and the winner stays in their seat, so the row closes up. Bouts continue until one champion is left.
Who wins doesn't matter here, only the shape of the contest: which blocks of original seats were merged by each bout. Two contests have the same shape if every bout joins the same two blocks of seats, even if independent bouts happen in a different order. For example, with 4 players, "seats 1-2 and seats 3-4 wrestle, then the two winners" is one shape, no matter which of the first two bouts happened first.
Implement bench_shapes(players: int) -> int: the number of different shapes.
bench_shapes(1) # 1 nobody wrestles
bench_shapes(3) # 2 (1 vs 2) then vs 3, or 1 vs (2 vs 3)
bench_shapes(4) # 5
Constraints: 1 <= players <= 600. Return the exact count (Python ints don't overflow). Trying every possible bout recursively without memoisation is exponential; the tests ask for players = 600.
Show hint
Look at the final bout: it joins seats 1..i with seats i+1..players for some split i, and each side had its own independent contest. So shapes(n) = sum over i of shapes(i) * shapes(n - i): the Catalan recurrence, shifted by one.