HackerRank Diameter Minimization problem solution

In this HackerRank Diameter Minimization problem solution we have given two integers, n, and m, to build a strongly connected oriented graph with n vertices where each vertex has outdegree m and the graph’s diameter is as small as possible (see the Scoring section below for more detail). Then print the graph according to the Output Format specified.

Problem solution in Python.

#!/bin/python3


import sys
import math

def opt_diameter(n, m):
    count = 1
    depth = 0
    while count < n:
        depth += 1
        count = m ** depth
    return depth
    
def diameter(n, m):
    count = 1
    depth = 0
    while count < n:
        depth += 1
        count += m ** depth
    left_over = m ** depth - (count - n)
    limit = m ** (depth - 1)
    discount = 1
    if left_over > limit:
        discount = 0
    return max(depth, 2 * depth - discount)

def solve(in_file, out_file):
    n, m = (int(raw) for raw in in_file.readline().strip().split(' '))
    out_file.write("{}n".format(opt_diameter(n, m)))
    count = 0
    for _ in range(n):
        ret = []
        for _ in range(m):
            val = count % n
            count += 1
            ret.append(str(val))
        out_file.write("{}n".format(" ".join(ret)))

if __name__ == '__main__':
    from_file = False
    if from_file:
        path = 'Data\'
        name = 'mega_prime'
        file_input = open(path + name + '.in', 'r')
        file_output = open(path + name + '.out','w')
        solve(file_input, file_output)
        file_input.close()
        file_output.close()
    else:
        solve(sys.stdin, sys.stdout)

Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

  static Deque<Integer> q = new LinkedList<>();

  static int[] dis = new int[1001];

  static int bfs(int n, int m, int x) {
    Arrays.fill(dis, 1_000_000_000);
    dis[x] = 0;
    q.add(x);
    int mmh = 0;
    while (!q.isEmpty()) {
      int k = q.removeFirst();
      mmh = dis[k];
      for (int i = 0; i < m; i++) {
        int j = (k * m + i) % n;
        if (dis[j] > mmh + 1) {
          dis[j] = mmh + 1;
          q.add(j);
        }
      }
    }
    return mmh;
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());

    dis = new int[n];
    
    int mmh = 0;
    for (int i = 0; i < n; i++) {
      mmh = Math.max(mmh, bfs(n, m, i));
    }
    bw.write(mmh + "n");
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        bw.write((i * m + j) % n + " ");
      }
      bw.write("n");
    }

    bw.newLine();

    bw.close();
    br.close();
  }
}

Problem solution in C++.

#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
#define forn(i,n) for (int i = 0; i < int(n); ++i)
typedef long long ll;
typedef long long i64;
typedef long double ld;
const int inf = int(1e9) + int(1e5);
const ll infl = ll(2e18) + ll(1e10);

int calcBest(int n, int m) {
    int d = 0;
    int onD = 1;
    int cn = 1;
    while (cn < n) {
        onD *= m;
        ++d;
        cn += onD;
    }
    return d;
}

const int maxn = 1005;
int g[maxn][maxn];
int n, m;

int dist[maxn];
int calcDiam(int s) {
    fill(dist, dist + n, inf);

    vector<int> q;
    dist[s] = 0;
    q.push_back(s);
    forn (ii, sz(q)) {
        int u = q[ii];
        forn (i, m) {
            int v = g[u][i];
            if (dist[v] < inf)
                continue;
            dist[v] = dist[u] + 1;
            q.push_back(v);
        }
    }

    if (sz(q) < n)
        return inf;
    return dist[q.back()];
}

int main() {
    #ifdef LOCAL
    assert(freopen("test.in", "r", stdin));
    #endif
    cin >> n >> m;
    forn (i, n) {
        forn (j, m)
            g[i][j] = (i * m + j) % n;
    }
    int diam = 0;
    forn (i, n)
        diam = max(diam, calcDiam(i));
    int best = calcBest(n, m);
    //cerr << "best " << best << 'n';
    assert(diam <= best + 1);
    assert(diam >= best);

    cout << diam << 'n';
    forn (i, n) {
        forn (j, m)
            cout << g[i][j] << ' ';
        cout << 'n';
    }
}