HackerRank Hacker Country Problem Solution

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/2

Explanation
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.

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 C cpp CSharp Hackerrank Solutions java python