Dynamic programming., Data Structure & Algorithms

Count Scorecards(30 points)

In a tournament, N players play against each other exactly once. Each game results in either of the player winning. There are no ties. You have given a scorecard containing the scores of each player at the end of the tournament. The score of a player is the total number of games the player won in the tournament. However, the scores of some players might have been erased from the scorecard. How many possible scorecards are consistent with the input scorecard?

Input:
The first line contains the number of cases T. T cases follow. Each case contains the number N on the first line followed by N numbers on the second line. The ith number denotes s_i, the score of the ith player. If the score of the ith player has been erased, it is represented by -1.

Output:
Output T lines, containing the answer for each case. Output each result modulo 1000000007.

Constraints:
1 <= T <= 20
1 <= N <= 40
-1 <= s_i < N

Sample Input:
5
3
-1 -1 2
3
-1 -1 -1
4
0 1 2 3
2
1 1
4
-1 -1 -1 2

Sample Output:
2
7
1
0
12


Explanation:
For the first case, there are 2 scorecards possible: {0,1,2} or {1,0,2}.
For the second case, the valid scorecards are {1,1,1}, {0,1,2}, {0,2,1}, {1,0,2}, {1,2,0}, {2,0,1}, {2,1,0}.
For the third case, the only valid scorecard is {0,1,2,3}.
For the fourth case, there is no valid scorecard. It is not possible for both players to have score 1.
Posted Date: 6/30/2012 6:58:09 PM | Location : United States







Related Discussions:- Dynamic programming., Assignment Help, Ask Question on Dynamic programming., Get Answer, Expert's Help, Dynamic programming. Discussions

Write discussion on Dynamic programming.
Your posts are moderated
Related Questions
Write a program to simulate searching over a hashed file, with different assumptions for the sizeof file pages.Write a program to perform equality search operations on the hashed f

how to write a code for for a company , for calculate the salary pay

I=PR/12 numbers of years : Interest Rate up to 1 years : 5.50 Up to 5 years : 6.50 More than 5 year : 6.75 please design an algorithm based on the above information

Explain Division Method Division Method: - In this method, key K to be mapped into single of the m states in the hash table is divided by m and the remainder of this division

I need a recursive algorithm to implement the FIRST function to any grammar

Q. Define the terms data type and abstract data type. Comment upon the significance of both these.   Ans: We determine the total amount of memory to reserve by determining

human resource management project work in c++

Using Assertions When writing code, programmer must state pre- and subtle post conditions for public operations, state class invariants and insert unreachable code assertions a

When there is requirement to access records sequentially by some key value and also to access records directly by the similar key value, the collection of records may be organized

need c++ algorithmic software program to derive one numerical outcome from 10 levels of variables with 135 combinations cross computed