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 Limits
Time limits for this challenge are provided here.
Input Format
The 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 be
0.
Output Format
Print 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/2Explanation
The 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.
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()
