HackerRank Hacker Country problem solution

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:

1. You can start in any city.
2. You must use 2 or more different roads (meaning you will visit 2 or more cities).
3. At the end of your trip, you should be back in your city of origin.
4. 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;
    }
}