TopCoder problem "FairTournament" used in SRM 344 (Division I Level Three)



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 p1 in first place (ranking 1), participant p2 in second place (ranking 2), ..., participant pn 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-pi|<=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.

 

Definition

    
Class:FairTournament
Method:countPermutations
Parameters:int, int
Returns:String
Method signature:String countPermutations(int n, int k)
(be sure your method is public)
    
 

Constraints

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

Examples

0)
    
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.
1)
    
3
2
Returns: "6"
2)
    
10
3
Returns: "19708"
3)
    
100
1
Returns: "573147844013817084101"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7332

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10668&pm=7332

Writer:

Petr

Testers:

PabloGilberto , brett1479 , Yarin , Olexiy

Problem categories:

Dynamic Programming