Table of Contents
Repair Roads – 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++ Repair Roads HackerRank Solution
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 10000
int memo[MAXN][3];
vector<int> E[MAXN];
int solve(int x, int froot, int p) {
int& ref = memo[x][froot];
if(ref != -1) return ref;
ref = froot == 1 ? 0 : 1;
int children = 0;
vector<int> C;
for(int i = 0; i < E[x].size(); i++) {
int v = E[x][i];
if(v == p) continue;
int res = solve(v, 0, x);
ref += res;
C.push_back(solve(v, 1, x) - res);
children++;
}
sort(C.begin(), C.end());
int r1 = ref;
int charge = (froot == 1 ? 1 : 2);
for(int i = 0; i < C.size(); i++) {
r1 += C[i];
if(i == charge) {
r1++;
charge += 2;
}
ref = min(ref, r1);
}
if(children == 0 && froot != 2) {
ref = 0;
}
//cout << x << ", " << froot << ", " << ref << " (" << C.size() << ")" << endl;
if(froot == 0) {
int r2 = 0;
for(int i = 0; i < E[x].size(); i++) {
int v = E[x][i];
if(v == p) continue;
r2 += solve(v, 2, x);
}
ref = min(ref, r2);
}
return ref;
}
int main() {
int T; cin >> T;
for(int t = 1; t <= T; t++) {
int N; cin >> N;
for(int i = 0; i < N; i++) E[i].clear();
for(int i = 1; i < N; i++) {
int u, v; cin >> u >> v;
E[u].push_back(v);
E[v].push_back(u);
}
memset(memo, -1, sizeof(memo));
cout << solve(0, false, -1) << endl;
}
}
Java Repair Roads HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.FileInputStream;
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 void solve()
{
for(int T = ni();T >= 1;T--){
int n = ni();
int[] from = new int[n-1];
int[] to = new int[n-1];
for(int i = 0;i < n-1;i++){
from[i] = ni();
to[i] = ni();
}
int[][] g = packU(n, from, to);
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 d = 0;
for(int e : g[cur]){
if(par[cur] != e)d = Math.max(d, des[e]);
}
des[cur] = d + 1;
}
int[][] dp = new int[n][2]; // not extended, extended
boolean[] ex = new boolean[n];
for(int i = n-1;i >= 0;i--){
int cur = ord[i];
int ct = 0;
int sdp = 0;
int sh = 0;
boolean onch = false;
for(int e : g[cur]){
if(par[cur] != e){
// if(cur == 11)tr(e, des[e], dp[e], ex[e]);
if(des[e] >= 2){
if(ex[e]){
ct++;
sdp += dp[e][1]-1;
}else{
sdp += dp[e][1];
}
sh++;
}else{
sdp += dp[e][0];
onch = true;
}
}
}
// if(cur == 11){
// tr(sdp, sh, onch);
// }
// 0 1 ex
// 1 1 ex
// 2 1 noex
// 3 2 ex
if(ct > 0){
dp[cur][0] = dp[cur][1] = sdp + (ct+1)/2;
if(ct%2 == 1)ex[cur] = true;
}else{
dp[cur][0] = sdp + (onch ? 1 : 0);
dp[cur][1] = sdp + 1;
ex[cur] = true;
if(!onch)des[cur] = 1;
}
// tr(cur, sdp, ct, sh, dp[cur], ex[cur]);
}
// tr(dp);
// tr(ex);
out.println(dp[0][0]);
}
}
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 };
}
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 Repair Roads HackerRank Solution
import collections
import queue
def solve():
n = int(input().strip())
# read graph
graph = dict((i, []) for i in range(0, n))
for j in range(n - 1):
x, y = [int(p) for p in input().strip().split()]
graph[x].append(y)
graph[y].append(x)
# transform graph into tree
level = 1
root = 0
q = queue.Queue()
q.put((root, level, None))
seen = set([])
levels = collections.defaultdict(set)
tree = {}
while not q.empty():
item, level, parent = q.get()
levels[level].add(item)
seen.add(item)
tree[item] = dict(id=item, parent=parent, level=level, children=set([]),
leaf=None)
for child in graph[item]:
if child not in seen:
q.put((child, level + 1, item))
seen.add(child)
tree[item]['children'].add(child)
# print('Levels: %s' % levels)
# print('Tree: %s' % tree)
# count clusters
clusters = 1
has_items_in_cluster = False
for level in sorted(levels.keys(), reverse=True):
for item in levels[level]:
tree_item = tree[item]
if not tree_item['children']: # leaf
tree_item['leaf'] = True
else:
has_items_in_cluster = True
branches = 0
for child in tree_item['children']:
if not tree[child]['leaf']:
branches += 1
# branches == 0 -> visit point and go up
# branches == 1 -> visit downstream, point and go up
# branches % 2 == 0 -> have (branches // 2) clusters
# branches % 2 == 1 -> have (branches // 2) clusters and go up
if branches >= 2:
new_clusters = branches // 2
clusters += new_clusters
# print('New clusters: %d' % new_clusters)
if branches % 2 == 0:
has_items_in_cluster = False
# cluster will also include road up
parent = tree_item['parent']
if parent is not None:
# print('Cut %s and %s' % (item, parent))
tree[parent]['children'].remove(item)
# print(tree[item])
# print('Tree: %s' % tree)
if not has_items_in_cluster:
clusters -= 1 # last cluster was created but has no items
print(clusters)
t = int(input().strip())
for tt in range(t):
solve()
C Repair Roads HackerRank Solution
#include<stdio.h>
#include<malloc.h>
#define null NULL
long count;
long n2;
long *st[2];
typedef struct N
{
long data;
struct N * next;
}node;
long adj(node **ar,long p)
{
/*long i=0;
while(i<n2 && ar[p][i]!=1){i++;
}
if(i==n2)
return 0;
long temp=ar[p][i];
if(t == 1)
{
ar[p][i]=-1;
ar[i][p]=-1;
}
// printf("p=%ld i=%ld",p,i);
return i;*/
node *t=ar[p];
if(t==null)
{
return 0;
}
t=ar[p];
ar[p]=ar[p]->next;
long d=t->data;
// printf("0-> %ld ",d);
free(t);
t=null;
t=ar[d];
if(ar[d]->data==p)
{
ar[d]=ar[d]->next;
}
else
{
node * prev=ar[d];
t=ar[d]->next;
while(t->data != p)
{
// printf(" d= %ld",t->data);
t=t->next;
prev=prev->next;
}
prev->next=t->next;
}
free(t);
t=null;
return d;
}
void dfsvisit(node ** ar,long s)
{
long v,v2;
while(v=adj(ar,s))
{
// printf("hello\n");
dfsvisit(ar,v);
// printf("v=%ld s=%ld",v,s);
if(st[0][v]==0 && st[1][v]==0)
{
if(st[1][s]==0)
{
// printf("hello");
st[1][s]=0;
st[0][s]=1;
}
}
else if(st[0][v]==1)
{
if(st[0][s]==0)
{
st[0][s]=st[0][v];
st[1][s]=st[1][v]+1;
}
else if(st[0][s]==1 && st[1][s]==0 )
{
st[0][s]=st[0][v];
st[1][s]=st[1][v]+1;
}
else
{
count++;
st[1][s]=-1;
st[0][s]=0;
}
}
// printf("count=%ld",count);
}
}
int main()
{
long t,n,a,b;
scanf("%ld",&t);
while(t--)
{
scanf("%ld",&n);
node **ar=(node**)malloc(n*sizeof(node*));
// long **ar=(long**)calloc(n,sizeof(long*));
st[0]=(long*)calloc(n,sizeof(long));
st[1]=(long*)calloc(n,sizeof(long));
long i=0;
n2=n;
while(n--)
{
//ar[i++]=(long*)calloc(n2,sizeof(long));
ar[i++]=null;
}
n=n2;
n--;
while(n--)
{
scanf("%ld %ld",&a,&b);
node *temp=(node*)malloc(sizeof(node));
//ar[a][b]=1;
//ar[b][a]=1;
temp->next=ar[a];
ar[a]=temp;
ar[a]->data=b;
temp=(node*)malloc(sizeof(node));
temp->next=ar[b];
ar[b]=temp;
ar[b]->data=a;
// printf("ar[b]->data = %ld",ar[b]->data);
}
long s=0;
n=n2;
count=0;
// adj(ar,0);
dfsvisit(ar,0);
count=count+st[0][0];
printf("%ld\n",count);
free(ar);
ar=NULL;
free(st[0]);
free(st[1]);
}
return 0;
}
Leave a comment below
