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. Topics we are covering Toggle Problem solution in Python.Problem solution in Java.Problem solution in C++.Problem solution in C. 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); } Algorithms coding problems solutions