Savita And Friends – 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++ Savita And Friends HackerRank Solution
/*
*/
//#pragma comment(linker, "/STACK:16777216")
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>
//#include <memory.h>
#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define eps 1e-14
//#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 256
//#define N 120000
using namespace std;
long tests;
vector<pair<long, long> > g[200000];
long a,b,c;
long long cp1,cp2,tt;
long n,m,k;
long long dist[200000];
long bda,bdb;
double nmove;
set<pair<long long, long > > sett;
set<pair<long long, long> > ::iterator it;
pair<long long, long> tp;
long long qv;
long long qcost;
long d1[200000],d2[200000];
double l,r,mid1,mid2;
double gett(double val)
{
double bst=0;
for (int i=1;i<=n;i++)
bst=max(bst,min(d1[i]+val,d2[i]+tt-val));
return bst;
}
int main(){
//freopen("pattern.in","r",stdin);
//freopen("pattern.out","w",stdout);
//freopen("C:/input.txt","r",stdin);
//freopen("C:/output.txt","w",stdout);
ios_base::sync_with_stdio(0);
//cin.tie(0);
cin>>tests;
for (;tests;--tests)
{
cin>>n>>m>>k;
for (int i=1;i<=n;i++)
g[i].clear();
for (int i=1;i<=m;i++)
{
cin>>a>>b>>c;
if (i==k){cp1=a,cp2=b;tt=c;}
g[a].push_back(make_pair(b,c));
g[b].push_back(make_pair(a,c));
}
for (int i=1;i<=n;i++)
dist[i]=1e16;
dist[cp1]=0;
sett.clear();
for (int i=1;i<=n;i++)
sett.insert(make_pair(dist[i],i));
for (int iter=1;iter<=n;iter++)
{
it=sett.begin();
tp=(*it);
sett.erase(it);
qv=tp.second;
qcost=tp.first;
for (int i=0;i<g[qv].size();i++)
{
long long nv=g[qv][i].first;
long long ncost=g[qv][i].second+qcost;
if (min(nv,qv)==min(cp1,cp2)&&max(nv,qv)==max(cp1,cp2))
continue;
if (dist[nv]>ncost)
{
sett.erase(make_pair(dist[nv],nv));
dist[nv]=ncost;
sett.insert(make_pair(dist[nv],nv));
}
}
}
for (int i=1;i<=n;i++)
d1[i]=dist[i];
// -- 2nd end
for (int i=1;i<=n;i++)
dist[i]=1e16;
dist[cp2]=0;
sett.clear();
for (int i=1;i<=n;i++)
sett.insert(make_pair(dist[i],i));
for (int iter=1;iter<=n;iter++)
{
it=sett.begin();
tp=(*it);
sett.erase(it);
qv=tp.second;
qcost=tp.first;
for (int i=0;i<g[qv].size();i++)
{
long long nv=g[qv][i].first;
long long ncost=g[qv][i].second+qcost;
if (min(nv,qv)==min(cp1,cp2)&&max(nv,qv)==max(cp1,cp2))
continue;
if (dist[nv]>ncost)
{
sett.erase(make_pair(dist[nv],nv));
dist[nv]=ncost;
sett.insert(make_pair(dist[nv],nv));
}
}
}
for (int i=1;i<=n;i++)
d2[i]=dist[i];
/*
for (int i=1;i<=n;i++)
cout<<d1[i]<<" ";
cout<<endl;
for (int i=1;i<=n;i++)
cout<<d2[i]<<" ";
cout<<endl;
*/
l=0;
r=tt;
while (r-l>1e-6)
{
mid1=l*2+r;
mid2=l+r*2;
mid1/=3;
mid2/=3;
if (gett(mid1)<gett(mid2))r=mid2;
else l=mid1;
}
if (gett(0)<gett(l))l=0;
if (gett(tt)<gett(l))l=tt;
// cout<<gett(2)<<endl;
cout.precision(5);
cout<<fixed<<l<<" "<<gett(l)<<endl;
}
cin.get();cin.get();
return 0;}
Java Savita And Friends HackerRank Solution
import java.io.*;
import java.util.*;
public class Solution {
static final long INF = 1000000000000000000L;
static class Edge {
int o;
long len;
public Edge(int o, long len) {
this.o = o;
this.len = len;
}
}
static class Point implements Comparable<Point> {
long x, y;
public Point(long x, long y) {
this.x = x;
this.y = y;
}
@Override
public int compareTo(Point o) {
if (x == o.x) {
return Long.compare(o.y, y);
}
return Long.compare(x, o.x);
}
}
public static void solve(Input in, PrintWriter out) throws IOException {
int tests = in.nextInt();
for (int test = 0; test < tests; ++test) {
int n = in.nextInt();
int m = in.nextInt();
int k = in.nextInt() - 1;
ArrayList<Edge>[] edges = new ArrayList[n];
for (int i = 0; i < n; ++i) {
edges[i] = new ArrayList<Edge>();
}
int a0 = -1, b0 = -1;
long c0 = -1;
for (int i = 0; i < m; ++i) {
int a = in.nextInt() - 1;
int b = in.nextInt() - 1;
long c = in.nextLong();
if (i == k) {
a0 = a;
b0 = b;
c0 = c;
} else {
edges[a].add(new Edge(b, c));
edges[b].add(new Edge(a, c));
}
}
long[] da = dists(a0, edges);
long[] db = dists(b0, edges);
Point[] points = new Point[n];
for (int i = 0; i < n; ++i) {
if (da[i] == INF && db[i] == INF) {
throw new AssertionError();
}
if (da[i] + c0 < db[i]) {
points[i] = new Point(-da[i], da[i] + 2 * c0);
} else if (db[i] + c0 < da[i]) {
points[i] = new Point(-db[i] - c0, db[i] + c0);
} else {
points[i] = new Point(-da[i], db[i] + c0);
}
}
Arrays.sort(points);
Point last = null, ans = null;
for (Point p : points) {
Point cur;
if (last == null) {
cur = new Point(0, -2 * p.x);
} else if (last.y < p.y) {
cur = new Point(p.x + last.y, last.y - p.x);
} else {
continue;
}
last = p;
if (ans == null || ans.y > cur.y || ans.y == cur.y && ans.x > cur.x) {
ans = cur;
}
}
if (last == null) {
throw new AssertionError();
}
{
Point cur = new Point(2 * c0, 2 * (last.y - c0));
if (ans == null || ans.y > cur.y || ans.y == cur.y && ans.x > cur.x) {
ans = cur;
}
}
out.printf("%.5f %.5f%n", ans.x / 2.0, ans.y / 2.0);
}
}
static class Node implements Comparable<Node> {
int i;
long dist;
public Node(int i, long dist) {
this.i = i;
this.dist = dist;
}
@Override
public int compareTo(Node o) {
return Long.compare(dist, o.dist);
}
}
private static long[] dists(int v0, ArrayList<Edge>[] edges) {
long[] d = new long[edges.length];
Arrays.fill(d, INF);
PriorityQueue<Node> pq = new PriorityQueue<Node>();
d[v0] = 0;
pq.add(new Node(v0, 0));
while (!pq.isEmpty()) {
Node n = pq.poll();
if (d[n.i] != n.dist) {
continue;
}
for (Edge e : edges[n.i]) {
if (d[e.o] > n.dist + e.len) {
d[e.o] = n.dist + e.len;
pq.add(new Node(e.o, d[e.o]));
}
}
}
return d;
}
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 Savita And Friends HackerRank Solution
import heapq
def calc_dist(G, start):
dist = [-1] * len(G)
active = [(0, start)]
while active:
d, i = heapq.heappop(active)
if dist[i] >= 0: continue
dist[i] = d
for j, e in G[i]:
if dist[j] < 0:
heapq.heappush(active, (d+e, j))
return dist
T = int(input())
for t in range(T):
N, M, K = map(int, input().split())
edges = []
G = [[] for i in range(N+1)]
for i in range(M):
A, B, C = map(int, input().split())
edges.append((A, B, C))
G[A].append((B, C))
G[B].append((A, C))
A, B, C = edges[K-1]
distA = calc_dist(G, A)
distB = calc_dist(G, B)
peaks = []
for i in range(1,N+1):
x = (C + distB[i] - distA[i]) / 2
peaks.append((x, distA[i] + x))
peaks.sort()
pts = []
for x, y in peaks:
while pts:
x0, y0 = pts[-1]
if y0 > y - x + x0: break
pts.pop()
if pts:
x0, y0 = pts[-1]
xy = x0 + y0
if y > xy - x:
x1 = (xy - y + x) / 2
pts.append((x1, xy - x1))
pts.append((x, y))
else:
if x > 0:
pts.append((0, y - x))
pts.append((x, y))
x, y = pts[-1]
if x < C: pts.append((C, y + x - C))
xmin, ymin = pts[0]
for x, y in pts:
if y < ymin:
xmin = x
ymin = y
print("%.5f %.5f" % (xmin, ymin))
C Savita And Friends HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
typedef struct{
int u;
long long w;
} node;
void heap_insert(node *heap,node *elem,int *size,int *heap_list);
void heap_update(node *heap,node *elem,int *heap_list);
void heap_read(node *heap,int *size,int *heap_list,node *ans);
void DJ(int N,int M,int*u,int*v,int*w,int*v_right,int*list_index,int*left_index,int*right_index,int S,long long*d);
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size,int right_size);
void sort_a3(int*a,int*b,int*c,int size);
void merge3(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 T,N,M,K,A,B,C,f,i;
int *u,*v,*w,*v_right,*list_index,*left_index,*right_index;
long long max1,max2,maxa,maxb,min;
long long *d_a,*d_b;
u=(int*)malloc(100000*sizeof(int));
v=(int*)malloc(100000*sizeof(int));
w=(int*)malloc(100000*sizeof(int));
v_right=(int*)malloc(100000*sizeof(int));
list_index=(int*)malloc(100000*sizeof(int));
left_index=(int*)malloc(100000*sizeof(int));
right_index=(int*)malloc(100000*sizeof(int));
d_a=(long long*)malloc(100000*sizeof(long long));
d_b=(long long*)malloc(100000*sizeof(long long));
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&N,&M,&K);
for(i=0;i<M;i++){
scanf("%d%d%d",u+i,v+i,w+i);
u[i]--;
v[i]--;
list_index[i]=i;
}
A=u[K-1];
B=v[K-1];
C=w[K-1];
for(i=0;i<N;i++)
d_a[i]=d_b[i]=-1;
sort_a3(u,v,w,M);
for(i=0;i<M;i++)
v_right[i]=v[i];
sort_a2(v_right,list_index,M);
for(i=0;i<M;i++){
if(i==0 || u[i]!=u[i-1])
left_index[u[i]]=i;
if(i==0 || v_right[i]!=v_right[i-1])
right_index[v_right[i]]=i;
}
DJ(N,M,u,v,w,v_right,list_index,left_index,right_index,A,d_a);
DJ(N,M,u,v,w,v_right,list_index,left_index,right_index,B,d_b);
max1=max2=maxa=maxb=-1;
for(i=0;i<N;i++){
if(d_a[i]>maxa)
maxa=d_a[i];
if(d_b[i]>maxb)
maxb=d_b[i];
min=(d_a[i]>d_b[i])?d_b[i]:d_a[i];
if(min>max1){
max1=min;
if(min==d_a[i])
f=0;
else
f=1;
}
else if(min==max1 && f && min==d_a[i])
f=0;
}
if(f){
for(i=0;i<N;i++){
min=(d_a[i]>d_b[i])?d_b[i]:d_a[i];
if(min>max2 && min!=d_b[i] && d_b[i]>max1 && d_b[i]>=(double)min+((double)C+max1-min)/2)
max2=min;
}
if((max2==-1 || max1-max2>=C) && maxa>maxb)
printf("%.5lf %.5lf\n",(double)C,(double)maxb);
else if(maxa<=(double)max2+((double)C+max1-max2)/2)
printf("%.5lf %.5lf\n",0.0,(double)maxa);
else
printf("%.5lf %.5lf\n",((double)C+max1-max2)/2,(double)max2+((double)C+max1-max2)/2);
}
else{
for(i=0;i<N;i++){
min=(d_a[i]>d_b[i])?d_b[i]:d_a[i];
if(min>max2 && min!=d_a[i] && d_a[i]>max1 && d_a[i]>(double)max1+((double)C-max1+min)/2)
max2=min;
}
if((max2==-1 || max1-max2>=C) && maxb>=maxa)
printf("%.5lf %.5lf\n",0.0,(double)maxa);
else if(maxb<(double)max1+((double)C-max1+max2)/2)
printf("%.5lf %.5lf\n",(double)C,(double)maxb);
else
printf("%.5lf %.5lf\n",((double)C-max1+max2)/2,(double)max1+((double)C-max1+max2)/2);
}
}
return 0;
}
void heap_insert(node *heap,node *elem,int *size,int *heap_list){
(*size)++;
int index=(*size);
while(index>1 && elem->w<heap[index/2].w){
heap[index]=heap[index/2];
heap_list[heap[index].u]=index;
index/=2;
}
heap[index]=(*elem);
heap_list[elem->u]=index;
return;
}
void heap_update(node *heap,node *elem,int *heap_list){
int index=heap_list[elem->u];
while(index>1 && elem->w<heap[index/2].w){
heap[index]=heap[index/2];
heap_list[heap[index].u]=index;
index/=2;
}
heap[index]=(*elem);
heap_list[elem->u]=index;
return;
}
void heap_read(node *heap,int *size,int *heap_list,node *ans){
(*ans)=heap[1];
int index=1;
while(index*2<*size && heap[*size].w>heap[index*2].w || index*2+1<*size && heap[*size].w>heap[index*2+1].w){
index=(heap[index*2].w>heap[index*2+1].w)?index*2+1:index*2;
heap[index/2]=heap[index];
heap_list[heap[index].u]=index/2;
}
heap[index]=heap[*size];
heap_list[heap[index].u]=index;
(*size)--;
return;
}
void DJ(int N,int M,int*u,int*v,int*w,int*v_right,int*list_index,int*left_index,int*right_index,int S,long long*d){
int i,next_solve,heap_size=0,*heap_list;
node elem,*heap;
heap=(node*)malloc(N*sizeof(node));
heap_list=(int*)malloc(N*sizeof(int));
d[S]=0;
next_solve=S;
while(1){
for(i=left_index[next_solve];i>=0 && i<M && u[i]==next_solve;i++)
if(d[v[i]]==-1 || d[v[i]]>d[next_solve]+w[i]){
elem.u=v[i];
elem.w=d[next_solve]+w[i];
if(d[v[i]]==-1)
heap_insert(heap,&elem,&heap_size,heap_list);
else
heap_update(heap,&elem,heap_list);
d[v[i]]=d[next_solve]+w[i];
}
for(i=right_index[next_solve];i>=0 && i<M && v_right[i]==next_solve;i++)
if(d[u[list_index[i]]]==-1 || d[u[list_index[i]]]>d[next_solve]+w[list_index[i]]){
elem.u=u[list_index[i]];
elem.w=d[next_solve]+w[list_index[i]];
if(d[u[list_index[i]]]==-1)
heap_insert(heap,&elem,&heap_size,heap_list);
else
heap_update(heap,&elem,heap_list);
d[u[list_index[i]]]=d[next_solve]+w[list_index[i]];
}
if(heap_size==0)
break;
heap_read(heap,&heap_size,heap_list,&elem);
next_solve=elem.u;
}
free(heap);
free(heap_list);
return;
}
void sort_a2(int*a,int*b,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int*left_a,*left_b,*right_a,*right_b;
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));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
}
sort_a2(left_a,left_b,m);
sort_a2(right_a,right_b,size-m);
merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
return;
}
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,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];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else if (left_a[i] <= right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
}
}
return;
}
void sort_a3(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_a3(left_a,left_b,left_c,m);
sort_a3(right_a,right_b,right_c,size-m);
merge3(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 merge3(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