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)
```

{"mode":"full","isActive":false}

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;
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;
}
}
}
return mmh;
}

public static void main(String[] args) throws IOException {
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();
}
}
```

{"mode":"full","isActive":false}

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';
}
}
```

{"mode":"full","isActive":false}