Table of Contents
Hacker Country – 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++ Hacker Country HackerRank Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510;
const int inf = (int)1e9;
int a[N][N];
int d[N][N];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) scanf("%d", a[i] + j);
for (int i = 0; i < n; i++) d[0][i] = 0;
for (int it = 0; it < n; it++) {
for (int i = 0; i < n; i++) d[it + 1][i] = inf;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (i == j) {
continue;
}
int dt = d[it][i] + a[i][j];
if (dt < d[it + 1][j]) {
d[it + 1][j] = dt;
}
}
}
long long p = inf, q = 1;
for (int i = 0; i < n; i++) {
long long pp = 0, qq = 1;
for (int it = 0; it < n; it++) {
long long num = d[n][i] - d[it][i];
long long den = n - it;
if (num * qq > pp * den) {
pp = num;
qq = den;
}
}
if (pp * q < p * qq) {
p = pp;
q = qq;
}
}
int xx = p, yy = q;
while (xx > 0 && yy > 0)
if (xx > yy) xx %= yy;
else yy %= xx;
int g = xx + yy;
p /= g;
q /= g;
printf("%d/%d", (int)p, (int)q);
return 0;
}
Java Hacker Country 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 Solution {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static void solve()
{
int n = ni();
int[][] a = new int[n][n];
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
a[i][j] = ni();
}
}
long[] ret = minavg(a);
out.println(ret[0] + "/" + ret[1]);
}
static long[] minavg(int[][] g)
{
int n = g.length;
int[][] dp = new int[n+1][n];
int I = 400000;
for(int k = 0;k < n;k++){
Arrays.fill(dp[k+1], I);
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
if(i != j && dp[k][i] < I){
dp[k+1][j] = Math.min(dp[k+1][j], dp[k][i] + g[i][j]);
}
}
}
}
long[] ret = {1L, 0L};
for(int i = 0;i < n;i++){
long[] lret = {0L, 1L};
for(int k = 0;k < n;k++){
if(dp[n][i] < I && dp[k][i] < I){
long num = dp[n][i]-dp[k][i];
long den = n-k;
if(lret[0] * den < lret[1] * num){
lret[0] = num; lret[1] = den;
}
}
}
if(lret[0] > 0){
if(ret[0] * lret[1] > ret[1] * lret[0]){
ret = lret;
}
}
}
long gcd = gcd(ret[0], ret[1]);
ret[0] /= gcd;
ret[1] /= gcd;
return ret;
}
public static long gcd(long a, long b) {
if(a == 0)return b;
if(b == 0)return a;
while (b > 0){
long c = a;
a = b;
b = c % b;
}
return a;
}
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 Hacker Country HackerRank Solution
#!/bin/python3
import os
import sys
def hackerCountry(tolls):
lc = len(tolls)
k = [i for i in range(lc)]
class Hiker:
def __init__(self, tolls: list):
self.cities = tolls
self.min_p = [200,1]
self.min_ratio = self.min_p[0]/self.min_p[1]
self.valid_paths = {}
self.time_in_copy_1 = 0
self.time_in_copy_2 = 0
self.time_in_copy_3 = 0
self.paths_added = 0
self.best_path = []
self.it = range(lc)
self.it2 = [x for x in ["road","toll","is_over"]]
self.iterations = 0
self.possible_paths = []
def find_start_path_for_city(self, city: int):
self.valid_paths[city] = []
for i, c in enumerate(self.cities[city]):
# print(i,c,city)
path = {"toll": 0, "road": 0, "path": [city], "is_over": False, "lookup":{}}
if i != city:
# path.increase(self.cities[city][c],c)
path["path"].append(i)
path["road"] += 1
path["toll"] += c
path["lookup"][i]=""
self.valid_paths[city].append(path)
# find return path
if (path["toll"] + self.cities[i][city]) / (
path["road"] + 1) < self.min_ratio:
self.min_p[0] = path["toll"] + self.cities[i][city]
self.min_p[1] = path["road"] + 1
self.min_ratio = self.min_p[0] / self.min_p[1]
def expand_path(self, path: dict,city:int,):
if path["toll"] / path["road"] > self.min_ratio:
path["is_over"] = True
while not path["is_over"]:
#pp = self.get_path(path)
pp = path["path"]
start_len = len(pp)
for c in self.it:
if c not in path["lookup"]:
path["road"] += 1
t= self.cities[pp[-1]][c]
path["toll"] += t
pp.append(c)
if path["toll"] / path["road"] < self.min_ratio:
cities_left = list(set(pp[1:] + k))
tolls_left = [self.cities[c][_] for _ in
cities_left]
if (min(tolls_left) + path["toll"]) / (path["road"] + 1) < self.min_ratio:
path_new = {x: path[x] for x in self.it2}
path_new["path"]=pp.copy()
path_new["lookup"]=path["lookup"].copy()
path_new["lookup"][c]=""
self.valid_paths[city].append(path_new)
if (path["toll"] + self.cities[c][city]) / (
path["road"] + 1) < self.min_ratio:
self.min_p[0] = path["toll"] + \
self.cities[c][
city]
self.min_p[1] = path["road"] + 1
self.min_ratio = self.min_p[0]/self.min_p[1]
path["toll"]-=t
path["road"]-=1
pp.pop(-1)
if len(pp) == start_len:
path["is_over"] = True
def check_paths_for_city(self, city: int):
finalized_paths = 0
while finalized_paths < len(self.valid_paths[city]):
finalized_paths = 0
for i, p in enumerate(self.valid_paths[city]):
if p["is_over"]:
finalized_paths += 1
else:
self.expand_path(p,city)
def find_best_ratio(self, a: int, b: int):
# print(f"original res {a}/{b}")
y = 10
while True:
to_break = True
for i in range(y, 1, -1):
if a % i == 0 and b % i == 0:
a = a // i
b = b // i
y = i
to_break = False
if to_break:
break
return (f"{a}/{b}")
def main(self):
for c in self.it:
self.find_start_path_for_city(c)
for c in self.it:
self.check_paths_for_city(c)
return self.find_best_ratio(self.min_p[0], self.min_p[1])
h = Hiker(tolls)
return h.main()
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
n = int(input())
tolls = []
for _ in range(n):
tolls.append(list(map(int, input().rstrip().split())))
result = hackerCountry(tolls)
fptr.write(result + '\n')
fptr.close()
Python 2 Hacker Country HackerRank Solution
import fileinput
import bisect
MAX_NODES = 500
MAX_COST = 200
class Graph:
def __init__(self, N):
self.N = N
self.M = [[0 for j in range(0,N)] for i in range(0,N)]
self.O = [[0 for j in range(0,N)] for i in range(0,N)]
self.min = MAX_COST
self.minCosts = [MAX_COST for i in range(0,N)]
self.count = 0
self.result = []
self.tot = MAX_COST*N
self.k = [0 for k in range(0,N+1)]
self.kmin = [0 for k in range(0,N+1)]
def setRow(self, row, values):
values[row] = MAX_COST+1
self.M[row] = values
ord = [(i,values[i]) for i in range(0,self.N)]
ord.sort(key=lambda x:x[1])
self.O[row] = ord
for v in ord:
if v[1]<self.minCosts[self.N-1]:
bisect.insort(self.minCosts, v[1])
else:
break
def init(self):
del self.minCosts[self.N:]
for i in range(1,self.N):
self.minCosts[i] += self.minCosts[i-1]
for lp in range(2,self.N+1):
kmin = MAX_COST
for k in range(lp,self.N+1):
kval = self.minCosts[k-lp]*1.0/k
if kval<kmin:
kmin = kval
self.kmin[lp] = kval
self.k[lp] = k
def minpath(self, r, first, last, c, lp, l):
next = []
minc = MAX_COST+1
p = pos = 0
lp+=1
for i in range(0,N):
(p,minc) = self.O[last][i]
pos = bisect.bisect_left(r,p)
if pos<len(r) and r[pos]==p:
if (c+minc)*1.0/self.k[lp]+self.kmin[lp]<self.min:
next.append(pos)
for j in range(i+1,N):
(p,v) = self.O[last][j]
if v==minc:
pos = bisect.bisect_left(r,p)
if pos<len(r) and r[pos]==p:
next.append(pos)
else:
break
break
else:
return
c += minc
for pos in next:
p = r[pos]
#self.count+=1
cost = c + self.M[p][first]
newmin = cost*1.0/lp
if newmin < self.min:
self.tot = cost
self.min = newmin
#print lp,self.min,self.count,c,'+',self.M[p][first],self.tot
self.result.append((lp, cost))
if lp<l and c*1.0/self.k[lp]+self.kmin[lp]<self.min:
self.minpath(r[:pos]+r[pos+1:], first, p, c, lp, l)
def getFraction(self):
(x,y) = min(self.result, key=lambda x: x[1]*1.0/x[0])
for i in range(2,x/2):
if y%i==0 and x%i==0:
y/=i
x/=i
if y%x==0:
y/=x
x=1
return (y,x)
def cost(self, p):
tot = G.M[p[-1]][p[0]]
for i in range(1,len(p)):
tot += G.M[p[i-1]][p[i]]
return tot
if __name__ == '__main__':
i = 0
#reading the input
for line in fileinput.input():
#nr of nodes and edges
if i==0:
N = int(line)
if N<1 or N>MAX_NODES:
raise Exception(format("Wrong number of total nodes: %d" % N))
G = Graph(N)
#edges
elif i<=N:
vals = map(int, line.split())
G.setRow(i-1,vals)
i += 1
G.init()
for i in range(0,N):
G.minpath(range(0,i)+range(i+1,N), i, i, 0, 1, N)
print ("%d/%d"%G.getFraction())
C Hacker Country HackerRank Solution
#include<stdio.h>
typedef long long int64;
typedef struct { int n,d; } Fraction;
#define INF 1000000009
#define maxi 502
int GCD(int a,int b) { return (b==0)?a:GCD(b,a%b); }
int Compare(Fraction a,Fraction b) { int64 x=(int64)(a.n)*b.d,y=(int64)(b.n)*a.d; return x<y?-1:(x==y?0:1); }
int A[maxi][maxi],d[maxi][maxi],N;
int solve()
{
int i,j,k; d[0][0]=0; for(i=1;i<N;i++) d[0][i]=INF;
for(i=1;i<=N;i++)
{
for(j=0;j<N;j++)
{
int min=INF; for(k=0;k<N;k++) if(A[k][j]) if(d[i-1][k]+A[k][j]<min) min=d[i-1][k]+A[k][j];
d[i][j]=min;
}
}
Fraction min={INF,1};
for(i=0;i<N;i++)
{
Fraction a,max={0,1};
for(j=0;j<N;j++)
{
if(d[N][i]==INF && d[j][i]==INF) { a.n=INF; a.d=1; }
else { a.n=d[N][i]-d[j][i]; a.d=N-j; }
if(Compare(max,a)==-1) { max.n=a.n; max.d=a.d; }
}
if(Compare(min,max)==1) { min.n=max.n; min.d=max.d; }
}
int g=GCD(min.n,min.d);
min.n/=g; min.d/=g;
printf("%d/%d\n",min.n,min.d);
}
int main()
{
int T=1;
while(T--)
{
scanf("%d",&N);
int i,j; for(i=0;i<N;i++) for(j=0;j<N;j++) scanf("%d",&A[i][j]);
solve();
}
return 0;
}
Leave a comment below
