Table of Contents
ByteLandian Tours – 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++ ByteLandian Tours HackerRank Solution
#include<iostream>
#include<vector>
#include<stdio.h>
#include<set>
#include<string.h>
#include<stdlib.h>
using namespace std ;
#define INF (int)1e9
#define MOD 1000000007
#define MAXN 10002
vector<int> G[MAXN] ;
int n ;
void form_graph(int prufer[])
{
int i,j,k,degree[MAXN] ;
for(i=0;i<n;i++) degree[i] = 1 ;
for(i=0;i<n-2;i++) degree[prufer[i]]++ ;
for(i=0;i<MAXN;i++) G[i].clear() ;
for(i=0;i<n-2;i++)
{
for(j=0;degree[j] != 1;j++) ;
G[j].push_back(prufer[i]) ;
G[prufer[i]].push_back(j) ;
degree[j] -- ;
degree[prufer[i]] -- ;
}
for(i=0;degree[i] != 1;i++) ;
for(j=i+1;degree[j] != 1;j++) ;
G[i].push_back(j) ;
G[j].push_back(i) ;
}
void generate(int N)
{
int prufer[MAXN] ;
n = N ;
for(int i = 0;i < n - 2;i++) prufer[i] = rand() % n ;
form_graph(prufer) ;
}
int perm[MAXN] ;
void generateCaterpiller(int N,int path)
{
n = N ;
for(int i = 0;i < MAXN;i++) G[i].clear() ;
for(int i = 0;i < n;i++) perm[i] = i ;
for(int i = 0;i < n;i++)
{
int j = i + rand() % (n - i) ;
swap(perm[i],perm[j]) ;
}
if(path > n) path = n ;
for(int i = 0;i + 1 < path;i++)
{
G[perm[i]].push_back(perm[i + 1]) ;
G[perm[i + 1]].push_back(perm[i]) ;
}
for(int i = path;i < n;i++)
{
int k = rand() % path ;
G[perm[k]].push_back(perm[i]) ;
G[perm[i]].push_back(perm[k]) ;
}
}
void generateAlmostCaterpiller(int N,int path,int dangle)
{
n = N ;
for(int i = 0;i < MAXN;i++) G[i].clear() ;
for(int i = 0;i < n;i++) perm[i] = i ;
for(int i = 0;i < n;i++)
{
int j = i + rand() % (n - i) ;
swap(perm[i],perm[j]) ;
}
if(path > n) path = n ;
for(int i = 0;i + 1 < path;i++)
{
G[perm[i]].push_back(perm[i + 1]) ;
G[perm[i + 1]].push_back(perm[i]) ;
}
for(int i = path;i + dangle < n;i++)
{
int k = rand() % path ;
G[perm[k]].push_back(perm[i]) ;
G[perm[i]].push_back(perm[k]) ;
}
for(int i = n - dangle;i < n;i++)
{
int k = rand() % i ;
G[perm[k]].push_back(perm[i]) ;
G[perm[i]].push_back(perm[k]) ;
}
}
int dist[22][22] ;
int memo[15][1 << 15] ;
int brute(int k,int mask)
{
if(mask == 0) return dist[k][0] <= 2 ? 1 : 0 ;
if(memo[k][mask] != -1) return memo[k][mask] ;
int ret = 0 ;
for(int i = 0;i < n;i++) if(mask & 1 << i)
if(dist[k][i] <= 2)
{
int cret = brute(i,mask ^ 1 << i) ;
ret += cret ;
if(ret >= MOD) ret -= MOD ;
}
return memo[k][mask] = ret ;
}
int brute()
{
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
dist[i][j] = i == j ? 0 : INF ;
for(int i = 0;i < n;i++)
for(int j = 0;j < G[i].size();j++)
dist[i][G[i][j]] = dist[G[i][j]][i] = 1 ;
for(int k = 0;k < n;k++)
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]) ;
memset(memo,255,sizeof memo) ;
int ret = brute(0,(1 << n) - 2) ;
return ret ;
}
char isLeaf[MAXN] ;
int fac[MAXN] ;
int solve()
{
int ret = 1,path = n ;
for(int i = 0;i < n;i++) path -= isLeaf[i] = G[i].size() == 1 ;
for(int i = 0;i < n;i++) if(!isLeaf[i])
{
int ct = 0,ct2 = 0 ;
for(int j = 0;j < G[i].size();j++)
if(!isLeaf[G[i][j]])
ct++ ;
else ct2++ ;
if(ct > 2) return 0 ;
ret = 1LL * ret * fac[ct2] % MOD ;
}
return path == 1 ? ret : 2 * ret % MOD ;
}
void test()
{
for(int t = 1;t <= 10000;t++)
{
generate(15) ;
// cout << "Case: " << t << endl ;
int ret1 = brute() ;
int ret2 = solve() ;
cout << ret1 << " " << ret2 << endl ;
if(ret1 != ret2)
{
cout << "failed on case: " << t << endl ;
cout << ret1 << " " << ret2 << endl ;
cout << n << endl ;
char vis[102][102] ;
memset(vis,0,sizeof vis) ;
for(int i = 0;i < n;i++)
for(int j = 0;j < G[i].size();j++) if(!vis[i][G[i][j]])
{
cout << i << " " << G[i][j] << endl ;
vis[i][G[i][j]] = vis[G[i][j]][i] = true ;
}
while(1) ;
}
}
cout << "Done" << endl ;
}
typedef pair<int,int> P ;
void testGen()
{
char in[10] = "in .txt" ;
for(int test = 0;test < 10;test++)
{
in[2] = test + '0' ;
FILE * fout = fopen(in,"w") ;
int runs = 20 ;
fprintf(fout,"%d\n",runs) ;
for(int t = 0;t < runs;t++)
{
int N ;
if(test < 3) generate(10) ;
else if(test < 7)
{
N = rand() % 9999 + 2 ;
if(t < 10) generateCaterpiller(N,rand() % 10 + 1) ;
else generateCaterpiller(N,rand() % (2 * N / 3) + 1) ;
}
else if(test < 9)
{
N = rand() % 9999 + 2 ;
if(rand() % 2) generateAlmostCaterpiller(N,rand() % N + 1,5) ;
else generateCaterpiller(N,rand() % (2 * N / 3) + 1) ;
}
else generate(rand() % 1000 + 2) ;
fprintf(fout,"%d\n",n) ;
set<pair<int,int> > vis ;
for(int i = 0;i < n;i++)
for(int j = 0;j < G[i].size();j++)
{
P cur = P(i,G[i][j]) ;
if(vis.find(cur) == vis.end())
{
fprintf(fout,"%d %d\n",i,G[i][j]) ;
vis.insert(cur) ;
swap(cur.first,cur.second) ;
vis.insert(cur) ;
}
}
}
}
}
void genMakefile()
{
for(int test = 0;test < 100;test++)
{
printf("./a.out < in%d%d.txt > out%d%d.txt\n",test / 10,test % 10,test / 10,test % 10) ;
}
}
int par[MAXN] ;
int fn(int k) { return k == par[k] ? k : par[k] = fn(par[k]) ; }
int main()
{
fac[0] = 1 ;
for(int i = 1;i < MAXN;i++) fac[i] = 1LL * i * fac[i - 1] % MOD ;
// genMakefile() ; return 0 ;
// testGen() ; return 0 ;
// test() ; return 0 ;
int runs ;
scanf("%d",&runs) ;
while(runs--)
{
scanf("%d",&n) ;
for(int i = 0;i < MAXN;i++) G[i].clear() ;
for(int i = 0;i < n;i++) par[i] = i ;
for(int i = 1;i < n;i++)
{
int a,b ;
scanf("%d%d",&a,&b) ;
if(a < 0 || a >= n || b < 0 || b >= n || fn(a) == fn(b)) { cout << "Bad input" << endl ; return 1 ; }
par[fn(a)] = fn(b) ;
G[a].push_back(b) ;
G[b].push_back(a) ;
}
int ret = solve() ;
printf("%d\n",ret) ;
}
return 0 ;
}
Java ByteLandian Tours HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
public class Solution {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static long[] F = new long[10001];
static void solve()
{
F[0] = 1;
for(int i = 1;i <= 10000;i++){
F[i] = F[i-1] * i % mod;
}
for(int T = ni();T >= 1;T--){
int n = ni();
int[] f = new int[n-1];
int[] t = new int[n-1];
for(int i = 0;i < n-1;i++){
f[i] = ni();
t[i] = ni();
}
if(n == 2){
out.println(0);
continue;
}
if(n == 1){
out.println(1);
continue;
}
int[][] g = packU(n, f, t);
int[][] pars = parents(g, 0);
int[] par = pars[0];
int[] ord = pars[1];
int[] des = new int[n];
for(int i = n-1;i >= 0;i--){
int cur = ord[i];
int max = 0;
for(int e : g[cur]){
if(par[cur] != e){
max = Math.max(max, des[e]+1);
}
}
des[cur] = max;
}
int root = 0;
if(g[0].length == 1 && g[g[0][0]].length >= 2){
root = g[0][0];
}
int over = 0;
for(int e : g[root]){
if(par[root] != e && des[e] > 0)over++;
}
long r;
if(over >= 3){
r = 0;
}else if(over == 0){
r = F[g[root].length];
}else{
r = 2*F[g[root].length-over];
for(int e : g[root]){
if(par[root] != e){
r = r * rec(e, g, par, des) % mod;
}
}
}
out.println(r);
}
}
static long mod = 1000000007;
static long rec(int cur, int[][] g, int[] par, int[] des)
{
int oo = -1;
int one = 0;
for(int e : g[cur]){
if(par[cur] != e){
if(des[e] > 0){
if(oo != -1)return 0;
oo = e;
}else{
one++;
}
}
}
if(oo != -1){
return rec(oo, g, par, des) * F[one] % mod;
}else{
return F[one];
}
}
public static int[][] parents(int[][] g, int root)
{
int n = g.length;
int[] par = new int[n];
Arrays.fill(par, -1);
int[] q = new int[n];
q[0] = root;
for(int p = 0, r = 1;p < r;p++) {
int cur = q[p];
for(int nex : g[cur]){
if(par[cur] != nex){
q[r++] = nex;
par[nex] = cur;
}
}
}
return new int[][] {par, q};
}
public static int[][] packU(int n, int[] from, int[] to)
{
int[][] g = new int[n][];
int[] p = new int[n];
for(int f : from)p[f]++;
for(int t : to)p[t]++;
for(int i = 0;i < n;i++)g[i] = new int[p[i]];
for(int i = 0;i < from.length;i++){
g[from[i]][--p[from[i]]] = to[i];
g[to[i]][--p[to[i]]] = from[i];
}
return g;
}
public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
static boolean eof()
{
try {
is.mark(1000);
int b;
while((b = is.read()) != -1 && !(b >= 33 && b <= 126));
is.reset();
return b == -1;
} catch (IOException e) {
return true;
}
}
static int ni()
{
try {
int num = 0;
boolean minus = false;
while((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'));
if(num == '-'){
num = 0;
minus = true;
}else{
num -= '0';
}
while(true){
int b = is.read();
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
}
} catch (IOException e) {
}
return -1;
}
static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
Python 3 ByteLandian Tours HackerRank Solution
import math
def tours(adj, N):
facts = [0]*N
z=0
for i in range(len(adj)):
vertList = adj[i]
z_count = 0
nz_count = 0
for neighbor in vertList:
if len(adj[neighbor]) == 1:
facts[i] += 1
z_count += 1
z+= 1
else:
nz_count += 1
if nz_count > 2:
return 0
sum = 1
for num in facts:
sum = (sum * math.factorial(num)) % 1000000007
if z == N-1:
return sum
return (2*sum)% 1000000007
T = int(input())
for i in range(T):
N = int(input())
adj = [[] for i in range(N)]
for x in range(1, N):
road = list(map(int,input().split()))
adj[road[0]].append(road[1])
adj[road[1]].append(road[0])
print(tours(adj, N))
Python 2 ByteLandian Tours HackerRank Solution
import Queue
from math import factorial as fac
from copy import copy
def bfs(graph,start,end,N):
n=0
q=Queue.Queue()
path=[start]
q.put(path)
while not q.empty():
path=q.get()
last_node=path[-1]
if len(path)==N:
if end in graph[last_node]:
n+=1
else:
for node in graph[last_node]:
if node not in path:
q.put(path+[node])
return n
T=int(raw_input())
for i in xrange(T):
isLeaf={}
cMap={}
N=int(raw_input())
for j in xrange(N-1):
c1,c2 = map(int,raw_input().split())
try:
cMap[c1]
except KeyError:
cMap[c1]=[]
try:
cMap[c2]
except KeyError:
cMap[c2]=[]
cMap[c1].append(c2)
cMap[c2].append(c1)
path=N
ret=1
for each in cMap:
isLeaf[each]=len(cMap[each])==1
path-=isLeaf[each]
for each in cMap:
c=0
c2=0
for node in cMap[each]:
if isLeaf[node]:
c+=1
else:
c2+=1
if c2>2:
path=-1
ret=1*ret*fac(c) % 1000000007
if path==-1:
print 0
elif path==1:
print ret
else:
print 2*ret% 1000000007
C ByteLandian Tours HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007
typedef struct _node{
int x;
struct _node *next;
} node;
void add_edge(int x,int y);
void clean();
int d[10000],N;
long long fac[10001];
node *list[10000]={0};
int main(){
int T,x,y,n,c1,c2,i;
long long ans;
node *p;
fac[0]=fac[1]=1;
for(i=2;i<10001;i++)
fac[i]=i*fac[i-1]%MOD;
scanf("%d",&T);
while(T--){
ans=1;
n=0;
scanf("%d",&N);
for(i=0;i<N;i++)
d[i]=0;
for(i=0;i<N-1;i++){
scanf("%d%d",&x,&y);
add_edge(x,y);
d[x]++;
d[y]++;
}
for(i=0;i<N;i++)
if(d[i]!=1){
n++;
c1=c2=0;
for(p=list[i];p;p=p->next)
if(d[p->x]==1)
c1++;
else
c2++;
if(c2>2){
ans=0;
break;
}
else
ans=ans*fac[c1]%MOD;
}
if(n>1)
ans=2*ans%MOD;
printf("%lld\n",ans);
clean();
}
return 0;
}
void add_edge(int x,int y){
node *p1,*p2;
p1=(node*)malloc(sizeof(node));
p2=(node*)malloc(sizeof(node));
p1->x=y;
p1->next=list[x];
list[x]=p1;
p2->x=x;
p2->next=list[y];
list[y]=p2;
return;
}
void clean(){
node *p1,*p2;
int i;
for(i=0;i<N;i++)
if(list[i]){
p1=list[i];
while(p1){
p2=p1;
p1=p1->next;
free(p2);
}
list[i]=NULL;
}
return;
}
Leave a comment below
