Table of Contents
Count Scorecards – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ replace HackerRank Solution
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include<iostream>
#include<vector>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std ;
#define MAXN 42
#define MOD 1000000007
int n ;
vector<int> G ;
int check(vector<int> gg)
{
sort(gg.begin(),gg.end()) ;
int sum = 0 ;
for(int i = 0;i < n;i++)
{
sum += gg[i] ;
if(sum < i * (i + 1) / 2) return 0 ;
}
return 1 ;
}
int solve1(int k,int sum)
{
if(sum > n * (n - 1) / 2) return 0 ;
if(k == n) return sum == n * (n - 1) / 2 && check(G) ? 1 : 0 ;
if(G[k] != -1) return solve1(k + 1,sum + G[k]) ;
int ret = 0 ;
for(int i = 0;i < n;i++)
{
G[k] = i ;
ret += solve1(k + 1,sum + i) ;
G[k] = -1 ;
}
return ret ;
}
int solve1(vector<int> g)
{
G = g ;
n = G.size() ;
int ret = solve1(0,0) ;
return ret ;
}
int fac[MAXN],inv[MAXN] ;
int pow(int a,int b)
{
if(b == 0) return 1 ;
int ret = pow(a,b / 2) ;
ret = 1LL * ret * ret % MOD ;
if(b & 1) ret = 1LL * ret * a % MOD ;
return ret ;
}
int occ[MAXN],big[MAXN] ;
int memo[MAXN][MAXN][MAXN * MAXN] ;
int solve2(int k,int last,int sum)
{
if(last == n) return 0 ;
if(sum > n * (n - 1) / 2) return 0 ;
if(k == n) return big[last + 1] == 0 && sum == n * (n - 1) / 2 ? 1 : 0 ;
if(memo[k][last + 1][sum] != -1) return memo[k][last + 1][sum] ;
int occr = occ[last + 1] ;
int ret = 0,added = 0 ;
for(int i = 0;k + i <= n;i++)
{
if(sum + added < (k + i) * (k + i - 1) / 2) break ;
if(i >= occr) ret += 1LL * inv[i - occr] * solve2(k + i,last + 1,sum + added) % MOD ;
if(ret >= MOD) ret -= MOD ;
added += last + 1 ;
}
return memo[k][last + 1][sum] = ret ;
}
int solve2(vector<int> g)
{
fac[0] = inv[0] = 1 ;
for(int i = 1;i < MAXN;i++)
{
fac[i] = 1LL * i * fac[i - 1] % MOD ;
inv[i] = pow(fac[i],MOD - 2) ;
}
n = g.size() ;
int start = 0 ;
memset(occ,0,sizeof occ) ;
memset(big,0,sizeof big) ;
for(int i = 0;i < g.size();i++) if(g[i] != -1) occ[g[i]]++,start++ ;
for(int i = 0;i < n;i++)
for(int j = i;j < n;j++)
big[i] += occ[j] ;
memset(memo,255,sizeof memo) ;
int ret = solve2(0,-1,0) ;
ret = 1LL * ret * fac[n - start] % MOD ;
return ret ;
}
vector<int> gen()
{
int n = rand() % 10 + 1 ;
vector<int> ret ;
for(int i = 0;i < n;i++)
{
if(rand() % 2 == 0) ret.push_back(-1) ;
else ret.push_back(rand() % n) ;
}
return ret ;
}
void test()
{
for(int t = 1;t < 100;t++)
{
vector<int> g = gen() ;
int ret1 = solve1(g) ;
int ret2 = solve2(g) ;
cout << ret1 << " " << ret2 << endl ;
if(ret1 != ret2)
{
cout << "failed on: " << t << endl ;
cout << g.size() << " : " ;
for(int i = 0;i < g.size();i++) cout << g[i] << " " ; cout << endl ;
while(1) ;
}
}
}
void generate()
{
char in[] = "in .txt" ;
for(int test = 0;test < 10;test++)
{
in[2] = test + '0' ;
FILE * fout = fopen(in,"w") ;
int runs = 20 ;
fprintf(fout,"%d\n",runs) ;
for(int t = 0;t < runs;t++)
{
if(rand() % 3 != 0) n = rand() % 40 + 1 ;
else n = 40 - rand() % 10 ;
int per = 70 ;
vector<int> g ;
for(int i = 0;i < n;i++)
{
if(rand() % 100 < per) g.push_back(-1) ;
else g.push_back(rand() % n) ;
}
fprintf(fout,"%d\n",n) ;
for(int i = 0;i < n;i++)
{
if(i) fprintf(fout," ") ;
fprintf(fout,"%d",g[i]) ;
}
fprintf(fout,"\n") ;
}
}
}
int main()
{
// srand(time(NULL)) ;
// generate() ; return 0 ;
// test() ; return 0 ;
int runs ;
cin >> runs ;
while(runs--)
{
int n ;
vector<int> g ;
cin >> n ;
for(int i = 0;i < n;i++)
{
int k ;
cin >> k ;
g.push_back(k) ;
}
int ret = solve2(g) ;
printf("%d\n",ret) ;
}
return 0 ;
}
Java rep HackerRank Solution
import java.io.*;
import java.util.*;
public class Solution {
// leave empty to read from stdin/stdout
private static final String TASK_NAME_FOR_IO = "";
// file names
private static final String FILE_IN = TASK_NAME_FOR_IO + ".in";
private static final String FILE_OUT = TASK_NAME_FOR_IO + ".out";
BufferedReader in;
PrintWriter out;
StringTokenizer tokenizer = new StringTokenizer("");
public static void main(String[] args) {
new Solution().run();
}
class State {
int[] a;
State(int[] a) {
this.a = a.clone();
Arrays.sort(this.a);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
State state = (State) o;
if (!Arrays.equals(a, state.a)) return false;
return true;
}
@Override
public int hashCode() {
return a != null ? Arrays.hashCode(a) : 0;
}
@SuppressWarnings({"ForLoopReplaceableByForEach"})
public int[] contains(int[] fixed) {
int rPos = 0;
int[] remaining = new int[a.length];
int fPos = 0;
for (int i = 0; i < a.length; i++)
if (fPos < fixed.length && a[i] == fixed[fPos]) {
fPos++;
} else {
remaining[rPos++] = a[i];
}
if (fPos < fixed.length) {
return null;
}
int[] result = new int[rPos];
System.arraycopy(remaining, 0, result, 0, rPos);
return result;
}
@Override
public String toString() {
StringBuilder result = new StringBuilder();
for (int v : a) {
if (result.length() > 0) {
result.append(' ');
}
result.append(Integer.toString(v));
}
return result.toString();
}
}
static final int MOD = 1000000007;
int n;
// http://mathworld.wolfram.com/ScoreSequence.html
private void solve() throws IOException {
// stress();
// timing();
int tc = nextInt();
for (int tcIdx = 0; tcIdx < tc; tcIdx++) {
n = nextInt();
List<Integer> fixedList = new ArrayList<Integer>();
for (int i = 0; i < n; i++) {
int k = nextInt();
if (k >= 0) {
fixedList.add(k);
}
}
int[] fixed = new int[fixedList.size()];
for (int i = 0; i < fixedList.size(); i++) {
fixed[i] = fixedList.get(i);
}
Arrays.sort(fixed);
out.println(solveFast(fixed));
// out.println(solveFast(fixed) + " - " + solveNaive(fixed));
}
}
private void stress() {
Random r = new Random(123456789L);
int tcNum = 100000;
for (int tcIdx = 0; tcIdx < tcNum; tcIdx++) {
n = 1 + r.nextInt(14);
System.out.print("Stress #" + tcIdx + ": n = " + n);
int len = r.nextInt(n + 1);
int[] fixed = new int[len];
for (int i = 0; i < len; i++) {
fixed[i] = r.nextInt(n);
}
Arrays.sort(fixed);
System.out.println(", answers: " + solveFast(fixed) + " vs. " + solveNaive(fixed));
}
}
private void timing() {
Random r = new Random(123456789L);
int tcNum = 20;
for (int tcIdx = 0; tcIdx < tcNum; tcIdx++) {
n = 40;
System.out.print("Timing #" + tcIdx + ": n = " + n);
int len = 0;
int[] fixed = new int[len];
for (int i = 0; i < len; i++) {
fixed[i] = r.nextInt(n);
}
Arrays.sort(fixed);
System.out.println(", answers: " + solveFast(fixed));
}
}
static final int MAXM = 100;
static long[][] CNK;
static {
CNK = new long[MAXM][MAXM];
for (int n = 0; n < MAXM; n++) {
CNK[n][0] = 1;
CNK[n][n] = 1;
for (int k = 1; k < n; ++k) {
CNK[n][k] = CNK[n - 1][k - 1] + CNK[n - 1][k];
CNK[n][k] %= MOD;
}
}
}
private int solveFast(int[] fixed) {
// d[len][fLen][min][sumRem]:
// we processed 'len' symbols so far
// out of them 'fLen' were taken from string 'fixed' -- we can actually calculate this one dynamically
// last used group of elements had value les than 'min'
// total sum remaining is equal to 'sum'
int nSum = (n * (n - 1)) / 2;
int[][][] d = new int[n + 1][n + 1][nSum + 1];
d[0][0][nSum] = 1;
for (int len = 0; len < n; len++)
for (int min = 0; min < n; min++) {
int fLen = 0;
while (fLen < fixed.length && fixed[fLen] < min) {
fLen++;
}
int fCnt = 0;
while (fLen + fCnt < fixed.length && fixed[fLen + fCnt] == fixed[fLen]) {
fCnt++;
}
for (int sumRem = 0; sumRem <= nSum; sumRem++)
if (d[len][min][sumRem] > 0) {
// we are definitely taking >= "min"
int lo = min;
// but we can't really take more than the next element of 'fixed'
int hi = fLen < fixed.length ? fixed[fLen] : n - 1;
// let's iterate over the element that we will put
for (int put = lo; put <= hi; put++) {
// what sum do we currently have
int sumBase = nSum - sumRem;
// determine minimum count, by presence in fixed array
int fCntMin = 0;
if (fLen < fixed.length && put == fixed[fLen]) {
fCntMin = fCnt;
}
int cnt = 1;
int sumCur = 0;
while (len + cnt <= n) {
// place the element, increase the sum
sumCur += put;
// but there is a lower limit on the sum, based on the position
int sumMin = ( (len + cnt - 1) * (len + cnt)) / 2;
// if criteria is not met, then there is no reason to continue
if (sumBase + sumCur < sumMin) {
break;
}
// if we took too much, then there is no reason to continue either
if (sumRem - sumCur - (n - (len + cnt)) * put < 0) {
break;
}
// start updating?
if (cnt >= fCntMin) {
// already placed:
// * len characters
//
// we are placing additionally:
// * fCntMin is the number of elements we are taking from 'fixed'
// * (cnt - fCntMin) is the number of wildcard elements we are adding
//
// so:
// * (len + fCntMin) will be occupied by previous characters + fixed characters
// * n - (len + fCntMin) is the remaining space (wildcards & non-wildcards)
// * n - (len + fCntMin) - (fixed.length - (fLen + fCntMin)) is the remaining space for wildcards
int wildcardPlaces = n - (len + fCntMin) - (fixed.length - (fLen + fCntMin));
int wildcardChars = cnt - fCntMin;
long addon = CNK[wildcardPlaces][wildcardChars] * d[len][min][sumRem];
d[len + cnt][put + 1][sumRem - sumCur] += addon % MOD;
if (d[len + cnt][put + 1][sumRem - sumCur] >= MOD) {
d[len + cnt][put + 1][sumRem - sumCur] -= MOD;
}
}
cnt++;
}
}
}
}
int result = 0;
int lo = fixed.length > 0 ? fixed[fixed.length - 1] + 1 : 0;
for (int min = lo; min <= n; min++) {
result += d[n][min][0];
if (result >= MOD) {
result -= MOD;
}
}
return result;
}
private int solveNaive(int[] fixed) {
buf = new int[n];
states = new HashSet<State>();
rec(0, 0, 0);
int result = 0;
for (State state : states) {
int[] remaining = state.contains(fixed);
if (remaining != null) {
long fLen = fact(remaining.length);
int[] cnt = new int[n];
for (int v : remaining) {
cnt[v]++;
}
for (int v : cnt)
if (v > 1) {
fLen /= fact(v);
}
result += fLen % MOD;
result %= MOD;
// System.out.println(state.toString() + ": " + fLen);
}
}
// System.out.println("***");
return result;
}
private long fact(int k) {
long result = 1;
for (int i = 2; i <= k; i++) {
result *= i;
}
return result;
}
Set<State> states;
int[] buf;
@SuppressWarnings({"UnusedDeclaration"})
private void printAll() {
for (n = 1; n <= 20; n++) {
System.out.println("n = " + n + ":");
buf = new int[n];
states = new HashSet<State>();
rec(0, 0, 0);
/*
for (State s : states) {
System.out.print(" ");
for (int v : s.a) {
System.out.print(v + " ");
}
System.out.println();
}
*/
System.out.println(" cnt = " + states.size());
}
}
private void rec(int k, int min, int sum) {
if (k >= n) {
int sumTarget = (k * (k - 1)) / 2;
if (sum == sumTarget) {
states.add(new State(buf));
}
return;
}
int sumMin = (k * (k + 1)) / 2;
for (int v = min; v < n; v++)
if (sum + v >= sumMin) {
buf[k] = v;
rec(k + 1, v, sum + v);
}
}
public void run() {
long timeStart = System.currentTimeMillis();
boolean fileIO = TASK_NAME_FOR_IO.length() > 0;
try {
if (fileIO) {
in = new BufferedReader(new FileReader(FILE_IN));
out = new PrintWriter(new FileWriter(FILE_OUT));
} else {
in = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(new OutputStreamWriter(System.out));
}
solve();
in.close();
out.close();
} catch (IOException e) {
throw new IllegalStateException(e);
}
long timeEnd = System.currentTimeMillis();
if (fileIO) {
System.out.println("Time spent: " + (timeEnd - timeStart) + " ms");
}
}
private String nextToken() throws IOException {
while (!tokenizer.hasMoreTokens()) {
String line = in.readLine();
if (line == null) {
return null;
}
tokenizer = new StringTokenizer(line);
}
return tokenizer.nextToken();
}
private int nextInt() throws IOException {
return Integer.parseInt(nextToken());
}
}
Python 2 rep HackerRank Solution
f = lambda n:n-1 + abs(n-1) and f(n-1)*long(n) or 1
def main():
ncases = int(raw_input())
for n in range(ncases):
raw_input()
case = [int(x) for x in raw_input().split()]
N = len(case)
L = case.count(-1)
cm = [case.count(d) for d in range(N)]
print get_counts(N, L, cm).get((N, N*(N-1)/2), 0) % 1000000007
def get_counts(N, L, cm):
"""
Iteratively generate solutions that satisfy two constraints.
N is the overall length of the scorecard.
L is the number of omitted scores.
cm is the minimum number of counts of each score, based on the scores that
are not omitted.
Here on, S1 is the length of the score set, and S2 is the sum of scores.
New score sets are generated by considering all possible counts of scores
equal to m. Such a score count is considered possible if it satisfies
Landau's theorem for tournaments (1953).
"""
S1max = N
S2max = N*(N-1)/2
C = {(0, 0) : f(L)}
for m in range(N):
Cn = {}
for (s1, s2), c in C.iteritems():
n = cm[m]
i = 0
fct = 1
S1 = s1+n
S2 = s2+m*n
while S1*(S1-1)/2 <= S2 <= S2max:
Cn[(S1, S2)] = Cn.get((S1, S2), 0) + c/fct
#big = Cn.get((S1, S2), 0) + c/fct
#Cn[(S1, S2)] = big % 1000000007
n += 1
i += 1
fct *= i
S1 = s1+n
S2 = s2+m*n
C = Cn
return C
if __name__ == '__main__':
main()
Python 3 rep HackerRank Solution
C rep HackerRank 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++;
}
// printf("%lld %lld h %lld %lld=l\n",i,j,h,l);
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(ii=0;ii<=n;ii++)
// for(jj=0;jj<=m;jj++)
// for(kk=0;kk<=1000;kk++)
// if(a[ii][jj][kk]) printf("%lld %lld %lld -> %lld\n", ii,jj,kk,a[ii][jj][kk]);
//printf("stred -----------%lld\n",i);
// continue;
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;
// if(a[i][j-jj][h]>0) printf("...%lld=i %lld=j %lld=k %lld=jj %lld=h\n",i,j,k,jj,h);
}
}
//for(ii=0;ii<=n;ii++)
// for(jj=0;jj<=m;jj++)
// for(kk=0;kk<=1000;kk++)
// if(a[ii][jj][kk]) printf("%lld %lld %lld -> %lld\n", ii,jj,kk,a[ii][jj][kk]);
//printf("-----------%lld\n",i);
l+=b[i];
}
/*
for(i=0;i<=n;i++)
for(j=0;j<=m;j++)
for(k=0;k<=1000;k++)
if(a[i][j][k]) printf("%lld %lld %lld -> %lld\n", i,j,k,a[i][j][k]);
for(i=0;i<=n;i++) printf("%lld %lld\n",i,c[i]);
*/
printf("%lld\n",(a[0][m][0]+P)%P);
//return 0;
}
return 0;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
