HackerRank Dortmund Dilemma problem solution YASH PAL, 31 July 2024 In this HackerRank Dortmund Dilemma problem solution, we have given the length N of Letter and number of K different letters from thw 26 letters of the English alphabet. and we need to find the number of easy names we can choose. Problem solution in Python. def func(): MOD = (10 ** 9) + 9 Max = (10 ** 5) + 1 nCr = [[1]] for n in range(1, 27): m = [1] for k in range(1, n): m.append(nCr[-1][k] + nCr[-1][k - 1]) m.append(1) nCr.append(m) DP = [[]] for k in range(1, 27): FDP = [1] for i in range(1, Max): temp = FDP[-1] * k if i % 2 == 0: temp = temp - FDP[i // 2] FDP.append(temp % MOD) DP.append(FDP) for t in range(int(input())): N, K = map(int, input().split()) G = [0] for i in range(1, K + 1): G.append(pow(i, N, MOD) - DP[i][N] - sum(G[j] * nCr[i][j] for j in range(1, i)) % MOD) print(G[-1] * nCr[26][K] % MOD) func() Problem solution in Java. import java.util.Scanner; public class DortmundDilemma { public static final int MAX_N = 100000; public static final int MAX_K = 26; public static final long MOD = 1000000009; static long[][] C; static long[][] F; static long[][] G; static long[][] P; public static void main(String[] args) { C = new long[MAX_K+1][MAX_K+1]; for (int i = 0; i <= MAX_K; i++) { C[i][0] = C[i][i] = 1; for (int j = 1; j < i; j++) { C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD; } } F = new long[MAX_N+1][MAX_K+1]; G = new long[MAX_N+1][MAX_K+1]; P = new long[MAX_N+1][MAX_K+1]; for (int k = 1; k <= MAX_K; k++) { F[1][k] = k; long kn = k; for (int n = 2; n <= MAX_N; n++) { kn = kn * k % MOD; if (n % 2 == 1) { F[n][k] = F[n-1][k] * k % MOD; } else { F[n][k] = (F[n-1][k] * k % MOD - F[n/2][k] + MOD) % MOD; } G[n][k] = (kn - F[n][k] + MOD) % MOD; P[n][k] = G[n][k]; for (int j = 1; j < k; j++) { P[n][k] = (P[n][k] - P[n][j] * C[k][j] % MOD + MOD) % MOD; } } } Scanner scanner = new Scanner(System.in); for (int t = scanner.nextInt(); t > 0; t--) { int N = scanner.nextInt(), K = scanner.nextInt(); System.out.println(P[N][K] * C[26][K] % MOD); } scanner.close(); } } Problem solution in C++. #include <stdio.h> #include <stdlib.h> #include <math.h> #include <string.h> #include <assert.h> #define fo(i,a,b) dfo(int,i,a,b) #define fr(i,n) dfr(int,i,n) #define fe(i,a,b) dfe(int,i,a,b) #define fq(i,n) dfq(int,i,n) #define nfo(i,a,b) dfo(,i,a,b) #define nfr(i,n) dfr(,i,n) #define nfe(i,a,b) dfe(,i,a,b) #define nfq(i,n) dfq(,i,n) #define dfo(d,i,a,b) for (d i = (a); i < (b); i++) #define dfr(d,i,n) dfo(d,i,0,n) #define dfe(d,i,a,b) for (d i = (a); i <= (b); i++) #define dfq(d,i,n) dfe(d,i,1,n) #define ffo(i,a,b) dffo(int,i,a,b) #define ffr(i,n) dffr(int,i,n) #define ffe(i,a,b) dffe(int,i,a,b) #define ffq(i,n) dffq(int,i,n) #define nffo(i,a,b) dffo(,i,a,b) #define nffr(i,n) dffr(,i,n) #define nffe(i,a,b) dffe(,i,a,b) #define nffq(i,n) dffq(,i,n) #define dffo(d,i,a,b) for (d i = (b)-1; i >= (a); i--) #define dffr(d,i,n) dffo(d,i,0,n) #define dffe(d,i,a,b) for (d i = (b); i >= (a); i--) #define dffq(d,i,n) dffe(d,i,1,n) #define ll long long #define alok(n,t) ((t*)malloc((n)*sizeof(t))) #define pf printf #define sf scanf #define pln pf("n") #define mod 1000000009 #define bet(a,b,c) ((a)<=(b)&&(b)<=(c)) #define K 26 #define N 111111 ll _i[K+1]; ll C[K+1][K+1]; ll _p[K+1][2*N+1]; ll _q[K+1][2*N+1]; ll _s[K+1][N+1]; ll _g[K+1][N+1]; ll _t[K+1][N+1]; int main() { fe(k,0,K) { if (k == 0) { _i[k] = 0; } else if (k == 1) { _i[k] = 1; } else { _i[k] = (mod - mod/k) * _i[mod % k] % mod; } } fe(n,0,K) fe(r,0,K) { if (r < 0 or r > n) { C[n][r] = 0; } else if (r == 0 or r == n) { C[n][r] = 1; } else { C[n][r] = (C[n-1][r-1] + C[n-1][r]) % mod; } } fe(k,0,K) fe(n,0,2*N) { if (n == 0) { _p[k][n] = 1; } else { _p[k][n] = _p[k][n-1] * k % mod; } if (n == 0) { _q[k][n] = 1; } else { _q[k][n] = _q[k][n-1] * _i[k] % mod; } } fe(k,0,K) fe(n,0,N) { if (k == 1) { if (n <= 1) { _g[k][n] = 0; } else { _g[k][n] = _q[k][2*n]; } } else { ll s = (_p[k][n/2]-1) * _i[k-1] % mod * _p[k][(n+1)/2]; ll t = _s[k][n/2] * _p[k][n]; _g[k][n] = (s - t) % mod * _q[k][2*n] % mod; } if (n == 0) { _s[k][n] = 0; } else { _s[k][n] = (_s[k][n-1] + _g[k][n]) % mod; } if (k == 0) { _t[k][n] = 0; } else { ll ct = _p[k][2*n] * _g[k][n] % mod; fr(kk,k) { ct -= C[k][kk] * _t[kk][n]; ct %= mod; } _t[k][n] = ct; } } int z; sf("%d", &z); assert(bet(1,z,100000)); while (z--) { int n, k; sf("%d%d", &n, &k); assert(bet(1,n,100000)); assert(bet(1,k,26)); ll ans = _t[k][n] * C[26][k] % mod; if (ans < 0) ans += mod; pf("%lldn", ans); } } Problem solution in C. #include <assert.h> #include <limits.h> #include <math.h> #include <stdbool.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #define FOR(i, a, b) for(__typeof(a) i=(a); i<(b); i++) #define MEM(x,val) memset((x),(val),sizeof(x)); #define MOD 1000000009 #define N 100000 #define K 26 typedef long long ll; char* readline(); char** split_string(char*); void print_matrix(int n, int m, ll arr[n][m]) { for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { printf("%lld ", arr[i][j]); } putchar('n'); } } ll cdp[K+1][K+1]; ll comb(ll n, ll k){ if(k > n) return 0; if(n == k) return 1; if(k == 0) return 1; if(k == 1) return n % MOD; if(cdp[n][k]==-1) cdp[n][k] = ( comb(n-1,k-1) + comb(n-1,k) ) % MOD; return cdp[n][k]; } ll dp[N+1][K+1]; void init() { MEM(cdp, -1); FOR(k, 1, K+1) { FOR(n, 1, N+1) { if(n==1) dp[n][k] = k; else { dp[n][k] = (n % 2 ? (dp[n-1][k]*k)%MOD: (dp[n-1][k]*k)%MOD - dp[n/2][k] ) % MOD; if(dp[n][k] < 0) dp[n][k] += MOD; } } } FOR(k, 1, K+1) { ll kN = 1; FOR(n, 1, N+1) { kN = kN*k % MOD; dp[n][k] = kN - dp[n][k]; if(dp[n][k] < 0) dp[n][k] += MOD; FOR(j, 1, k) { dp[n][k] -= (dp[n][j]*comb(k,j)) % MOD; if(dp[n][k] < 0) dp[n][k] += MOD; } } } } int main() { init(); FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w"); int t; scanf("%d", &t); while (t--) { int n, k; scanf("%d %d", &n, &k); assert(1 <= n && n <= 100000); assert(1 <= k && k <= 26); fprintf(fptr, "%lldn", (dp[n][k]*comb(26,k))%MOD); } fclose(fptr); } algorithm coding problems