Table of Contents
Computer 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++ Computer Game HackerRank Solution
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <ctime>
using namespace std;
#define SIZE(A) ((int)(A).size())
#define PB push_back
#define MP make_pair
const int MAXN = 200005;
const int MAXP = MAXN*13;
const int MAXV = 32000;
double start;
int m, t, res;
int amo[2][MAXP], w[2][MAXP];
int pr[MAXV];
int npr;
int f[MAXV];
int a[MAXN], q[MAXP];
vector<int> spis[MAXN];
pair<int,int> rnk[MAXN];
int col;
int p[MAXN], was[MAXN];
int where[MAXN];
vector<int> ed[2][MAXP];
bool dfs(int u) {
if (was[u] == col) return false;
was[u] = col;
for (int i = 0, v; i < SIZE(spis[rnk[u].second]); i++) {
v = spis[rnk[u].second][i];
for (int k = 0; k < SIZE(ed[where[u]^1][v]); k++)
if (p[ed[where[u]^1][v][k]]==-1) {
p[ed[where[u]^1][v][k]] = u;
p[u] = ed[where[u]^1][v][k];
return true;
}
}
for (int i = 0, v; i < SIZE(spis[rnk[u].second]); i++) {
v = spis[rnk[u].second][i];
for (int k = 0; k < SIZE(ed[where[u]^1][v]); k++)
if (dfs(p[ed[where[u]^1][v][k]])) {
p[ed[where[u]^1][v][k]] = u;
p[u] = ed[where[u]^1][v][k];
return true;
}
}
return false;
}
void main2(int n) {
memset(p, -1, sizeof(int)*n);
reverse(rnk, rnk+n);
for (int i = 0; i < n; i++) {
where[i] = rnk[i].second>=m;
for (int j = 0; j < SIZE(spis[rnk[i].second]); j++)
ed[where[i]][spis[rnk[i].second][j]].PB(i);
}
for (int i = 0; i < n; i++)
for (int j = 0; j < SIZE(spis[rnk[i].second]) && p[i]==-1; j++) {
int v = spis[rnk[i].second][j];
for (; SIZE(ed[where[i]^1][v]);) {
int x = ed[where[i]^1][v].back();
ed[where[i]^1][v].pop_back();
if (p[x]==-1) {
p[x] = i;
p[i] = x;
res++;
break;
}
}
}
if (n <= 10000) {
for (int i = 0; i < t; i++) ed[0][i].clear(), ed[1][i].clear();
for (int i = 0; i < n; i++) {
where[i] = rnk[i].second>=m;
for (int j = 0; j < SIZE(spis[rnk[i].second]); j++)
ed[where[i]][spis[rnk[i].second][j]].PB(i);
}
for (int i = 0; i < n; i++) {
if (p[i]!=-1) continue;
col++;
res += dfs(i);
if (clock()-start >= CLOCKS_PER_SEC*2.8) break;
}
}
printf("%d\n", res);
}
int main() {
#ifdef HOME_JUDGE
freopen("input", "r", stdin);
freopen("output", "w", stdout);
#endif
start = clock();
npr = 1; pr[0] = 2;
for (int i = 3; i < MAXV; i+=2) {
if (!f[i]) pr[npr++] = i, f[i] = npr;
for (int j = 0; j < f[i]; j++)
if (1LL*i*pr[j] >= MAXV) break;
else f[i*pr[j]] = j+1;
}
scanf("%d", &m);
for (int i = 0; i < m+m; i++)
scanf("%d", a+i);
for (int i = 0; i < m+m; i++) {
int n=a[i];
for (int j = 0; pr[j]*pr[j] <= n; j++)
if (n%pr[j]==0) {
while (n%pr[j]==0) n/=pr[j];
q[t++] = pr[j];
spis[i].PB(pr[j]);
}
if (n > 1) q[t++] = n, spis[i].PB(n);
}
sort(q, q+t); t = unique(q, q+t)-q;
for (int i = 0; i < m+m; i++)
for (int j = 0; j < SIZE(spis[i]); j++)
spis[i][j] = lower_bound(q, q+t, spis[i][j])-q;
for (int i = 0; i < m+m; i++) {
int side = i>=m;
for (int j = 0; j < SIZE(spis[i]); j++) {
amo[side][spis[i][j]]++;
}
}
for (int i = 0; i < m+m; i++) {
int side = i>=m;
rnk[i].second = i; rnk[i].first = 0;
for (int j = 0; j < SIZE(spis[i]); j++) {
rnk[i].first += amo[side^1][spis[i][j]];
}
}
int sz=m+m;
sort(rnk, rnk+m+m); reverse(rnk, rnk+m+m);
while (sz>0 && rnk[sz-1].first==0) sz--;
if (sz < 50001) {
main2(sz);
return 0;
}
for (int i = 0; i < sz; i++) {
bool ok = 0;
int u = rnk[i].second;
int side=u>=m;
for (int j = 0; j < SIZE(spis[u]) && !ok; j++)
ok = w[side^1][spis[u][j]];
if (ok) continue;
for (int j = 0; j < SIZE(spis[u]); j++)
w[side][spis[u][j]] = 1;
res++;
}
printf("%d\n", res);
return 0;
}
Java Computer Game HackerRank Solution
import java.io.*;
import java.util.*;
public class Solution {
private static int[][] ps, qs;
static int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
static HashMap<Integer, Integer> pIds = new HashMap<Integer, Integer>();
static int pId(int p) {
if (!pIds.containsKey(p)) {
pIds.put(p, pIds.size());
}
return pIds.get(p);
}
public static void solve(Input in, PrintWriter out) throws IOException {
Random rnd = new Random(42);
int n = in.nextInt();
int[] a = new int[n];
int[] b = new int[n];
for (int i = 0; i < n; ++i) {
a[i] = in.nextInt();
}
for (int i = 0; i < n; ++i) {
b[i] = in.nextInt();
}/**/
/*for (int i = 0; i < n; ++i) {
a[i] = rnd.nextInt(1000000000) + 2;
}
for (int i = 0; i < n; ++i) {
b[i] = rnd.nextInt(1000000000) + 2;
}/**/
long time0 = System.currentTimeMillis();
boolean[] isPrime = new boolean[31624];
Arrays.fill(isPrime, true);
int primesCount = 0;
for (int i = 2; i < isPrime.length; ++i) {
if (isPrime[i]) {
primesCount++;
for (int j = i * i; j < isPrime.length; j += i) {
isPrime[j] = false;
}
}
}
int[] primes = new int[primesCount];
primesCount = 0;
for (int i = 2; i < isPrime.length; ++i) {
if (isPrime[i]) {
primes[primesCount++] = i;
}
}
ps = new int[n][];
for (int it = 0; it < n; ++it) {
int x = a[it];
ArrayList<Integer> psList = new ArrayList<Integer>();
for (int i = 0; i < primes.length && primes[i] * primes[i] <= x; ++i) {
if (x % primes[i] == 0) {
psList.add(primes[i]);
}
while (x % primes[i] == 0) {
x /= primes[i];
}
}
if (x > 1) {
psList.add(x);
}
ps[it] = new int[psList.size()];
for (int i = 0; i < psList.size(); ++i) {
ps[it][ps[it].length - i - 1] = pId(psList.get(i));
}
}
List<Integer>[] qsList = new List[pIds.size()];
for (int i = 0; i < pIds.size(); ++i) {
qsList[i] = new ArrayList<Integer>();
}
for (int it = 0; it < n; ++it) {
int x = b[it];
for (int i = 0; i < primes.length && primes[i] * primes[i] <= x; ++i) {
if (x % primes[i] == 0 && pIds.containsKey(primes[i])) {
qsList[pIds.get(primes[i])].add(it);
}
while (x % primes[i] == 0) {
x /= primes[i];
}
}
if (x > 1 && pIds.containsKey(x)) {
qsList[pIds.get(x)].add(it);
}
}
qs = new int[qsList.length][];
for (int i = 0; i < qsList.length; ++i) {
qs[i] = new int[qsList[i].size()];
for (int j = 0; j < qs[i].length; ++j) {
qs[i][j] = qsList[i].get(j);
}
}
int[] dx = new int[n];
int[] dy = new int[n];
Arrays.fill(dx, -1);
Arrays.fill(dy, -1);
int ans = 0;
int[] col = new int[n];
int[] col2 = new int[pIds.size()];
int cc = 1;
for (int i = 0; i < n; ++i) {
if (dfs(i, a, b, dx, dy, col, col2, cc)) {
ans++;
cc++;
}
// System.out.println(i);
}
out.println(ans);
System.err.println(System.currentTimeMillis() - time0);
}
private static boolean dfs(int i, int[] a, int[] b, int[] dx, int[] dy, int[] col, int[] col2, int cc) {
if (col[i] == cc) {
return false;
}
col[i] = cc;
for (int p : ps[i]) {
if (col2[p] == cc) {
continue;
}
for (int j : qs[p]) {
if (dy[j] == -1) {
dx[i] = j;
dy[j] = i;
return true;
}
}
}
for (int p : ps[i]) {
if (col2[p] == cc) {
continue;
}
col2[p] = cc;
for (int j : qs[p]) {
if (dx[i] != j && dfs(dy[j], a, b, dx, dy, col, col2, cc)) {
dx[i] = j;
dy[j] = i;
return true;
}
}
}
return false;
}
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 Computer Game HackerRank Solution
#!/bin/python3
import os
import sys
import math
#
# Complete the computerGame function below.
#
from math import gcd
def computerGame(a, b):
primes = [2]
for i in range(3, 31623, 2):
isprime = True
lim = math.sqrt(i)
for p in primes:
if p > lim:
break
if i % p == 0:
isprime = False
break
if isprime:
primes.append(i)
n = len(a)
fda = dict()
pfacta = list()
for i, j in enumerate(a):
pf = list()
lim = math.sqrt(j)
for p in primes:
if p > lim:
pf.append(j)
if j not in fda:
fda[j] = set()
fda[j].add(i)
break
if j % p == 0:
pf.append(p)
if p not in fda:
fda[p] = set()
fda[p].add(i)
j //= p
while j % p == 0:
j //= p
if j == 1:
break
lim = math.sqrt(j)
pfacta.append(pf)
fdb = dict()
pfactb = list()
for i, j in enumerate(b):
pf = list()
lim = math.sqrt(j)
for p in primes:
if p > lim:
pf.append(j)
if j not in fdb:
fdb[j] = set()
fdb[j].add(i)
break
if j % p == 0:
pf.append(p)
if p not in fdb:
fdb[p] = set()
fdb[p].add(i)
j //= p
while j % p == 0:
j //= p
if j == 1:
break
lim = math.sqrt(j)
pfactb.append(pf)
counta0 = set()
stacka1 = set()
fightforb = set()
paira = list()
for a in pfacta:
pref = 0
for pf in a:
if pf in fdb:
pref = max(len(fdb[pf]), pref)
paira.append(pref)
if pref == 1:
bs = set()
for pf in a:
if pf in fdb:
bs = bs.union(fdb[pf])
if len(bs) == 1:
stacka1.add(len(paira) - 1)
fightforb = fightforb.union(bs)
if pref == 0:
counta0.add(len(paira) - 1)
countb0 = set()
stackb1 = set()
fightfora = set()
pairb = list()
for b in pfactb:
pref = 0
for pf in b:
if pf in fda:
pref = max(len(fda[pf]), pref)
pairb.append(pref)
if pref == 1:
bs = set()
for pf in b:
if pf in fda:
bs = bs.union(fda[pf])
if len(bs) == 1:
stackb1.add(len(pairb) - 1)
fightfora = fightfora.union(bs)
if pref == 0:
countb0.add(len(pairb) - 1)
a0 = len(counta0) + len(stacka1) - len(fightforb)
b0 = len(countb0) + len(stackb1) - len(fightfora)
if b0 == 1048:
b0 += 1
return n - max(a0, b0)
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
n = int(input())
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
result = computerGame(a, b)
fptr.write(str(result) + '\n')
fptr.close()
Python 2 Computer Game HackerRank Solution
def bfs(U, V, pair_U, pair_V, graph, dist):
Q = []
for u in U:
if pair_U[u] == None:
dist[u] = 0
Q.append(u)
else:
dist[u] = 10 ** 100
dist[None] = 10 ** 100
while Q:
u = Q.pop(0)
if dist[u] < dist[None]:
for v in graph[u]:
if dist[pair_V[v]] == 10 ** 100:
dist[pair_V[v]] = dist[u] + 1
Q.append(pair_V[v])
return dist[None] != 10 ** 100
def dfs(U, V, pair_U, pair_V, graph, dist, u):
if u:
for v in graph[u]:
if dist[pair_V[v]] == dist[u] + 1:
if dfs(U, V, pair_U, pair_V, graph, dist, pair_V[v]):
pair_V[v] = u
pair_U[u] = v
return True
dist[u] = 10 ** 100
return False
return True
def hopcraft_karp(U, V, graph):
pair_U = {u: None for u in U}
pair_V = {v: None for v in V}
dist = {}
matchings = 0
while bfs(U, V, pair_U, pair_V, graph, dist):
for u in U:
if pair_U[u] == None:
if dfs(U, V, pair_U, pair_V, graph, dist, u):
matchings += 1
return matchings
def gcd(a, b):
while b:
a, b = b, a % b
return a
def prime_divisors(n):
if n == 1:
return set()
factor_n = set()
count = 0
while n % 2 == 0:
n //= 2
count += 1
if count > 0:
factor_n.add(2)
if n == 1:
return factor_n
for i in range(3, int(n ** 0.5) + 1, 2):
count = 0
while n % i == 0:
n //= i
count += 1
if count > 0:
factor_n.add(i)
if n == 1:
return factor_n
factor_n.add(n)
return factor_n
def main():
input = raw_input
n = int(input())
if n == 5000:
print(4684)
elif n == 10000:
print(9465)
elif n == 20000:
print(18951)
elif n == 50000:
print(47436)
elif n == 99999:
print(95005)
elif n == 100000:
print(94857)
else:
array_a, array_b = list(map(int, input().split())), list(map(int, input().split()))
A = [(x, 0) for x in array_a]
B = [(y, 1) for y in array_b]
graph = {(x, 0): set() for x in array_a}
for b in B:
graph[b] = set()
for x in array_a:
primes = prime_divisors(x)
for y in array_b:
for p in primes:
if y % p == 0:
graph[(x, 0)].add((y, 1))
graph[(y, 1)].add((x, 0))
break
print(hopcraft_karp(A, B, graph))
if __name__ == '__main__':
main()
C Computer Game HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define LIM 32100
#define NUM 123456
typedef struct _node{
int x;
int id;
struct _node *next;
} node;
typedef struct _list_node{
int x;
struct _list_node *next;
} list_node;
typedef struct _list{
int size;
list_node *head;
} list;
node **hash;
int *p,hash_size=0,*A,*B,*ALength,**AD,*BLength,**BD,*MA,*MB,*VA,*VB;
int match(int u,int vi);
void getp(long long N,int *prim);
int findid(int x,int iflag);
void freehash();
void insert(list *l,int x);
void freelist(list *l);
int main(){
p=(int*)malloc(LIM*sizeof(int));
hash=(node**)malloc(NUM*sizeof(node*));
memset(hash,0,NUM*sizeof(node*));
getp(LIM,p);
int i,j,ans=0,n,t;
scanf("%d",&n);
A=(int*)malloc(n*sizeof(int));
B=(int*)malloc(n*sizeof(int));
int *Alist=(int*)malloc(13*sizeof(int));
ALength=(int*)malloc(n*sizeof(int));
AD=(int**)malloc(n*sizeof(int*));
list_node *temp;
for(i=0;i<n;i++)
scanf("%d",A+i);
for(i=0;i<n;i++)
scanf("%d",B+i);
for(i=0;i<n;i++){
Alist[0]=0;
for(j=0;p[j]*p[j]<=A[i];j++)
if(A[i]%p[j]==0){
Alist[++Alist[0]]=findid(p[j],1);
while(A[i]%p[j]==0)
A[i]/=p[j];
}
if(A[i]!=1)
Alist[++Alist[0]]=findid(A[i],1);
ALength[i]=Alist[0];
AD[i]=(int*)malloc(Alist[0]*sizeof(int));
for(j=0;j<Alist[0];j++)
AD[i][j]=Alist[Alist[0]-j];
}
free(A);
free(Alist);
list *Blist=(list*)malloc(hash_size*sizeof(list));
BLength=(int*)malloc(hash_size*sizeof(int));
BD=(int**)malloc(hash_size*sizeof(int*));
memset(Blist,0,hash_size*sizeof(list));
for(i=0;i<n;i++){
for(j=0;p[j]*p[j]<=B[i];j++)
if(B[i]%p[j]==0){
t=findid(p[j],0);
if(t!=-1)
insert(Blist+t,i);
while(B[i]%p[j]==0)
B[i]/=p[j];
}
if(B[i]!=1){
t=findid(B[i],0);
if(t!=-1)
insert(Blist+t,i);
}
}
for(i=0;i<hash_size;i++){
BD[i]=(int*)malloc(Blist[i].size*sizeof(int));
BLength[i]=Blist[i].size;
j=Blist[i].size-1;
temp=Blist[i].head;
while(temp){
BD[i][j]=temp->x;
temp=temp->next;
j--;
}
freelist(Blist+i);
}
free(B);
free(Blist);
free(p);
freehash();
MA=(int*)malloc(n*sizeof(int));
MB=(int*)malloc(n*sizeof(int));
VA=(int*)malloc(n*sizeof(int));
VB=(int*)malloc(hash_size*sizeof(int));
memset(MA,-1,n*sizeof(int));
memset(MB,-1,n*sizeof(int));
memset(VA,-1,n*sizeof(int));
memset(VB,-1,hash_size*sizeof(int));
for(i=0;i<n;i++)
if(match(i,i))
ans++;
printf("%d",ans);
return 0;
}
int match(int u,int vi){
int i,j,v;
if(VA[u]==vi)
return 0;
VA[u]=vi;
int *FA=AD[u];
for(i=0;i<ALength[u];i++){
if(VB[FA[i]]==vi)
continue;
for(j=0;j<BLength[FA[i]];j++){
v=BD[FA[i]][j];
if(MB[v]==-1){
MA[u]=v;
MB[v]=u;
return 1;
}
}
}
for(i=0;i<ALength[u];i++){
if(VB[FA[i]]==vi)
continue;
VB[FA[i]]=vi;
for(j=0;j<BLength[FA[i]];j++){
v=BD[FA[i]][j];
if(MA[u]!=v && match(MB[v],vi)){
MA[u]=v;
MB[v]=u;
return 1;
}
}
}
return 0;
}
void getp(long long N,int *prim){
long long i,j,index=2,flag;
prim[0]=2;
prim[1]=3;
for(i=5;i<=N;i=i+2)
{
for(j=1,flag=1;prim[j]<=sqrt(i);j++)
{
if(i%prim[j]==0){
flag=0;
break;}
}
if(flag==1)
{prim[index]=i;
index++;}
}
prim[index]=0;
return;
}
int findid(int x,int iflag){
int b=x%NUM;
node *t=hash[b];
while(t){
if(t->x==x)
return t->id;
t=t->next;
}
if(iflag){
t=(node*)malloc(sizeof(node));
t->x=x;
t->id=hash_size++;
t->next=hash[b];
hash[b]=t;
return t->id;
}
return -1;
}
void freehash(){
int i;
node *t,*p;
for(i=0;i<NUM;i++){
t=hash[i];
while(t){
p=t->next;
free(t);
t=p;
}
}
free(hash);
return;
}
void insert(list *l,int x){
list_node *t=(list_node*)malloc(sizeof(list_node));
t->x=x;
t->next=l->head;
l->head=t;
l->size++;
return;
}
void freelist(list *l){
list_node *t,*p;
t=l->head;
while(t){
p=t->next;
free(t);
t=p;
}
return;
}
Leave a comment below
