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.

Graph traversal, 1) Which graph traversal uses a queue to hold vertices whi...

1) Which graph traversal uses a queue to hold vertices which are to be processed next ? 2) Which of the graph traversal is recursive by nature? 3) For a dense graph, Prim's a

Write functions for both addition and subtraction, You will write functions...

You will write functions for both addition and subtraction of two numbers encoded in your data structure. These functions should not be hard to write. Remember how you add and subt

Binary tree, A binary tree is a tree data structures in which each node hav...

A binary tree is a tree data structures in which each node have at most two child nodes, generally distinguished as "right" and "left". Nodes with children are called parent nodes,

Er diagram, Ask queConsider the following functional dependencies: Applican...

Ask queConsider the following functional dependencies: Applicant_ID -> Applicant_Name Applicant_ID -> Applicant_Address Position_ID -> Positoin_Title Position_ID -> Date_Position_O

Queue be represented by circular linked list, Q. Can a Queue be represented...

Q. Can a Queue be represented by circular linked list with only one pointer pointing to the tail of the queue? Substantiate your answer using an example. A n s . Yes a

The various ways in which lc code can be accessed, Problem Your LC code...

Problem Your LC code is stored in a memory location as shown and the variable name is LC                  LC Memory address       Content(LC code)

Stack and array, how to implement multiple stack using single dimension arr...

how to implement multiple stack using single dimension array in c

Program, circular queue using c

circular queue using c

Program on radix sort., Write a program that uses the radix sort to sort 10...

Write a program that uses the radix sort to sort 1000 random digits. Print the data before and after the sort. Each sort bucket should be a linked list. At the end of the sort, the

Complexity, Complexity : How do the resource needs of a program or algorith...

Complexity : How do the resource needs of a program or algorithm scale (the growth of resource requirements as a function of input). In other words, what happens with the performan

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