Journey Scheduling – 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++ Journey Scheduling HackerRank Solution
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
#define ll long long
#define ull unsigned ll
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
template <class T, class S, class U, class V> void reader(T *x, S *y, U *z, V *w){reader(x);reader(y);reader(z);reader(w);}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
template<class T, class S> void writerLn(T x, S y){writer(x,' ');writer(y,'\n');}
template<class T, class S, class U> void writerLn(T x, S y, U z){writer(x,' ');writer(y,' ');writer(z,'\n');}
template<class T> void writerArr(T x[], int n){int i;if(!n){mypc('\n');return;}rep(i,n-1)writer(x[i],' ');writer(x[n-1],'\n');}
#define MD 1000000007
void* setUndirectEdge(int N, int M, int A[], int B[], int **es, int ***edge, void *workMemory){int i;*es=(int*)workMemory;*edge=(int**)((*es)+N);(*edge)[0]=(int*)((*edge)+N);rep(i,N)(*es)[i]=0;rep(i,M)(*es)[A[i]]++,(*es)[B[i]]++;REP(i,1,N)(*edge)[i]=(*edge)[i-1]+(*es)[i-1];workMemory=(void*)((*edge)[N-1]+(*es)[N-1]);rep(i,N)(*es)[i]=0;rep(i,M)(*edge)[A[i]][(*es)[A[i]]++]=B[i],(*edge)[B[i]][(*es)[B[i]]++]=A[i];return workMemory;}
int N, M;
int *es, **edge;
int A[110000], B[110000];
int dist[110000];
int dist1[110000], dist2[110000];
void dfs(int now, int d, int bef){
int i, j, k;
dist[now] = d;
rep(i,es[now]){
k = edge[now][i];
if(k==bef) continue;
dfs(k,d+1,now);
}
}
int main(){
int i, j, k, V, K;
int v1, v2, mx;
ll res, mxd;
void *mem = malloc(10000000);
reader(&N, &M);
rep(i,N-1) reader(A+i,B+i), A[i]--, B[i]--;
setUndirectEdge(N,N-1,A,B,&es,&edge,mem);
dfs(0,0,-1);
mx = 0;
rep(i,N) if(mx < dist[i]) mx = dist[i], v1 = i;
dfs(v1,0,-1);
mx = 0;
rep(i,N) if(mx < dist[i]) mx = dist[i], v2 = i;
rep(i,N) dist1[i] = dist[i];
dfs(v2,0,-1);
rep(i,N) dist2[i] = dist[i];
mxd = 0;
rep(i,N) if(mxd < dist2[i]) mxd = dist2[i];
while(M--){
reader(&V,&K); V--;
res = max(dist1[V], dist2[V]) + (K-1) * mxd;
writerLn(res);
}
return 0;
}
Java Journey Scheduling HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class C {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static void solve()
{
int n = ni(), m = ni();
int[] from = new int[n-1];
int[] to = new int[n-1];
for(int i = 0;i < n-1;i++){
from[i] = ni()-1;
to[i] = ni()-1;
}
int[][] g = packU(n, from, to);
int[][] pars = parents3(g, 0);
int[] ord = pars[1], par = pars[0];
int[] ds1 = new int[n];
int[] ds2 = new int[n];
Arrays.fill(ds1, -1);
Arrays.fill(ds2, -1);
for(int i = n-1;i >= 0;i--){
int cur = ord[i];
for(int e : g[cur]){
if(ds1[cur] <= ds1[e] + 1){
ds2[cur] = ds1[cur];
ds1[cur] = ds1[e] + 1;
}else if(ds2[cur] <= ds1[e] + 1){
ds2[cur] = ds1[e] + 1;
}
}
}
for(int i = 1;i < n;i++){
int cur = ord[i];
int pa = par[cur];
int x = -1;
if(ds1[pa] == ds1[cur] + 1){
x = ds2[pa] + 1;
}else{
x = ds1[pa] + 1;
}
if(ds1[cur] <= x){
ds2[cur] = ds1[cur];
ds1[cur] = x;
}else if(ds2[cur] <= x){
ds2[cur] = x;
}
}
int diam = 0;
for(int i = 0;i < n;i++){
diam = Math.max(diam, ds1[i]);
}
tr(ds1);
tr(ds2);
for(int u = 0;u < m;u++){
int v = ni()-1, K = ni();
out.println(ds1[v] + (long)diam * (K-1));
}
}
public static int[][] parents3(int[][] g, int root) {
int n = g.length;
int[] par = new int[n];
Arrays.fill(par, -1);
int[] depth = new int[n];
depth[0] = 0;
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;
depth[nex] = depth[cur] + 1;
}
}
}
return new int[][] { par, q, depth };
}
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");
}
private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }
private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
Python 3 Journey Scheduling HackerRank Solution
#!/bin/env python3
from heapq import *
def read():
return map(int, input().split())
def read_graph(N, M):
G = [[] for _ in range(N)]
for _ in range(M):
u, v = map(int, input().split())
u, v = u-1, v-1
G[u].append((1, v))
G[v].append((1, u))
return G
def dykstra(G, s, c0=0, f_cost=lambda a,b:a+b):
N = len(G)
cost = [None] * N
path = [None] * N
h = [(c0, None, s, None)]
while len(h) != 0:
c, m, n, p = heappop(h)
if cost[n] != None: continue
cost[n] = c
path[n] = (m, p)
for m2, n2 in G[n]:
if cost[n2] != None: continue
heappush(h, (f_cost(c, m2), m2, n2, n))
return cost, path
def dfs(n0, d0):
global G
global dist
q = [(n0, d0)]
while len(q) != 0:
n,d = q.pop()
for m, n2 in G[n]:
if dist[n2] != -1: continue
dist[n2] = d+1
q.append((n2, d+1))
N, M = read()
G = read_graph(N, N-1)
# both ends(s,t) of diameter
c,p = dykstra(G,0)
s = c.index(max(c))
c,p = dykstra(G,s)
t = c.index(max(c))
# length of diameter
n, diam = t, 0
while p[n][1] != None:
diam += 1
n = p[n][1]
# find middle point of diameter
n1, n2 = t, p[t][1]
for i in range(diam//2):
n1 = p[n1][1]
n2 = p[n2][1]
# distance from middle point
dist = [-1] * N
if diam % 2 == 0:
dist[n1] = 0
dfs(n1, 0)
else:
dist[n1] = 0
dist[n2] = 0
dfs(n1, 0)
dfs(n2, 0)
for i in range(M):
v,k = read()
print(dist[v-1] + (diam+1)//2 + (k-1)*diam)
Python 2 Journey Scheduling HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
from collections import defaultdict
N, M = None, None
Q = None
G = defaultdict(lambda: set())
def read_data():
global N, M, Q, G
N, M = map(int, raw_input().strip().split())
Q = []
for _ in xrange(N-1):
x, y = map(int, raw_input().strip().split())
G[x-1].add(y-1)
G[y-1].add(x-1)
for _ in xrange(M):
Q.append(map(int, raw_input().strip().split()))
def get_distances(start):
global G
d = {start:0}
q = [(start, 0)]
while len(q):
node, dist = q.pop(0)
for neighbour in G[node]:
if neighbour not in d:
d[neighbour] = dist+1
q.append((neighbour, dist+1))
return d
def get_diameter():
global N, G
d = get_distances(0)
x_diam = max(d, key=d.get)
dx = get_distances(x_diam)
y_diam = max(d, key=dx.get)
dy = get_distances(y_diam)
diam_size = max(dy.values())
max_dist = {}
for node in xrange(N):
max_dist[node] = max(dx[node], dy[node])
return (x_diam, y_diam, diam_size, max_dist)
def solve_queries():
global Q
x, y, d, m = get_diameter()
for v, k in Q:
print d*(k-1) + m[v-1]
read_data()
solve_queries()
C Journey Scheduling HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _node{
int x;
int w;
struct _node *next;
} lnode;
void insert_edge(int x,int y,int w);
void dfs1(int x);
void dfs2(int x,int y);
int max(int x,int y);
int h[100000],sh[100000],l[100000],u[100000],trace[100000];
lnode *table[100000]={0};
int main(){
int N,M,x,y,i;
scanf("%d%d",&N,&M);
for(i=0;i<N-1;i++){
scanf("%d%d",&x,&y);
insert_edge(x-1,y-1,1);
}
memset(trace,0,sizeof(trace));
dfs1(0);
memset(trace,0,sizeof(trace));
dfs2(0,-1);
for(i=0;i<M;i++){
scanf("%d%d",&x,&y);
printf("%lld\n",max(h[x-1],u[x-1])+(y-1)*(long long)l[0]);
}
return 0;
}
void insert_edge(int x,int y,int w){
lnode *t=malloc(sizeof(lnode));
t->x=y;
t->w=w;
t->next=table[x];
table[x]=t;
t=malloc(sizeof(lnode));
t->x=x;
t->w=w;
t->next=table[y];
table[y]=t;
return;
}
void dfs1(int x){
lnode *p;
trace[x]=1;
h[x]=sh[x]=l[x]=0;
for(p=table[x];p;p=p->next)
if(!trace[p->x]){
dfs1(p->x);
if(h[p->x]+p->w>=h[x]){
sh[x]=h[x];
h[x]=h[p->x]+p->w;
}
else if(h[p->x]+p->w>sh[x])
sh[x]=h[p->x]+p->w;
if(l[p->x]>l[x])
l[x]=l[p->x];
}
if(h[x]+sh[x]>l[x])
l[x]=h[x]+sh[x];
return;
}
void dfs2(int x,int y){
lnode *p;
trace[x]=1;
if(y==-1)
u[x]=0;
else
if(h[y]==h[x]+1)
u[x]=max(u[y]+1,sh[y]+1);
else
u[x]=max(u[y]+1,h[y]+1);
for(p=table[x];p;p=p->next)
if(!trace[p->x])
dfs2(p->x,x);
return;
}
int max(int x,int y){
return (x>y)?x:y;
}
Leave a comment below