HackerRank Count Scorecards Problem Solution

HackerRank Count Scorecards Problem Solution

Yashwant Parihar,

In this post, we will solve 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?
Input Format
The first line contains a single integer t denoting the number of test cases, t test cases
follow.
The first line of each test case contains a single integer n. The second line contains n space- separated integers 81, 82, …, S. Si denotes the score of the ith player. If the score of the ith player has been erased, it is represented by -1.

Output Format

For each test case, output a single line containing the answer for that test case modulo 10 power 9 + 7.

Sample Input 0

5
3
-1 -1 2
3
-1 -1 -1
4
0 1 2 3
2
1 1
4
-1 -1 -1 2

Sample Output 0

2
7
1
0
12

Explanation 0

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 of 1.
For the fifth case, 6-variations of {(3,1,0)[2]}, and 3 variations each of {(2,2,0)[2]} and {(2,1,1)[2]}.

HackerRank Count Scorecards Problem Solution
HackerRank Count Scorecards Problem Solution

Count Scorecards C Solution

/* 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;
}

Count Scorecards C++ Solution

#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;
}

Count Scorecards C Sharp Solution

using System;
using System.IO;

namespace Problem51Nod
{
    class Program
    {
        static long Mod = 1000000007, Mul;
        static int Total, N;
        static long[] Inv = new long[50], Acc;
        static long[, ,] Dp;

        static long Solve(int[] nums)
        {
            int n = nums.Length - 1;
            N = n; Total = n * (n - 1) / 2;

            int remain = 0, total = 0;
            Acc = new long[n + 1];

            for (int i = nums.Length - 2; i >= 0; i--)
            {
                remain += nums[i];
                total += nums[i] * i;
                Acc[i] = Acc[i + 1] + nums[i] * i;

                if (remain * (N - 1) - total < remain * (remain - 1) / 2)
                    return 0;
            }

            if (total > Total) return 0;

            remain = N - remain;
            Mul = 1;
            for (int i = 2; i <= remain; i++)
                Mul = Mul * i % Mod;

            Dp = new long[n + 1, remain + 1, Total + 1];

            for (int i = 0; i <= n; i++)
                for(int j = 0; j <= remain; j++)
                    for(int k = 0; k <= Total; k++)
                        Dp[i,j,k] = -1;

            long result = Dfs(0, remain, 0, nums, 0);
            return result;
        }

        static long Dfs(int min, int remain, int count, int[] nums, int total)
        {
            if ((N - count) * min > Total - total || total + Acc[min] > Total) return 0;
            if (remain == 0) return total + Acc[min] == Total ? Mul : 0;
            if (min == N) return 0;

            if (Dp[min, remain, total] == -1)
            {
                long result = 0;

                for (int i = 0; i <= remain; i++)
                {
                    int current = i + nums[min];
                    int preTotal = total + current * min;
                    int preCount = count + current;

                    if (preTotal < preCount * (preCount - 1) >> 1)
                        continue;

                    int sufTotal = Total - preTotal;
                    int sufCount = N - preCount;

                    if (sufTotal < sufCount * (sufCount - 1) >> 1)
                        continue;

                    result += Inv[i] * Dfs(min + 1, remain - i, preCount, nums, preTotal) % Mod;
                }

                Dp[min, remain, total] = result % Mod;
            }

            return Dp[min, remain, total];
        }

        public static long ModInv(long n, long mod)
        {
            long x2 = 0, x3 = mod, y2 = 1, y3 = n, q, t2, t3;

            while (true)
            {
                if (y3 == 0) return 0;
                if (y3 == 1)
                {
                    if (y2 < 0) y2 += mod;
                    return y2;
                }
                q = x3 / y3;
                t2 = x2 - q * y2;
                t3 = x3 - q * y3;
                x2 = y2; x3 = y3;
                y2 = t2; y3 = t3;
            }
        }

        static void Main(string[] args)
        {
            Inv[0] = 1;

            for (int i = 1; i < Inv.Length; i++)
                Inv[i] = Inv[i - 1] * ModInv(i, Mod) % Mod;

            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
            int t = Convert.ToInt32(sr.ReadLine());

            for (int l = 0; l < t; l++)
            {
                int n = Convert.ToInt32(sr.ReadLine());
                string[] content = sr.ReadLine().Split(' ');
                int[] nums = new int[n + 1];
                bool flag = false;

                for (int i = 0; i < n; i++)
                {
                    int index = Convert.ToInt32(content[i]);

                    if (index >= n)
                        flag = true;

                    if (index != -1 && index < n)
                        nums[index]++;
                }

                long result = flag ? 0 : Solve(nums);
                sw.WriteLine(result);
            }

            sw.Flush();
        }
    }
}

Count Scorecards Java Solution

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();
  }
}

Count Scorecards Python Solution

# Enter your code here. Read input from STDIN.
tests = int(raw_input())

mod = 10**9+7

def c2(n):
    return n * (n - 1) / 2

for test in xrange(tests):
    n = int(raw_input())
    xs = map(int, raw_input().split())
    m = xs.count(-1)
    xs = sorted([x for x in xs if x >= 0])
    mem = dict()
    c = [[1]]
    for i in xrange(n):
        c.append([u + v for (u, v) in zip(c[i] + [0], [0] + c[i])])
    def din(i = 0, j = 0, k = 0, sum = 0):
        if i == n:
            return 1 if j == len(xs) and sum == c2(n) else 0 
        if sum < c2(i) or sum + k * (n - i) > c2(n):
            return 0
        if j < len(xs) and k == xs[j]:
            return din(i + 1, j + 1, k, sum + k)
        if (i, j, k, sum) not in mem:
            r = 0
            for t in xrange(min(n - i, m - (i - j)) + 1):
                r += c[m - (i - j)][t] * din(i + t, j, k + 1, sum + k * t)
            r %= mod
            mem[(i, j, k, sum)] = r
            return r
        return mem[(i, j, k, sum)]
    print(din())
c C# C++ HackerRank Solutions java javascript python