Simple Game – 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
/* no greedy easy life */
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cassert>
#include <cstdlib>
#include <queue>
#include <ctime>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
const double EPS = 1e-9;
const double PI = acos(-1);
const int MOD = (int) 1e9 + 7;
const int MAXN = (int) 666 + 7;
int n, m, k;
int g[MAXN];
bool used[MAXN];
int dp[11][MAXN][MAXN];
void add(int &x, int y) {
x += y;
if (x >= MOD) {
x -= MOD;
}
}
int get(int x) {
if (k <= 3)
return g[x];
else
return x - 1;
}
int main() {
#ifdef LOCAL
freopen("in", "r", stdin);
//freopen("out", "w", stdout);
#endif
cin >> n >> m >> k;
g[1] = 0;
for (int i = 2; i <= n; i++) {
memset(used, 0, sizeof used);
for (int x = 1; x < i; x++)
used[g[x] ^ g[i - x]] = true;
if (k > 2) {
for (int x = 1; x < i; x++)
for (int y = x; x + y < i; y++)
used[g[x] ^ g[y] ^ g[i - x - y]] = true;
}
while (used[g[i]]) {
g[i]++;
}
}
dp[0][0][0] = 1;
for (int len = 0; len < m; len++) {
for (int sum = 0; sum <= n; sum++) {
for (int xor_sum = 0; xor_sum <= n; xor_sum++) {
if (!dp[len][sum][xor_sum]) continue;
for (int last = 1; last <= n - sum; last++) {
add(dp[len + 1][sum + last][xor_sum ^ get(last)], dp[len][sum][xor_sum]);
}
}
}
}
int ans = 0;
for (int x = 1; x <= n; x++)
add(ans, dp[m][n][x]);
cout << ans;
return 0;
}
Java rep HackerRank Solution
import java.io.*;
import java.util.*;
public class HR_simple_game {
final static long MOD = 1000000007;
static int K;
static HashMap<Integer, BitSet>[] cache;
static int[] mexCache;
static int mex(int n) {
if (mexCache[n] == -1) {
mexCache[n] = 0;
BitSet set = new BitSet();
for (int k = 2; k <= K; ++k) {
set.or(d(n, k));
}
while (set.get(mexCache[n])) {
mexCache[n]++;
}
}
return mexCache[n];
}
static BitSet d(int n, int k) {
if (cache[n] == null) {
cache[n] = new HashMap<>();
}
BitSet ret = cache[n].get(k);
if (ret == null) {
ret = new BitSet();
if (k == 1) {
ret.set(mex(n));
} else {
for (int n1 = 1; n1 < n; ++n1) {
BitSet s1 = d(n1, k - 1);
int v2 = mex(n - n1);
for (int v1 = s1.nextSetBit(0); v1 >= 0; v1 = s1.nextSetBit(v1 + 1)) {
ret.set(v1 ^ v2);
}
}
}
cache[n].put(k, ret);
}
return ret;
}
public static void solve(Input in, PrintWriter out) throws IOException {
int n = in.nextInt();
int m = in.nextInt();
K = in.nextInt();
int[] values = new int[n + 1];
if (K <= 3) {
cache = new HashMap[n + 1];
mexCache = new int[n + 1];
Arrays.fill(mexCache, -1);
for (int i = 0; i <= n; ++i) {
values[i] = mex(i);
}
} else {
for (int i = 2; i <= n; ++i) {
values[i] = i - 1;
}
}
int maxValue = 1;
for (int i = 0; i <= n; ++i) {
while (maxValue <= values[i]) {
maxValue *= 2;
}
}
// System.err.println(Arrays.toString(values));
long[][] d = new long[n + 1][maxValue];
d[0][0] = 1;
for (int it = 0; it < m; ++it) {
long[][] d1 = new long[n + 1][maxValue];
for (int i = 0; i <= n; ++i) {
for (int v = 0; v < maxValue; ++v) {
if (d[i][v] == 0) {
continue;
}
for (int j = 1; i + j <= n; ++j) {
d1[i + j][v ^ values[j]] += d[i][v];
}
}
}
d = d1;
for (int i = 0; i <= n; ++i) {
for (int v = 0; v < maxValue; ++v) {
d[i][v] %= MOD;
}
}
}
long ans = 0;
for (int v = 1; v < maxValue; ++v) {
ans += d[n][v];
}
out.println(ans % 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
C rep HackerRank Solution
/*
4 3 3
3
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD 1000000007
#define MAX_NIM 600
#define MAX_NIM_SIZE (MAX_NIM/63+1)
void solve(int x);
void solve_aux(int x,int y,long long *a);
int min(int x,int y);
long long solve1(int n,int m);
long long solve2(int n,int m,int o);
int K,nim[600],tt[MAX_NIM];
long long dp[600][600][MAX_NIM_SIZE],dp1[600][10],dp2[600][10][600];
int main(){
int N,M,i;
long long total,total1;
memset(dp,-1,sizeof(dp));
memset(dp1,-1,sizeof(dp1));
memset(dp2,-1,sizeof(dp2));
scanf("%d%d%d",&N,&M,&K);
if(K>=4)
for(i=0;i<N;i++)
nim[i]=i;
else{
nim[0]=0;
for(i=2;i<=N;i++)
solve(i);
}
total=solve1(N,M);
total1=solve2(N,M,0);
printf("%lld",(total-total1+MOD)%MOD);
return 0;
}
void solve(int x){
int i,j,sum;
long long a[MAX_NIM_SIZE];
memset(tt,0,sizeof(tt));
for(i=1;i<x;i++){
solve_aux(x-i,min(x-i,K-1),a);
for(j=0;j<MAX_NIM;j++)
if(a[j/63]&(1LL<<(j%63))){
sum=(nim[i-1]^j);
tt[sum]=1;
}
}
for(i=0;i<MAX_NIM;i++)
if(!tt[i]){
nim[x-1]=i;
break;
}
return;
}
void solve_aux(int x,int y,long long *a){
int i,j,sum;
long long b[MAX_NIM_SIZE];
if(!x){
for(i=0;i<MAX_NIM_SIZE;i++)
a[i]=0;
return;
}
if(dp[x-1][y-1][0]!=-1){
for(i=0;i<MAX_NIM_SIZE;i++)
a[i]=dp[x-1][y-1][i];
a[nim[x-1]/63]|=(1LL<<(nim[x-1]%63));
return;
}
for(i=0;i<MAX_NIM_SIZE;i++)
a[i]=dp[x-1][y-1][i]=0;
if(y==1){
a[nim[x-1]/63]|=(1LL<<(nim[x-1]%63));
dp[x-1][y-1][nim[x-1]/63]|=(1LL<<(nim[x-1]%63));
return;
}
for(i=1;i<=x;i++){
solve_aux(x-i,min(x-i,y-1),b);
for(j=0;j<MAX_NIM;j++)
if(b[j/63]&(1LL<<(j%63))){
sum=(nim[i-1]^j);
a[sum/63]|=(1LL<<(sum%63));
dp[x-1][y-1][sum/63]|=(1LL<<(sum%63));
}
}
return;
}
int min(int x,int y){
return (x<y)?x:y;
}
long long solve1(int n,int m){
int i;
if(!n || !m)
return 0;
if(dp1[n-1][m-1]!=-1)
return dp1[n-1][m-1];
if(m==1)
dp1[n-1][m-1]=1;
else{
dp1[n-1][m-1]=0;
for(i=1;i<n;i++)
dp1[n-1][m-1]=(dp1[n-1][m-1]+solve1(n-i,m-1))%MOD;
}
return dp1[n-1][m-1];
}
long long solve2(int n,int m,int o){
int i;
if(!n || !m)
return 0;
if(dp2[n-1][m-1][o]!=-1)
return dp2[n-1][m-1][o];
if(m==1)
if(nim[n-1]==o)
dp2[n-1][m-1][o]=1;
else
dp2[n-1][m-1][o]=0;
else{
dp2[n-1][m-1][o]=0;
for(i=1;i<n;i++)
dp2[n-1][m-1][o]=(dp2[n-1][m-1][o]+solve2(n-i,m-1,o^nim[i-1]))%MOD;
}
return dp2[n-1][m-1][o];
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
