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 {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
StringTokenizer st = new StringTokenizer(br.readLine());
int t = Integer.parseInt(st.nextToken());
Solve solve = new Solve();
solve.init();
int[] s = new int[55];
for (int it = 0; it < t; it++) {
st = new StringTokenizer(br.readLine());
int sCount = Integer.parseInt(st.nextToken());
int n = 0;
int numErased = 0;
st = new StringTokenizer(br.readLine());
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("%lldn",(a[0][m][0]+P)%P);
}
return 0;
}