Dynamic programming., Data Structure & Algorithms

Assignment Help:
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.

Related Discussions:- Dynamic programming.

BINARY SEARCH, GIVE TRACE OF BINARY SEARCH ALGORITHM BY USING A SUITABLE EX...

GIVE TRACE OF BINARY SEARCH ALGORITHM BY USING A SUITABLE EXAMPLE.

Algorithms, write short note on algorithms

write short note on algorithms

What is complexity, Complexity is the rate at which the needed storage or c...

Complexity is the rate at which the needed storage or consumed time rise as a function of the problem size. The absolute growth based on the machine utilized to execute the program

Maximum degree of any vertex in a simple graph, The maximum degree of any v...

The maximum degree of any vertex in a simple graph with n vertices is (n-1) is the maximum degree of the vertex in a simple graph.

Define strictly binary tree, Define Strictly Binary Tree Strictly Bina...

Define Strictly Binary Tree Strictly Binary Tree: - If each non leaf node in binary tree has non empty left and right sub-trees , then the tree is known as a strictly binary t

Addressing modes, Compare zero-address, one-address, two-address, and three...

Compare zero-address, one-address, two-address, and three-address machines by writing programs to compute: Y = (A – B X C) / (D + E X F) for each of the four machines. The inst

Present the algorithm of binary search. , B i n a ry Search Alg...

B i n a ry Search Algorithm is given as follows 1. if (low > high) 2.     return (-1) 3. mid = (low +high)/2; 4. if ( X = = a [mid]) 5.      return (mid); 6.

Merge sort , What is the best-case number of comparisons performed by merge...

What is the best-case number of comparisons performed by mergesort on an input sequence of 2 k distinct numbers?

State in brief about assertion, State  in brief about assertion Asser...

State  in brief about assertion Assertion: A statement which should be true at a designated point in a program.

Test whether a binary tree is a binary search tree, Q. Write down an algori...

Q. Write down an algorithm to test whether a Binary Tree is a Binary Search Tree.              A n s . The algorithm to check whether a Binary tree is as Binary Search

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd