TopCoder problem "AppleTrees" used in Member SRM 489 (Division I Level Three)



Problem Statement

    Rabbit Hanako likes apples. She decided to plant apple trees along a straight road.



The road has D candidate positions for planting apple trees. These positions are numbered 0 through D-1, from left to right. The distance between position x and position y is |x-y| meters (|x-y| denotes the absolute value of x-y). She wants to plant N apple trees numbered from 0 to N-1 in different positions. The trees may be planted in any order. The i-th tree won't grow if there are other trees which are closer than r[i] meters. In other words, if i and j are distinct, the distance between the i-th tree and the j-th tree must be at least max(r[i],r[j]) meters.



Return the number of ways to plant all apple trees modulo 1,000,000,007.
 

Definition

    
Class:AppleTrees
Method:theCount
Parameters:int, int[]
Returns:int
Method signature:int theCount(int D, int[] r)
(be sure your method is public)
    
 

Constraints

-D will be between 1 and 100,000, inclusive.
-r will contain between 1 and 40 elements, inclusive.
-Each element of r will be between 1 and 40, inclusive.
 

Examples

0)
    
10
{40}
Returns: 10
There are 10 candidate positions for the only tree.
1)
    
4
{1, 1, 1, 1}
Returns: 24
Trees must be planted in different positions, so the number of ways to plant all trees is 4! = 24.
2)
    
4
{1, 1, 2}
Returns: 4
The following 4 ways are possible:
  • Plant the 0th tree in position 0, the 1st tree in position 1, and the 2nd tree in position 3.
  • Plant the 0th tree in position 1, the 1st tree in position 0, and the 2nd tree in position 3.
  • Plant the 0th tree in position 2, the 1st tree in position 3, and the 2nd tree in position 0.
  • Plant the 0th tree in position 3, the 1st tree in position 2, and the 2nd tree in position 0.
3)
    
58
{5, 8}
Returns: 2550
4)
    
47
{4, 8, 9}
Returns: 28830
5)
    
100000
{21, 37, 23, 13, 32, 22, 9, 39}
Returns: 923016564

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14242&pm=11213

Writer:

rng_58

Testers:

liympanda , eleusive , ivan_metelsky , vexorian

Problem categories:

Dynamic Programming, Math