Tree Pruning – 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 <fstream>
#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
const int NMAX = 100004;
const long long INF = 1LL<<60;
vector <int> Tree[NMAX], Level[NMAX];
long long dp[NMAX][201], sum[NMAX];
int n, Father[NMAX], v[NMAX], val[NMAX], First[NMAX], Last[NMAX], ind;
inline void DFS(const int node,const int father){
First[node] = ++ind;
v[ind] = node;
for(vector < int >::iterator it = Tree[node].begin();it != Tree[node].end();++it)
if(*it != father)
DFS(*it,node);
Last[node] = ind;
}
int main(){
int n, k;
cin.sync_with_stdio(false);
cin >> n >> k;
for(int i = 1;i <= n; ++i)
cin >> val[i];
for(int i=1;i<n;++i){
int x,y;
cin >> x >> y;
Tree[x].push_back(y);
Tree[y].push_back(x);
}
DFS(1,0);
for(int i = 1;i <= n; ++i){
for(int j=0;j<=k;++j)
dp[i][j] = -INF;
}
dp[1][0] = 0;
for(int i = 1;i <= n; ++i)
{
int node = v[i];
for(int j = 0;j <= k; ++j)
if(dp[i][j]!=-INF)
{
dp[i + 1][j] =max(dp[i+1][j],dp[i][j]+val[node]);
if(j+1<=k)
dp[Last[node]+1][j+1] = max(dp[i][j],dp[Last[node]+1][j+1]);
}
}
long long sol = 0;
for(int j = 0;j <= k;++j)
sol = max(sol,dp[n+1][j]);
cout<<sol<<"\n";
return 0;
}
Java rep HackerRank Solution
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
public class HR_tree_pruning {
public static final long MINF = -1000000000000000000L;
public static void solve(Input in, PrintWriter out) throws IOException {
int n = in.nextInt();
int k = in.nextInt();
long[] w = new long[n];
// Random rnd = new Random();
ArrayList<Integer>[] edges = new ArrayList[n];
for (int i = 0; i < n; ++i) {
w[i] = in.nextLong();
// w[i] = rnd.nextInt();
edges[i] = new ArrayList<Integer>();
}
for (int i = 0; i < n - 1; ++i) {
int u = in.nextInt() - 1;
int v = in.nextInt() - 1;
// int u = i + 1;
// int v = rnd.nextInt(i + 1);
edges[u].add(v);
edges[v].add(u);
}
int[] inOrder = new int[n];
int[] next = new int[n];
dfs(0, -1, edges, 0, inOrder, next, w);
long[][] d = new long[k + 1][n + 1];
for (long[] ar : d) {
Arrays.fill(ar, MINF);
}
d[0][0] = w[0];
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= k; ++j) {
d[j][i + 1] = Math.max(d[j][i + 1], d[j][i]);
if (j + 1 <= k) {
d[j + 1][next[i]] = Math.max(d[j + 1][next[i]], d[j][i] - w[inOrder[i]]);
}
}
}
long ans = MINF;
for (int i = 0; i <= k; ++i) {
ans = Math.max(ans, d[i][n]);
}
out.println(ans);
}
private static int dfs(int i, int p, ArrayList<Integer>[] edges, int it, int[] inOrder, int[] next, long[] w) {
int it0 = it++;
inOrder[it0] = i;
for (int j : edges[i]) {
if (j != p) {
it = dfs(j, i, edges, it, inOrder, next, w);
w[i] += w[j];
}
}
next[it0] = it;
return it;
}
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
#!/bin/python3
import os
import sys
#
# Complete the treePrunning function below.
#
from collections import defaultdict
INF = -(1e15)
def dfs(x, f, g, k, weights):
dpc = [INF]*(k+1)
dpc[0] = weights[x]
for n in g[x]:
if n == f:
continue
dpn = dfs(n, x, g, k, weights)
dptmp = [INF]*(k+1)
for i in range(k+1):
if dpc[i] == INF:
break
for j in range(0, k-i+1):
if dpn[j] == INF:
break
dptmp[i+j] = max(dptmp[i+j], dpc[i]+dpn[j])
if i+1 <= k:
dptmp[i+1] = max(dptmp[i+1], dpc[i])
dpc = dptmp
return dpc
def treePrunning(k,weights,edges):
g = defaultdict(list)
for u, v in edges:
g[u-1].append(v-1)
g[v-1].append(u-1)
dpn = dfs(0, -1, g, k, weights)
return max(max(dpn),0)
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
nk = input().split()
n = int(nk[0])
k = int(nk[1])
weights = list(map(int, input().rstrip().split()))
tree = []
for _ in range(n-1):
tree.append(list(map(int, input().rstrip().split())))
result = treePrunning(k, weights, tree)
fptr.write(str(result) + '\n')
fptr.close()
Python 2 rep HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
from array import array
import time as tm
import sys
def ptime():
print tm.clock()-ptime.t
class child():
max_op=0
wghts=[]
srch=[]
rmndr=[]
usedn=[]
srch_or_rmdr=0
p_num=0
all_chlds_cntr=0
all_chlds=[]
isinit=False
chldless=[]
parent=None
@classmethod
def init_c (cls, wghts,pairs, max_op):
if cls.isinit: return
cls.wghts=array('l',wghts)
cls.p_num=len(pairs)
cls.srch=pairs[:]
cls.rmndr=pairs[:]
cls.srch_rmndr=[cls.srch,cls.rmndr]
#cls.all_chlds=[None]*len(wghts)
cls.isinit=True
cls.all_summ_wght=sum(wghts)
#cls.op_max_wght=[None]*(len(wghts)+1)
cls.max_op=max_op
cls.num_all_chlds=len(cls.wghts)
cls.all_chlds=[child(i) for i in xrange(cls.num_all_chlds) ]
[[cls.all_chlds[it1-1].linkto(it2-1), cls.all_chlds[it2-1].linkto(it1-1)] for it1, it2 in cls.srch]
cls.all_chlds[0].num_links+=1
# cls.all_chlds[it1-1].linkto(it2-1)
# cls.all_chlds[it2-1].linkto(it1-1)
cls.init_chldless()
@classmethod
def init_chldless(cls):
cls.chldless=filter(lambda it: it.num_links==1, cls.all_chlds)
for ch in cls.chldless:
ch.all_wght=ch.wght
ch.op_wght=[0, ch.wght]
def linktochld(self, n):
self.num_links+=1
self.chlds.append(child.all_chlds[n])
def linkto(self, n):
if self.num_links==0:
self.num_links+=1
self.parent=child.all_chlds[n]
else:
self.chlds.append(self.parent)
self.parent=None
self.linktochld(n)
self.linkto=self.linktochld
def trim_me(self, challengs):
if self.op_wght!=None and self.op_wght[1]<0:
if self.parent.op_wght==None:
self.parent.op_wght=self.op_wght
else:
self.crossup()
self.parent.num_links-=1
self.parent.chlds.remove(self)
self.parent.all_chlds_wght+=self.all_wght
if self.parent.num_links==1:
self.parent.all_wght=self.parent.all_chlds_wght+self.parent.wght
if self.parent.all_wght<0:
if self.parent.op_wght!=None:
if self.parent.op_wght[1]>self.parent.all_wght:
self.parent.op_wght[1]=self.parent.all_wght
else:
#ch.parent.op_wght=array('l',[0,ch.parent.all_wght])
self.parent.op_wght=[0,self.parent.all_wght]
if self.parent.vert!=0:
self.parent.parent=self.parent.chlds[0]
challengs.append( self.parent)
def __init__(self, n):
self.num_links=0
self.vert=n
self.wght=child.wghts[n]
#self.parent=prnt
self.all_wght=0 # neg childs
self.all_chlds_wght=0 #
#child.usedn.append(n)
#self.num_chlds_cntr=0 # for trim countig
self.op_wght=None
self.chlds=[]
#child.all_chlds[child.all_chlds_cntr]=self
#child.all_chlds_cntr+=1
def crossup(self):
s_lmt=len(self.op_wght)-1
l_lmt=len(self.parent.op_wght)-1
if l_lmt<self.max_op:
lensl=s_lmt+l_lmt
self.parent.op_wght.extend([0]*(s_lmt if s_lmt+l_lmt<= self.max_op else self.max_op-l_lmt ) )
tmp_prnt=self.parent.op_wght[:]
if s_lmt<=l_lmt:
shrt=self.op_wght
lng=tmp_prnt
s, l= [1,0]
else:
lng=self.op_wght
shrt=tmp_prnt
s_lmt, l_lmt= l_lmt, s_lmt
s,l=[0,1]
def set_best(i ,j):
sum=shrt[i]+lng[j]
if sum<self.parent.op_wght[i+j]:
self.parent.op_wght[i+j]=sum
[set_best(i, j) for i in xrange(s,s_lmt+1) for j in xrange(l,l_lmt+1 if i+l_lmt<=self.max_op \
else self.max_op-i+1)]
@classmethod
def trim_n_get_nxt_challengs(cls, chldless):
#me=child #check me !!!!
challengs=[]
for ch in chldless:
ch.trim_me(challengs)
return challengs
@classmethod
def calc_min_op_max_wght(cls):
ch_lst=cls.chldless
while True:
ch_lst=cls.trim_n_get_nxt_challengs(ch_lst)
# print [[it.vert, it.op_wght] for it in ch_lst]
if ch_lst==[]:
break
@classmethod
def get_max_wght(cls):
tmp=0
if cls.all_chlds[0].op_wght!=None:
tmp=min(cls.all_chlds[0].op_wght[1:cls.max_op+1])
#return [cls.all_summ_wght-it for it in cls.root.op_wght]
return cls.all_summ_wght-tmp
def main():
home=0
if not home:
tr=[]
N, K =[int(it) for it in raw_input().split()]
cc=array('l', [int(it) for it in raw_input().split()] )
for _ in xrange(N-1):
tr.append([int(it) for it in raw_input().split()])
else:
with open('d:/qq.txt', 'r') as f:
tr=[]
nxtln=f.readline()
N, K =[int(it) for it in nxtln.split()]
cc=array('l', [int(it) for it in f.readline().split()] )
for _ in xrange(N-1):
tr.append([int(it) for it in f.readline().split()])
#cc=[-1,1,-1,1,-1,1,-1,1,100]
#tr=[[1,2],[2,3],[2,4], [2,5],[2,6],[1,7],[1,8],[1,9]]
#tr=[[1,2]]
#K=4
#ptime.t=tm.clock()
#ptime()
child.init_c(cc,tr,K)
#c=child(1)
#if c.gen_tree():
# print c.all_summ_wght
#else:
#print 'trgen'
#ptime()
#print ''
#c.preset()
child.calc_min_op_max_wght( )
#print 'end'
#ptime()
print child.get_max_wght()
#c.trim_n_get_nxt_challengs( [it, False])
#print [[c.parent.vert if c.parent else None, c.vert] for c in child.chldless]
"""
c.trim_chldless()
print [[c.parent.vert if c.parent else None, c.vert] for c in child.chldless]
for c in child.all_chlds:
print c.vert, c.num_chlds_cntr, c.all_chlds_wght
"""
if __name__=='__main__': main()
C rep HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
typedef struct _node{
int x;
struct _node *next;
} node;
void insert_edge(int x,int y);
void dfs(int x);
long long max(long long x,long long y);
int a[100000],b[100000],size[100000],trace[100000]={0},NN=0;
long long dp[100001][201];
node *table[100000]={0};
int main(){
int N,K,x,y,i,j;
long long sum;
scanf("%d%d",&N,&K);
for(i=0;i<N;i++)
scanf("%d",a+i);
for(i=0;i<N-1;i++){
scanf("%d%d",&x,&y);
insert_edge(x-1,y-1);
}
dfs(0);
for(i=0;i<=K;i++)
dp[0][i]=0;
for(i=1,sum=0;i<=N;i++){
sum+=b[i-1];
for(j=0;j<=K;j++)
dp[i][j]=sum;
}
for(i=1,sum=0;i<=N;i++)
for(j=0;j<=K;j++){
if(j!=K)
dp[i+size[i-1]-1][j+1]=max(dp[i+size[i-1]-1][j+1],dp[i-1][j]);
dp[i][j]=max(dp[i][j],dp[i-1][j]+b[i-1]);
}
printf("%lld",dp[N][K]);
return 0;
}
void insert_edge(int x,int y){
node *t;
t=(node*)malloc(sizeof(node));
t->x=y;
t->next=table[x];
table[x]=t;
t=(node*)malloc(sizeof(node));
t->x=x;
t->next=table[y];
table[y]=t;
return;
}
void dfs(int x){
node *t;
int i=NN;
trace[x]=1;
b[NN++]=a[x];
for(t=table[x];t;t=t->next)
if(!trace[t->x])
dfs(t->x);
size[i]=NN-i;
return;
}
long long max(long long x,long long y){
return (x>y)?x:y;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below