HackerRank Diameter Minimization problem solution YASH PAL, 31 July 2024 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; 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(); } } {“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} Algorithms coding problems solutions