JOIN
Get Time

   Problem Statement  

 Problem Statement for Sortish

Problem Statement

    

Everyone likes some sequences more than others. Every person has their own function which tells them how good a sequence is. For example, for some people this function could simply be the count of negative numbers in the sequence.



Jezalb's most favorite sequences are ones that are sorted in increasing order. When he sees a sequence S, he immediately calculates the number of pairs of indexes i < j such that S[i] < S[j]. He calls this number the "sortedness" of S.



This morning Jezalb entered a classroom and saw a permutation of 1 through N on the blackboard. He quickly calculated its sortedness. He then left the classroom and forgot the permutation. He only remembered the sortedness he computed. You are given this value in a int sortedness.



Later that day Jezalb reentered the classroom and saw a sequence on the blackboard. The sequence was a permutation of 1 through N, but with some elements erased. You are given this sequence as a int[] seq with N elements. Some of the elements in seq may be 0, which indicates an erased number.



Jezalb thinks that the sequence seq may have been obtained by erasing some elements of the sequence he saw during his first visit to the classroom. He would like to restore the erased elements.



You are given the int sortedness and the int[] seq. Return the number of ways in which he can fill in the missing elements into seq in such a way that the sortedness of the obtained permutation will be exactly sortedness.

 

Definition

    
Class:Sortish
Method:ways
Parameters:int, int[]
Returns:long
Method signature:long ways(int sortedness, int[] seq)
(be sure your method is public)
    
 

Notes

-Pay attention to the unusual time limit.
 

Constraints

-sortedness will be between 0 and 1,000,000,000, inclusive.

-seq will contain between 1 and 2,000 elements, inclusive.

-Elements in seq will be between 0 and number of elements in seq, inclusive.

-Positive elements in seq will be distinct.

-Number of elements equal to 0 in seq will be between 0 and 14, inclusive.
 

Examples

0)
    
5
{4, 0, 0, 2, 0}
Returns: 2
There are six ways to fill in the missing elements. Out of those six permutations, only two have sortedness 5: {4, 1, 5, 2, 3} and {4, 3, 1, 2, 5}.
1)
    
4
{0, 0, 0, 0}
Returns: 5
All 5 possible ways are: {1, 3, 4, 2}, {1, 4, 2, 3}, {2, 1, 4, 3}, {2, 3, 1, 4}, {3, 1, 2, 4}.
2)
    
2
{1, 3, 2}
Returns: 1
There are no gaps and sortedness is indeed equal to 2.
3)
    
3
{0, 0, 2, 0, 0, 0}
Returns: 4
4)
    
87
{2,0}
Returns: 0
The only permutation that matches seq is {2, 1}. However, the sortedness of this sequence is 0, not 87.
5)
    
30
{0, 6, 3, 0, 0, 2, 10, 0, 0, 0}
Returns: 34
6)
    
100
{0, 13, 0, 0, 12, 0, 0, 0, 2, 0, 0, 10, 5, 0, 0, 0, 0, 0, 0, 7, 15, 16, 20}
Returns: 53447326

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 636 Round 1 - Division I, Level Three