FairTournament

SRM 344 · 2007-03-28 · by Petr

SRM 344 · 2007-03-28 · by Petr · Dynamic Programming

Show categories

Class Name: FairTournament

Return Type: String

Method Name: countPermutations

Arg Types: (int, int)

Problem Statement

Consider a tournament with n participants, numbered 1 to n in decreasing order by strength. The outcome of the tournament is a ranking of all the participants: participant p₁ in first place (ranking 1), participant p₂ in second place (ranking 2), ..., participant p_n in last place (ranking n). It can be easily seen that p is a permutation.

An outcome of the tournament is called k-fair if every participant gets a ranking that differs from his number by at most k. In other words, p is a permutation where the following condition holds for all i: |i-p_i|<=k.

Given an int n and an int k, return the number of different possible k-fair outcomes for a n-player tournament. The return value must be a String with no extra leading zeroes.

Constraints

n will be between 1 and 100, inclusive.
k will be between 1 and 6, inclusive.

Examples

3
1
Returns: "3"

Rankings "1,2,3", "2,1,3" and "1,3,2" are 1-fair, while "2,3,1", "3,1,2" and "3,2,1" are not.

3
2
Returns: "6"

10
3
Returns: "19708"

100
1
Returns: "573147844013817084101"

1
1
Returns: "1"

Submissions are judged against all 29 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FairTournament with a public method string countPermutations(int n, int k) · 29 test cases · 2 s / 256 MB per case