TopCoder problem "NumJordanForms" used in TCO06 Qual 2/10/13 (Division I Level Three)



Problem Statement

    You will be given 2 int[]s charPoly and minPoly, each containing N positive integers. A Jordan form is determined by choosing, for each index i, a partition of charPoly[i] such that no component of the partition exceeds minPoly[i] and at least 1 component is equal to minPoly[i]. A partition of a value v is an ordered list of positive integers that sum to v. Two Jordan forms are equivalent if they have the same partition for each i. Return the number of distinct Jordan forms mod 179424673.
 

Definition

    
Class:NumJordanForms
Method:howMany
Parameters:int[], int[]
Returns:int
Method signature:int howMany(int[] charPoly, int[] minPoly)
(be sure your method is public)
    
 

Constraints

-charPoly will contain between 1 and 50 elements, inclusive.
-minPoly will contain the same number of elements as charPoly.
-Each element of charPoly will be between 1 and 4000, inclusive.
-Element i of minPoly will be between 1 and charPoly[i], inclusive.
 

Examples

0)
    
{5}
{1}
Returns: 1
Only one Jordan form is possible here.
1)
    
{5}
{3}
Returns: 2
There are 2 partitions of 5 that are possible here: (1,1,3) and (2,3).
2)
    
{1,2,3,4,5,6,7,8,9}
{1,2,3,3,3,3,3,3,3}
Returns: 840
3)
    
{4000,4000,4000,4000,4000}
{500,1000,1500,2000,2500}
Returns: 41788067

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9898&pm=6049

Writer:

AdminBrett

Testers:

PabloGilberto , lbackstrom , Olexiy

Problem categories:

Dynamic Programming