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.

Multiple stacks in a single array, implement multiple stacks in an array an...

implement multiple stacks in an array and write different algorithms to perform operations on it

Stack making use of the linked list, Q. Implement a stack making use of the...

Q. Implement a stack making use of the linked list. Show the PUSH and POP operations both. A n s . Stack implemantation using linked list # include # include

Non-recursive implementation of preorder traversal, For preorder traversal,...

For preorder traversal, in the worst case, the stack will rise to size n/2, where n refer to number of nodes in the tree. Another method of traversing binary tree non-recursively t

Explain the abstract data type assertions, Explain the Abstract data type a...

Explain the Abstract data type assertions Generally, ADT assertions translate into assertions about the data types which implement ADTs, which helps insure that our ADT impleme

Sorting algorithm is best if the list is already sorted, Which sorting algo...

Which sorting algorithm is best if the list is already sorted? Why? Insertion sort as there is no movement of data if the list is already sorted and complexity is of the order

Matrices multiplication, Write an algorithm for multiplication of two spars...

Write an algorithm for multiplication of two sparse matrices using Linked Lists.

Explain the halting problem, Explain the halting problem Given a comput...

Explain the halting problem Given a computer program and an input to it, verify whether the program will halt on that input or continue working indefinitely on it.

Process of in-order traversal, In-order Traversal  This process when ex...

In-order Traversal  This process when executed iteratively also needs a stack and a Boolean to prevent the implementation from traversing any portion of a tree twice. The gener

What is quick sort, What is quick sort?   Answer Quick sort is on...

What is quick sort?   Answer Quick sort is one of the fastest sorting algorithm used for sorting a list. A pivot point is chosen. Remaining elements are divided or portio

Bst created in pre- order, Q. Make a BST for the given sequence of numbe...

Q. Make a BST for the given sequence of numbers. 45,32,90,34,68,72,15,24,30,66,11,50,10 Traverse the BST formed in  Pre- order, Inorder and Postorder.

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