HackerRank Hacker Country problem solution YASH PAL, 31 July 2024 In this 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? Problem solution in Python. #!/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() {“mode”:”full”,”isActive”:false} Problem solution in Java. 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)); } } {“mode”:”full”,”isActive”:false} Problem solution in C++. #include <iostream> #include <map> #define INFINITY 0x3f3f3f3f #define MAXN 505 using namespace std; typedef long long LL; LL get_difference(pair<int, int> a, pair<int, int> b) { LL t = (LL)a.first * b.second - (LL)a.second * b.first; return t; } int get_GCD(int a, int b) { return b == 0 ? a : get_GCD(b, a % b); } void get_min_cost(pair<int, int> p) { int g = get_GCD(p.first, p.second); cout << p.first / g << "/" << p.second / g << endl; } int main() { int input, s, roads[MAXN][MAXN], cities[MAXN][MAXN]; pair<int, int> directions, max_roads; cin >> input; for (int i = 0; i < input; i++) { for (int j = 0; j < input; j++) { cin >> roads[i][j]; if (i == j) roads[i][j] = INFINITY; } } for (int i = 0; i <= input + 1; i++) { for (int j = 0; j < input + 1; j++) { cities[i][j] = INFINITY; } } s = input++; for (int i = 0; i < input - 1; i++) { roads[s][i] = 0; roads[i][s] = INFINITY; } roads[s][s] = INFINITY; cities[0][s] = 0; for (int k = 0; k < input; k++) { for (int i = 0; i < input; i++) { for (int j = 0; j < input; j++) { if (cities[k][i] + roads[i][j] < cities[k + 1][j]) { cities[k + 1][j] = cities[k][i] + roads[i][j]; } } } } directions = make_pair(INFINITY, 1); for(int i = 0; i < input - 1; i++) { if(cities[input][i] == INFINITY) continue; max_roads = make_pair(-INFINITY, 1); for(int k = 0; k < input - 1; k++) { if(get_difference(make_pair(cities[input][i] - cities[k][i], input - k), max_roads) > 0) max_roads = make_pair(cities[input][i] - cities[k][i], input - k); } if (get_difference(max_roads, directions) < 0) directions = max_roads; } get_min_cost(directions); return 0; } {“mode”:”full”,”isActive”:false} Problem solution in C. #include <stdio.h> #include <stdlib.h> long long CC(long long n, long long d); int a[500][500],dp[501][500]; int main(){ int N,i,j,k,p,q,tp,tq,t; long double ans=201,tans; scanf("%d",&N); for(i=0;i<N;i++) for(j=0;j<N;j++) scanf("%d",&a[i][j]); for(i=0;i<=N;i++) for(j=0;j<N;j++) if(!i) dp[i][j]=0; else for(k=0,dp[i][j]=100000;k<N;k++){ if(j==k) continue; if(dp[i-1][k]+a[k][j]<dp[i][j]) dp[i][j]=dp[i-1][k]+a[k][j]; } for(i=0;i<N;i++){ for(tans=j=0;j<N;j++) if((dp[N][i]-dp[j][i])/(long double)(N-j)>tans){ tans=(dp[N][i]-dp[j][i])/(long double)(N-j); tp=dp[N][i]-dp[j][i]; tq=N-j; } if(tans<ans){ ans=tans; p=tp; q=tq; } } t=CC(p,q); printf("%d/%d",p/t,q/t); return 0; } long long CC(long long n, long long d){ while( 1 ) { n = n % d; if( n == 0 ) return d; d = d % n; if( d == 0 ) return n; } } {“mode”:”full”,”isActive”:false} algorithm coding problems