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()
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));
}
}
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;
}
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;
}
}
