# HackerRank Count Scorecards problem solution

In this HackerRank Count Scorecards problem solution In a tournament, N players play against each other exactly once. Each game results in exactly one player winning. There are no ties. You have been 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?

## Problem solution in Java.

```import java.io.*;
import java.util.*;

public class Solution {

static final int MOD = 1_000_000_007;

static class Solve {
int[] exceed = new int[55];
int numErased;
int sCount;
int scores;
int dp[][][] = new int[42][42][42 * 41];
int[][][] calced = new int[42][42][42 * 41];
int calcedn;
int[][] c = new int[55][55];

void init() {
for (int i = 0; i < 50; ++i) {
c[i][0] = 1;
for (int j = 1; j <= i; ++j) {
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
}
}
}

int calc(int k, int last, int sum) {
if (k == numErased) {
return (scores + sum == sCount * (sCount - 1) / 2) ? 1 : 0;
}

if (last >= sCount) {
return 0;
}

int ans = dp[k][last][sum];

if (calced[k][last][sum] == calcedn) {
return ans;
}
calced[k][last][sum] = calcedn;

ans = calc(k, last + 1, sum);
int sumi = sum;
for (int i = 1; k + i <= numErased; i++) {
sumi += last;
if (sumi + exceed[k + i] < (k + i) * (k + i - 1) / 2) {
break;
}

ans = (int) ((ans + 1L * c[numErased - k][i] * calc(k + i, last + 1, sumi)) % MOD);
}
dp[k][last][sum] = ans;
return ans;
}

int countScorecards(int[] s, int n, int sCount, int numErased) {
this.sCount = sCount;
this.numErased = numErased;

Arrays.sort(s, 0, n);

int sum = 0;
for (int i = 0; i < n; ++i) {
sum += s[i];
if (i * (i + 1) / 2 > sum) {
return 0;
}
}
scores = sum;

for (int i = 1; i <= numErased; ++i) {
sum = 0;
exceed[i] = 0;
for (int j = 0; j < n; ++j) {
sum += s[j] - (i + j);
exceed[i] = Math.min(exceed[i], sum);
}
}
calcedn++;
return calc(0, 0, 0);
}

}

public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

int t = Integer.parseInt(st.nextToken());

Solve solve = new Solve();
solve.init();

int[] s = new int[55];

for (int it = 0; it < t; it++) {
int sCount = Integer.parseInt(st.nextToken());
int n = 0;
int numErased = 0;

for (int j = 0; j < sCount; j++) {
int item = Integer.parseInt(st.nextToken());
if (item == -1) {
numErased++;
} else {
s[n++] = item;
}
}

int result = solve.countScorecards(s, n, sCount, numErased);

bw.write(String.valueOf(result));
bw.newLine();
}

bw.close();
br.close();
}
}```

## Problem solution in C++.

```#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <cassert>
#include <ctime>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
using namespace std;

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define vi vector<int>
#define all(v) (v).begin(), (v).end()
#define forit(it,v) for (__typeof(v.begin()) it = v.begin(); it != v.end(); ++it)
#define f0(a) memset(a, 0, sizeof(a))
#define ll long long

const int mod = 1000000007;
int a[55], exceed[55];
int C[55][55];
int n, m, N, scores;

int calced[42][42][42*41], calcedn;
int dp[42][42][42*41];

int Calc(int k, int last, int sum) {

if (k == m) return scores + sum == N * (N - 1) / 2;

if (last >= N) return 0;

int &ans = dp[k][last][sum];

if (calced[k][last][sum] == calcedn) return ans;
calced[k][last][sum] = calcedn;

ans = Calc(k, last + 1, sum);
for (int i = 1; k + i <= m; ++i) {
sum += last;
if (sum + exceed[k + i] < (k + i) * (k + i - 1) / 2) break;

ans = (ans + 1ll * C[m - k][i] * Calc(k + i, last + 1, sum)) % mod;
}
return ans;
}
void Solve() {
n = m = 0;
scanf("%d", &N);
for (int i = 0; i < N; ++i)  {
int x;
scanf("%d", &x);
if (x == -1) ++m;
else a[n++] = x;
}
sort(a, a + n);
int     sum = 0;
for (int i = 0; i < n; ++i) {
sum += a[i];
if (i * (i + 1) / 2 > sum) {
puts("0");
return;
}
}
scores = sum;

for (int i = 1; i <= m; ++i) {
int sum = 0;
exceed[i] = 0;
for (int j = 0; j < n; ++j) {
sum += a[j] - (i + j);
exceed[i] = min(exceed[i], sum);
}
}
++calcedn;
cout << Calc(0, 0, 0) << endl;

}
int main() {
for (int i = 0; i < 50; ++i) {
C[i][0] = 1;
for (int j = 1; j <= i; ++j) {
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}
}
int tests;
scanf("%d", &tests);
while (tests--)
Solve();
return 0;
}```

## Problem solution in C.

```/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <stdio.h>
#include <stdlib.h>

#define P 1000000007
#define N 450

long long bin[50][50],jj,kk,h,ll,ii,t,a[50][50][1010],i,j,k,l,m,n,c[100],b[100];

int com(const void * xx, const void *yy){
if(*(long long *)xx < *(long long*)yy) return 1;
return -1;
}

int main(){

for(i = 0; i < 50; i++) bin[i][0] = bin[i][i] = 1;
for(i = 1; i < 50; i++)
for(j = 1; j < i; j++) bin[i][j] = (bin[i - 1][j - 1]+ bin[i - 1][j])%P;

scanf("%lld",&t);
while(t--){
scanf("%lld",&n);
for(i = 0;i < n; i++) scanf("%lld",&c[i]);

qsort(c, n, sizeof(c[0]), com);

for(i = 0;i <= n; i++)
b[i]=0;

m = 0;
for(i = 0; i < n; i++)
if(c[i] != -1)
b[c[i]]++;
else m++;

for(i = 0; i <= n; i++)
for(j = 0; j <= n; j++)
for(k = 0; k <= N; k++)
a[i][j][k]=0;

a[n][0][0] = 1;
l = 0;

for(i = n - 1;i >= 0; i--) {
for(j = 0; j <= m; j++)
{
h = 0;
ll = l;
for(ii = 0; ii < b[i]; ii++){
h += (n - ll - j - 1) - i;
ll++;
}

for(k = 0; k <= N; k++)
if(k + h >= 0)
a[i][j][k + h] = (a[i][j][k + h] + a[i + 1][j][k]) % P;
}

for(j = m; j >= 0; j--)
for(k = 0; k < N; k++){
h = k;
for(jj = 1; jj <= j && h >= 0; jj++){
h -= (n- l - b[i] - (j - jj)-1) - i;

if(h<0) break;

a[i][j][k] = (a[i][j][k] + bin[m - j + jj][jj] * a[i][j - jj][h]) % P;

}
}

l += b[i];
}

printf("%lld\n",(a[0][m][0]+P)%P);

}

return 0;
}```