Table of Contents
Matrix – 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++ Matrix HackerRank Solution
#include<iostream>
#include<vector>
#include<cstring>
#include<cstdio>
#include<list>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<fstream>
#include<sstream>
#include<algorithm>
#include<numeric>
#include<cmath>
#include<climits>
#include<ctime>
using namespace std;
#define rp(i,a,b) for(int i = (a); i < (b); i++)
#define rrp(i,a,b)for(int i = (b); i >= (a); i--)
#define ri(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define cl(x,with) memset(x,with,sizeof(x))
#define sz(v) (v).size()
#define ll long long int
#define ii pair<int,int>
#define mp make_pair
#define vi vector<int>
#define vs vector<string>
#define MAX 600000
int parent[MAX];
int cnt[MAX];
int mark[MAX];
int fp(int v){
while(parent[v] != v)
v = parent[v];
return v;
}
bool unite(int x, int y){
int p1 = fp(x);
int p2 = fp(y);
if(p1 != p2 && !(mark[p1] == 1 && mark[p2] == 1)){
if(cnt[p1] > cnt[p2]){
parent[p2] = p1;
cnt[p1] += cnt[p2];
if(mark[p1] == 1 || mark[p2] == 1)
mark[p1] = 1;
}
else{
parent[p1] = p2;
cnt[p2] += cnt[p1];
if(mark[p1] == 1 || mark[p2] == 1)
mark[p2] = 1;
}
return 1;
}
return 0;
}
int main(){
int n, m, k;
cin >> n >> k; m = n-1;
vector< pair<int, pair<int,int> > >edge;
int wt = 0;
rp(i,0,n-1){
int x,y,z;
cin >> x >> y >> z;
wt += z;
edge.pb(mp(z,mp(x,y)));
}
sort(all(edge));
reverse(all(edge));
int tmp;
rp(i,0,n){
mark[i] = 0;
parent[i] = i;
}
rp(i,0,k){
cin >> tmp;
mark[tmp] = 1;
}
rp(i,0,n-1){
int x,y,z;
x = edge[i].second.first;
y = edge[i].second.second;
z = edge[i].first;
bool res = unite(x,y);
wt -= res*z;
}
cout << wt << "\n";
return 0;
}
Java Matrix HackerRank Solution
import java.util.*;
import java.io.*;
import static java.lang.Math.*;
public class Solution {
static class Foo51 {
static class Node {
boolean hasMachine;
int weightOfParent;
ArrayList<Integer> child = new ArrayList<Integer>();
ArrayList<Integer> weight = new ArrayList<Integer>();
}
Node[] nodes;
int N;
void main() {
BufferedReader br = null;
try {
br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().trim().split(" ");
N = Integer.parseInt(s[0].trim());
int K = Integer.parseInt(s[1].trim());
nodes = new Node[N];
for (int i = 0; i < N; i++) nodes[i] = new Node();
for (int i = 0; i < N-1; i++) {
s = br.readLine().trim().split(" ");
int a = Integer.parseInt(s[0].trim());
int b = Integer.parseInt(s[1].trim());
int weight = Integer.parseInt(s[2].trim());
nodes[a].child.add(b);
nodes[a].weight.add(weight);
nodes[b].child.add(a);
nodes[b].weight.add(weight);
}
for (int i = 0; i < K; i++) {
int a = Integer.parseInt(br.readLine().trim());
nodes[a].hasMachine = true;
}
long res = foo();
System.out.println(res);
} catch (Exception e) {
e.printStackTrace();
} finally {
if (br != null) {
try { br.close(); } catch (Exception e) { e.printStackTrace(); }
}
}
}
long foo() {
return doit(0, -1)[1];
}
long[] doit(int current, int parent) {
long[] res = new long[2];
Node curr = nodes[current];
if (current != 0 && nodes[current].child.size() == 1) {
// leaf
if (curr.hasMachine)
res[0] = nodes[current].weight.get(0);
return res;
}
int childNum = curr.child.size()-1;
if (current == 0)
childNum++;
long[][] child = new long[childNum][];
int index = 0;
for (int i = 0; i < curr.child.size(); i++) {
int childId = curr.child.get(i);
if (parent != childId) {
nodes[childId].weightOfParent = curr.weight.get(i);
child[index++] = doit(childId, current);
}
}
if (curr.hasMachine) {
for (int i = 0; i < childNum; i++) {
res[1] += child[i][0];
}
res[0] = res[1] + curr.weightOfParent;
} else {
long maxDiff = 0;
for (int i = 0; i < childNum; i++)
maxDiff = max(maxDiff, child[i][0]-child[i][1]);
long cost = 0;
for (int i = 0; i < childNum; i++)
cost += child[i][0];
res[0] = min(cost, cost-maxDiff+curr.weightOfParent);
res[1] = cost-maxDiff;
}
return res;
}
}
public static void main(String[] args) {
Foo51 foo = new Foo51();
foo.main();
}
}
Python 3 Matrix HackerRank Solution
import random
#random.seed(0)
def Find( uf, u ):
if uf[ u ] != u:
uf[ u ] = Find( uf, uf[ u ])
return uf[ u ]
def Sol( E, mlocs, N ):
uf = list(range(N))
E = sorted(E)
res = 0#MaxST = set()
while E:
w,u,v = E.pop()
#print(w,u,v, uf, mlocs)
if Find( uf, u ) in mlocs and Find( uf, v ) in mlocs: res += w; continue
if random.randint(0,1):
if Find( uf, u ) in mlocs: mlocs.add( Find( uf, v ) )
uf[ Find( uf, u ) ] = Find( uf, v )
else:
if Find( uf, v ) in mlocs: mlocs.add( Find( uf, u ) )
uf[ Find( uf, v ) ] = Find( uf, u )
#MaxST.add( (w,u,v) )
return res
N, K = map(int, input().split())
E = set()
mlocs = set()
for _ in range(N-1):
u,v,w = map(int,input().split())
E.add( (w, u, v) )
for _ in range(K):
u = int(input())
mlocs.add( u )
print( Sol( E, mlocs, N ))
#print(mlocs, E)
Python 2 Matrix HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
#!/usr/bin/python
def memo(f):
save = {}
def func(*args):
if args in save:
return save[args]
ret = f(*args)
save[args] = ret
return ret
return func
@memo
def f(root, parent): # cut all
ret = 0
for x, w in sub[root]:
if x == parent:
continue
if bad[x]:
ret += w + f(x, root)
else:
ret += min(w + g(x, root), f(x, root))
return ret
@memo
def g(root, parent): # root is good: cut all but one bad
s = f(root, parent)
ret = 10**100
for x, w in sub[root]:
if x == parent:
continue
if bad[x]:
delta = -w
else:
delta = g(x, root) - min(w + g(x, root), f(x, root))
now = s + delta
if now < ret:
ret = now
return ret
getnums = lambda: map(int, raw_input().strip().split())
n, k = getnums()
sub = [[] for x in xrange(n)]
bad = [False] * n
for x in xrange(n-1):
a, b, w = getnums()
sub[a].append((b, w))
sub[b].append((a, w))
for x in xrange(k):
a = input()
bad[a] = True
if bad[0]:
print f(0, -1)
else:
print min(f(0, -1), g(0, -1))
C Matrix HackerRank Solution
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <stdio.h>
#include <stdlib.h>
void trace(int*x_list,int*y_list,int*w_list,int index,int*track,int*i_list,int last_index,int min,long long*ans,int list_size,int*flag,int x_remove,int y_remove,int*x_r,int*y_r);
void sort_a(int*a,int*b,int*c,int size);
void merge(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size, int right_size);
int main ()
{
int i,j,N,K,x,y,w,x_remove,y_remove,flag;
long long ans=0;
scanf("%d%d",&N,&K);
int*x_list,*y_list,*w_list,*track,*i_list,*k_list;
x_list=(int*)malloc(2*(N-1)*sizeof(int));
y_list=(int*)malloc(2*(N-1)*sizeof(int));
w_list=(int*)malloc(2*(N-1)*sizeof(int));
i_list=(int*)malloc(N*sizeof(int));
k_list=(int*)malloc(K*sizeof(int));
track=(int*)malloc(N*sizeof(int));
for(i=0;i<N;i++)
track[i]=0;
for(i=0;i<N-1;i++){
scanf("%d%d%d",&x,&y,&w);
x_list[2*i]=x;
y_list[2*i]=y;
w_list[2*i]=w;
x_list[2*i+1]=y;
y_list[2*i+1]=x;
w_list[2*i+1]=w;
}
for(i=0;i<K;i++){
scanf("%d",&k_list[i]);
track[k_list[i]]=1;
}
sort_a(x_list,y_list,w_list,2*(N-1));
for(i=0;i<2*(N-1);i++)
if(i==0||x_list[i]!=x_list[i-1])
i_list[x_list[i]]=i;
for(i=0;i<K;i++){
while(1){
flag=1;
trace(x_list,y_list,w_list,k_list[i],track,i_list,-1,0,&ans,2*(N-1),&flag,0,0,&x_remove,&y_remove);
if(flag==0){
for(j=i_list[x_remove];j>=0&&j<2*(N-1)&&x_list[j]==x_remove;j++)
if(y_list[j]==y_remove){
y_list[j]=-1;
break;
}
for(j=i_list[y_remove];j>=0&&j<2*(N-1)&&x_list[j]==y_remove;j++)
if(y_list[j]==x_remove){
y_list[j]=-1;
break;
}
}
else break;
}
}
printf("%lld\n",ans);
return 0;
}
void trace(int*x_list,int*y_list,int*w_list,int index,int*track,int*i_list,int last_index,int min,long long*ans,int list_size,int*flag,int x_remove,int y_remove,int*x_r,int*y_r)
{
if((*flag)==0)
return;
int i;
if(track[index]&&min!=0){
(*ans)+=min;
(*flag)=0;
(*x_r)=x_remove;
(*y_r)=y_remove;
return;
}
for(i=i_list[index];i>=0&&i<list_size&&x_list[i]==index;i++)
if(y_list[i]==last_index||y_list[i]==-1)
continue;
else if(w_list[i]<min||track[index])
trace(x_list,y_list,w_list,y_list[i],track,i_list,index,w_list[i],ans,list_size,flag,x_list[i],y_list[i],x_r,y_r);
else
trace(x_list,y_list,w_list,y_list[i],track,i_list,index,min,ans,list_size,flag,x_remove,y_remove,x_r,y_r);
return;
}
void sort_a(int*a,int*b,int*c,int size)
{
if (size < 2)
return;
int m = (size+1)/2,i;
int*left_a,*left_b,*left_c,*right_a,*right_b,*right_c;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
left_c=(int*)malloc(m*sizeof(int));
right_c=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
left_c[i]=c[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
right_c[i]=c[i+m];
}
sort_a(left_a,left_b,left_c,m);
sort_a(right_a,right_b,right_c,size-m);
merge(a,left_a,right_a,b,left_b,right_b,c,left_c,right_c,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
free(left_c);
free(right_c);
return;
}
void merge(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size, int right_size)
{
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else if (left_a[i] <= right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
}
}
return;
}
Leave a comment below
