Table of Contents
Dortmund Dilemma – 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
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
typedef long long LL;
using namespace std;
const int SIZE = 1e5+5;
const int MOD = 1e9+9;
LL C[27][27],an[27][SIZE],tmp[27][SIZE],pp[27][SIZE],tmp2[27][SIZE],ha[27];
int main(){
REPP(i,1,27){
pp[i][0]=1;
REPP(j,1,SIZE)pp[i][j]=pp[i][j-1]*i%MOD;
}
REP(i,27){
C[i][0]=1;
REPP(j,1,i+1){
C[i][j]=C[i-1][j-1]+C[i-1][j];
}
}
REPP(i,1,27){
an[i][1]=i;
tmp[i][1]=i;
REPP(j,2,SIZE){
if(j%2==0)an[i][j]=tmp[i][j/2];
else an[i][j]=tmp[i][j/2]*i%MOD;
an[i][j]=pp[i][j]-an[i][j];
REPP(k,1,i){
an[i][j]=(an[i][j]-an[k][j]*C[i][k])%MOD;
}
if(an[i][j]<0)an[i][j]+=MOD;
tmp[i][j]=tmp[i][j-1]*i*i%MOD;
REPP(k,1,i+1){
tmp[i][j]=(tmp[i][j]+C[i][k]*an[k][j])%MOD;
}
}
}
CASET{
DRII(N,K);
if(N==1){
puts("0");
continue;
}
LL res=0;
if(N%2==0){
ha[1]=tmp[1][N/2];
REPP(i,2,K+1){
ha[i]=tmp[i][N/2];
REPP(j,1,i)ha[i]=(ha[i]-ha[j]*C[i][j])%MOD;
if(ha[i]<0)ha[i]+=MOD;
}
res=ha[K]*C[26][K]%MOD;
}
else{
ha[1]=tmp[1][N/2];
REPP(i,2,K+1){
ha[i]=tmp[i][N/2]*i%MOD;
REPP(j,1,i)ha[i]=(ha[i]-ha[j]*C[i][j])%MOD;
if(ha[i]<0)ha[i]+=MOD;
}
res=ha[K]*C[26][K]%MOD;
}
if(K==1)res=26;
if(res<0)res+=MOD;
printf("%lld\n",res);
}
return 0;
}
Java rep HackerRank Solution
import java.io.*;
import java.util.Arrays;
public class Solution {
static final long MOD = 1000000009;
static final int MAXK = 26;
static final int MAXN = 100000;
static long modPow(long x, long pow) {
long r = 1;
while (pow > 0) {
if (pow % 2 == 1) {
r = r * x % MOD;
}
pow /= 2;
x = x * x % MOD;
}
return r;
}
public static void solve(Input in, PrintWriter out) throws IOException {
long[][] c = new long[MAXK + 1][MAXK + 1];
for (int i = 0; i < c.length; ++i) {
for (int j = 1; j < i; ++j) {
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
}
c[i][0] = c[i][i] = 1;
}
long[][] d = new long[MAXK + 1][MAXN + 1];
for (int j = 1; j <= MAXK; ++j) {
d[j][0] = 1;
}
for (int i = 1; i <= MAXN; ++i) {
for (int j = 1; j <= MAXK; ++j) {
d[j][i] = (d[j][i - 1] * j + (i % 2 == 0 ? MOD - d[j][i / 2] : 0)) % MOD;
}
}
for (int i = 1; i <= MAXN; ++i) {
for (int j = 1; j <= MAXK; ++j) {
d[j][i] = (modPow(j, i) + MOD - d[j][i]) % MOD;
for (int j1 = 1; j1 < j; ++j1) {
d[j][i] = (d[j][i] + (MOD - c[j][j1]) * d[j1][i]) % MOD;
}
}
}
int tests = in.nextInt();
for (int test = 0; test < tests; ++test) {
int n = in.nextInt();
int k = in.nextInt();
out.println(d[k][n] * c[MAXK][k] % MOD);
}
}
public static void main(String[] args) throws IOException {
PrintWriter out = new PrintWriter(System.out);
solve(new Input(new BufferedReader(new InputStreamReader(System.in))), out);
out.close();
}
static class Input {
BufferedReader in;
StringBuilder sb = new StringBuilder();
public Input(BufferedReader in) {
this.in = in;
}
public Input(String s) {
this.in = new BufferedReader(new StringReader(s));
}
public String next() throws IOException {
sb.setLength(0);
while (true) {
int c = in.read();
if (c == -1) {
return null;
}
if (" \n\r\t".indexOf(c) == -1) {
sb.append((char)c);
break;
}
}
while (true) {
int c = in.read();
if (c == -1 || " \n\r\t".indexOf(c) != -1) {
break;
}
sb.append((char)c);
}
return sb.toString();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public long nextLong() throws IOException {
return Long.parseLong(next());
}
public double nextDouble() throws IOException {
return Double.parseDouble(next());
}
}
}
Python 3 rep HackerRank Solution
Python 2 rep HackerRank Solution
def go():
choose = [[1]]
for n in range(1,27):
a = [1]
for k in range(1,n):
a.append(choose[-1][k] + choose[-1][k-1])
a.append(1)
choose.append(a)
MAX = 10**5+1
MOD = 10**9+9
F = [[]]
for k in range(1,27):
f = [1]
for v in range(1,MAX):
nxt = f[-1]*k
if v%2==0: nxt -= f[v//2]
f.append(nxt % MOD)
F.append(f)
for _ in range(input()):
N,K = map(int,raw_input().split())
g = [0]
for k in range(1,K+1):
g.append((pow(k, N, MOD) - F[k][N] - sum(g[j]*choose[k][j] for j in range(1,k)) % MOD))
print g[-1] * choose[26][K] % MOD
go()
C rep HackerRank Solution
#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;
}
}
// K K
fe(n,0,K) fe(r,0,K) {
if (r < 0 || r > n) {
C[n][r] = 0;
} else if (r == 0 || r == n) {
C[n][r] = 1;
} else {
C[n][r] = (C[n-1][r-1] + C[n-1][r]) % mod;
}
}
// 2N K
fe(k,0,K) fe(n,0,2*N) {
//_p
if (n == 0) {
_p[k][n] = 1;
} else {
_p[k][n] = _p[k][n-1] * k % mod;
}
//_q
if (n == 0) {
_q[k][n] = 1;
} else {
_q[k][n] = _q[k][n-1] * _i[k] % mod;
}
}
// N K
fe(k,0,K) fe(n,0,N) {
//_g
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;
}
//_s
if (n == 0) {
_s[k][n] = 0;
} else {
_s[k][n] = (_s[k][n-1] + _g[k][n]) % mod;
}
//_t
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("%lld\n", ans);
}
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
