HackerRank Hacker Country Problem Solution Yashwant Parihar, May 25, 2023May 28, 2024 In this post, we will solve HackerRank Hacker Country Problem Solution. There are N cities in Hacker Country. Each pair of cities are directly connected by a unique directed road, and each road has its own toll that must be paid every time it is used. You’re planning a road trip in Hacker Country, and its itinerary must satisfy the following conditions: You can start in any city. You must use 2 or more different roads (meaning you will visit 2 or more cities). At the end of your trip, you should be back in your city of origin. The average cost (sum of tolls paid per road traveled) should be minimum. Can you calculate the minimum average cost of a trip in Hacker Country? Time LimitsTime limits for this challenge are provided here. Input FormatThe first line is an integer, N (number of cities).The N subsequent lines of N space-separated integers each describe the respective tolls or traveling from city i to city j: in other words, the jth integer of the ¿th line denotes the toll for traveling from city i to city j.Note: As there are no roads connecting a city to itself, the ith integer of line i will always be0.Output FormatPrint the minimum cost as a rational number p/q (tolls paid over roads traveled). The greatest common divisor of p and q should be 1. Sample Input 2 0 1 2 0 Sample Output 3/2 ExplanationThe toll from city co to city c is 1. The toll from c, to co is 2. Your travel cost p=1+2=3. Your number of roads traveled is q = 2. Thus, we print 3/2 as our answer. HackerRank Hacker Country Problem Solution Hacker Country C Solution #include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> #define MAX_SIZE 502 #define MAX_COST 200 int gcd( int a, int b ); int main(){ int w[MAX_SIZE][MAX_SIZE]; int d[MAX_SIZE][MAX_SIZE]; int N,rc,i,j,k,temp,min,min_P,min_Q,max_P,max_Q,p,q,g; double u,v; rc = scanf("%d",&N); for(i=0;i<N;i++){ for(j=0;j<N;j++){ rc = scanf("%d",&w[i][j]); d[i][j] = 0; } } for(k=1;k<=N;k++){ for(i=0;i<N;i++){ min = (MAX_SIZE * MAX_COST) + 1; for(j=0;j<N;j++){ if(i!=j){ temp = w[j][i] + d[k-1][j]; if(min > temp){ min = temp; } } } d[k][i] = min; } } /* for(i=0;i<=N;i++,printf("\n")){ for(j=0;j<N;j++,printf(" ")){ printf("%d",d[i][j]); } } */ min_P = (MAX_SIZE * MAX_COST) + 1; min_Q = 1; for(i=0;i<N;i++){ max_P = 0; max_Q = 1; for(k=0;k<N;k++){ p = d[N][i] - d[k][i]; q = N - k; u = ((double)p) / ((double)q); v = ((double)max_P) / ((double)max_Q); if(v<u){ max_P = p; max_Q = q; } } v = ((double)max_P) / ((double)max_Q); u = ((double)min_P) / ((double)min_Q); if(u>v){ min_P = max_P; min_Q = max_Q; } } g = gcd(min_P,min_Q); min_P = min_P/g; min_Q = min_Q/g; printf("%d/%d",min_P,min_Q); return 0; } int gcd( int a, int b ){ int c; while ( a != 0 ) { c = a; a = b%a; b = c; } return b; } Hacker Country C++ Solution #include <algorithm> #include <climits> #include <cstdio> using namespace std; typedef long long ll; #define REP(i, n) for (int i = 0; i < (n); i++) #define REP1(i, n) for (int i = 1; i <= (n); i++) int ri() { int x; scanf("%d", &x); return x; } const int N = 500; int g[N][N], d[N+1][N]; int gcd(int a, int b) { int t; while (b) t = a%b, a = b, b = t; return a; } int main() { int n = ri(); REP(i, n) REP(j, n) g[i][j] = ri(); d[0][0] = 0; REP1(k, n) REP(i, n) { d[k][i] = INT_MAX; REP(j, n) if (j != i) d[k][i] = min(d[k][i], d[k-1][j]+g[j][i]); } int optp = 1, optq = 0; REP(i, n) { int pp = 0, qq = 1; REP(k, n) { // all d[k][i] are finite int p = d[n][i]-d[k][i], q = n-k, x = gcd(p, q); p /= x; q /= x; if (ll(p)*qq > ll(q)*pp) pp = p, qq = q; } if (ll(pp)*optq < ll(qq)*optp) optp = pp, optq = qq; } printf("%d/%d\n", optp, optq); } Hacker Country C Sharp Solution using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { static string hackerCountry(int[][] g, int[][] d, int n) { d[0][0] = 0; for (int k = 1; k <= n; k++) { for (int i = 0; i < n; i++) { d[k][i] = int.MaxValue; for (int j = 0; j < n; j++) { if (j != i) d[k][i] = Math.Min(d[k][i], d[k - 1][j] + g[j][i]); } } } int optp = 1; int optq = 0; for (int i = 0; i < n; i++) { int pp = 0; int qq = 1; for (int k = 0; k < n; k++) { int p = d[n][i] - d[k][i]; int q = n - k; int x = gcd(p, q); p /= x; q /= x; if ((long)p * qq > (long)q * pp) { pp = p; qq = q; } } if ((long)pp * optq < (long)qq * optp) { optp = pp; optq = qq; } } return $"{optp}/{optq}"; } static int gcd(int a, int b) { int t; while (b > 0) { t = a % b; a = b; b = t; } return a; } static void Main(string[] args) { TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true); int n = Convert.ToInt32(Console.ReadLine()); int[][] tolls = new int[n][]; int[][] d = new int[n + 1][]; for (int tollsRowItr = 0; tollsRowItr < n; tollsRowItr++) { tolls[tollsRowItr] = Array.ConvertAll(Console.ReadLine().Split(' '), tollsTemp => Convert.ToInt32(tollsTemp)); d[tollsRowItr] = new int[n]; } d[n] = new int[n]; string result = hackerCountry(tolls,d,n); textWriter.WriteLine(result); textWriter.Flush(); textWriter.Close(); } } Hacker Country Java Solution import java.io.*; import java.math.*; import java.text.*; import java.util.*; import java.util.regex.*; public class Solution { private static final Scanner scan = new Scanner(System.in); public static void main(String[] args) throws IOException { int n = scan.nextInt(); int[][] ar = new int[n][n]; int p = 6; int[][][] mat = new int[p][n][n]; for (int i=0; i < n; i++) { for (int j = 0; j < n; j++) { int s = scan.nextInt(); if(s == 0) { ar[i][j] = 1000000; } else { ar[i][j] = s; } } } scan.close(); for (int i = 0; i < p; i++) { if (i >= n) { break; } for (int j = 0; j < n; j++) { mat[i][0][j] = ar[i][j]; } } for (int i = 0; i < p; i++){ if (i >= n) { break; } if (i == 4) { continue; } for (int j = 1; j < n; j++) { for (int k = 0; k < n; k++){ int mini = 1000000; for (int s = 0; s < n; s++) { int temp = mat[i][j-1][s] + ar[s][k]; if (temp < mini) mini = temp; } mat[i][j][k] = mini; } } } double min = 1000000; int a = 0, b = 0; for(int i = 0; i < p; i++) { if (i >= n) { break; } if (i == 4) { continue; } for (int j = 0; j < n; j++) { double s = ((double) mat[i][j][i]) / (j + 1); if (s < min) { min = s; a = mat[i][j][i]; b = j + 1; } } } BigInteger w = new BigInteger("" + a); BigInteger q = new BigInteger("" + b); int gcd = (w.gcd(q)).intValue(); System.out.println((a / gcd)+"/"+(b / gcd)); } } Hacker Country Python Solution 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() c C# C++ HackerRank Solutions java python CcppCSharpHackerrank Solutionsjavapython