HackerRank Diameter Minimization Solution Yashwant Parihar, June 2, 2023May 28, 2024 In this post, we will solve HackerRank Diameter Minimization Problem Solution. We define the diameter of a strongly-connected oriented graph, G = (V,E), as the minimum integer & such that for each u, v EG there is a path from u to v of length <d (recall that a path’s length is its number of edges).Given two integers, n and m. 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 below.Here’s a sample strongly-connected oriented graph with 3 nodes, whose outdegree is 2 and diameter is 1. Note: Cycles and multiple edges between vertices are allowed.Input FormatTwo space-separated integers describing the respective values of n (the number of vertices) and m (the outdegree of each vertex). ScoringWe denote the diameter of your graph as d and the diameter of the graph in the author’s solution as 8. Your score for each test case (as a real number from 0 to 1) Output FormatFirst, print an integer denoting the diameter of your graph on a new line.Next, print n lines where each line i (0 < i < n) contains m space-separated integers in the inclusive range from 0 ton – 1 describing the endpoints for each of vertex i’s outbound edges. Sample Input 0 5 2 Sample Output 0 2 1 4 2 0 3 1 4 2 0 3 Explanation 0The diagram below depicts a strongly-connected oriented graph with n = 5 nodes where each node has an outdegree of m = 2 The diameter of this graph is d = 2, which is minimal as the outdegree of each node must be m. We cannot construct a graph with a smaller diameter of d = 1 because it requires an outbound edge from each vertex to each other vertex in the graph (so the outdegree of that graph would be n-1). HackerRank Diameter Minimization Problem Solution Diameter Minimization C++ Solution #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() { 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'; } } Diameter Minimization C Sharp Solution using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Text; using static System.Math; using static System.Console; using static HackerRankUtils; public class Solution { #region Variables int m; int n; int BestDiameter = int.MaxValue; bool toplevel; Graph BestGraph = null; public static Dictionary<Tuple<int, int>, Solution> memo = new Dictionary<Tuple<int, int>, Solution>(); public static readonly Random random = new Random(unchecked((int)0xDEADBEEF)); public static readonly Dictionary<int, List<Case>> cases = new Dictionary<int, List<Case>>(); #endregion #region Constructor static void Main(string[] args) { var sw = new Stopwatch(); sw.Start(); var input = ReadLine().Split(' '); var n = int.Parse(input[0]); var m = int.Parse(input[1]); var sol = new Solution(n, m, true); LaunchTimer(() => { Report(sol); return true; }, TimeLimit); Setup(); var g = sol.Solve(); Report(sol); #if DEBUG WriteLine(sw.Elapsed); #endif } static void Report(Solution sol) { var g = sol.BestGraph; WriteLine(sol.BestDiameter); var list = new List<int>(); for (int i = 0; i < sol.n; i++) { list.Clear(); list.AddRange(g[i]); while (list.Count < sol.m) list.Add(list[0]); WriteLine(string.Join(" ", list)); } } public static void Test() { for (int i=2; i<1000; i++) for (int j=2; j<=5 && j<=i; j++) { var sol = new Solution(i, j); sol.Solve(); } } public Solution(int n, int m, bool toplevel=false) { this.n = n; this.m = m; this.toplevel = toplevel; } #endregion public Graph Solve() { var g = SolveCore(); if (g != null) RecordGraph(g); return BestGraph; } public Graph SolveCore() { if (m >= n - 1) return Graph.Complete(n); if (m==2) { RecordGraph(Graph.CycleGraph(n, m, true)); } // Case Analysis if (cases.ContainsKey(n)) { foreach(var c in cases[n]) { if (m < c.Degree) continue; var g = c.Action(); Debug.Assert(g.Diameter() == c.Diameter); // Set the graph as an upper bound RecordGraph(g); } } // Divide and Conquer if (n % 2 == 0 && m !=2) { var sol = Recurse(n / 2, m - 1); // Diameter + 1, Degree + 1 var g = Graph.Product(sol.BestGraph, Graph.K2); Debug.Assert(g.Diameter() == sol.BestDiameter + 1); RecordGraph(g); } RecordGraph(Graph.ConnectedGraph(n,m)); /* // Iterate through multiple random graphs var limit = toplevel ? RandomIterationsTop : RandomIterations; for (int i = 0; i < limit; i++) { RecordGraph(Graph.RandomGraph(n, m, true)); RecordGraph(Graph.RandomGraph(n, m, false)); }*/ // null means we are unsure; return null; } public static Solution Recurse(int n, int m) { var tup = new Tuple<int, int>(n, m); if (memo.ContainsKey(tup)) return memo[tup]; var sol = new Solution(n / 2, 2); sol.Solve(); memo[tup] = sol; return sol; } public void Attempt4() { if (n % 2 != 0) return; var sol = Recurse(n / 2, 2); var g = Graph.Product(sol.BestGraph, Graph.K2, false); RecordGraph(g); } public void Attempt5() { if (n % 2 != 0) return; var sol = Recurse(n / 2, 2); var g0 = sol.BestGraph; var g = Graph.Product(g0, Graph.K2, true); RecordGraph(g); } public void RecordGraph(Graph g) { var diameter = g.Diameter(BestDiameter); foreach(var e in g.g) { foreach(var v in e) if (v>=g.g.Length || v<0) return; } if (g.g.Length < n) return; if (BestGraph==null || diameter < BestDiameter) { BestGraph = g; BestDiameter = diameter; } } #region Case Analysis public static void Setup() { AddCase(18, 3, 3, () => Graph.Graph33(18)); AddCase(16, 4, 2, () => Graph.G8(2)); AddCase(24, 5, 2, () => Graph.G8(3)); AddCase(4, 2, 2, () => Graph.CubeGraph(2)); AddCase(16, 4, 4, () => Graph.CubeGraph(4)); AddCase(32, 5, 5, () => Graph.CubeGraph(5)); // K3,3 = C6(1,3) AddGraph(6, 3, 2, new[,] { { 0, 1 }, { 0, 3 }, { 0, 5 }, { 1, 2 }, { 1, 4 }, { 2, 3 }, { 2, 5 }, { 3, 4 }, { 4, 5 } }); // C8(1,4) AddGraph(8, 3, 2, new[,] { { 0, 1 }, { 0, 4 }, { 0, 7 }, { 1, 2 }, { 1, 5 }, { 2, 3 }, { 2, 6 }, { 3, 4 }, { 3, 7 }, { 4, 5 }, { 5, 6 }, { 6, 7 } }); // P AddGraph(10, 3, 2, new[,] { { 0, 1 }, { 0, 4 }, { 0, 5 }, { 1, 2 }, { 1, 6 }, { 2, 3 }, { 2, 7 }, { 3, 4 }, { 3, 8 }, { 4, 9 }, { 5, 7 }, { 5, 8 }, { 6, 8 }, { 6, 9 }, { 7, 9 } }); // C = Cml8(2:0,3) //AddGraph(8, 3, 3, new[,] { { 0, 1 }, { 0, 3 }, { 0, 7 }, { 1, 2 }, { 1, 6 }, { 2, 3 }, { 2, 5 }, { 3, 4 }, { 4, 5 }, { 4, 7 }, { 5, 6 }, { 6, 7 } }); // C10(1,5) AddGraph(10, 3, 3, new[,] { { 0, 1 }, { 0, 5 }, { 0, 9 }, { 1, 2 }, { 1, 6 }, { 2, 3 }, { 2, 7 }, { 3, 4 }, { 3, 8 }, { 4, 5 }, { 4, 9 }, { 5, 6 }, { 6, 7 }, { 7, 8 }, { 8, 9 } }); // C12(1,6) AddGraph(12, 3, 3, new[,] { { 0, 1 }, { 0, 11 }, { 0, 6 }, { 1, 2 }, { 1, 7 }, { 2, 3 }, { 2, 8 }, { 3, 4 }, { 3, 9 }, { 4, 10 }, { 4, 5 }, { 5, 11 }, { 5, 6 }, { 6, 7 }, { 7, 8 }, { 8, 9 }, { 9, 10 }, { 10, 11 } }); // PP7(1,3) K2 //AddGraph(14, 3, 3, new[,] { { 0, 1 }, { 0, 6 }, { 0, 7 }, { 1, 2 }, { 1, 8 }, { 2, 3 }, { 2, 9 }, { 3, 10 }, { 3, 4 }, { 4, 11 }, { 4, 5 }, { 5, 12 }, { 5, 6 }, { 6, 13 }, { 7, 10 }, { 7, 11 }, { 8, 11 }, { 8, 12 }, { 9, 12 }, { 9, 13 }, { 10, 13 } }); // PP7(1,2) K2 //AddGraph(14, 3, 3, new[,] { { 0, 1 }, { 0, 6 }, { 0, 7 }, { 1, 2 }, { 1, 8 }, { 2, 3 }, { 2, 9 }, { 3, 10 }, { 3, 4 }, { 4, 11 }, { 4, 5 }, { 5, 12 }, { 5, 6 }, { 6, 13 }, { 7, 12 }, { 7, 9 }, { 8, 10 }, { 8, 13 }, { 9, 11 }, { 10, 12 }, { 11, 13 } }); // Heawood AddGraph(14, 3, 3, new[,] { { 0, 1 }, { 0, 13 }, { 0, 5 }, { 1, 10 }, { 1, 2 }, { 2, 3 }, { 2, 7 }, { 3, 12 }, { 3, 4 }, { 4, 5 }, { 4, 9 }, { 5, 6 }, { 6, 11 }, { 6, 7 }, { 7, 8 }, { 8, 13 }, { 8, 9 }, { 9, 10 }, { 10, 11 }, { 11, 12 }, { 12, 13 } }); // O = C6(1,2) AddGraph(6, 4, 2, new[,] { { 0, 1 }, { 0, 2 }, { 0, 4 }, { 0, 5 }, { 1, 2 }, { 1, 3 }, { 1, 5 }, { 2, 3 }, { 2, 4 }, { 3, 4 }, { 3, 5 }, { 4, 5 } }); // K4,4 = C8(1,3) AddGraph(8, 4, 2, new[,] { { 0, 1 }, { 0, 3 }, { 0, 5 }, { 0, 7 }, { 1, 2 }, { 1, 4 }, { 1, 6 }, { 2, 3 }, { 2, 5 }, { 2, 7 }, { 3, 4 }, { 3, 6 }, { 4, 5 }, { 4, 7 }, { 5, 6 }, { 6, 7 } }); // K3 × K3 AddGraph(9, 4, 2, new[,] { { 0, 1 }, { 0, 2 }, { 0, 3 }, { 0, 6 }, { 1, 2 }, { 1, 4 }, { 1, 7 }, { 2, 5 }, { 2, 8 }, { 3, 4 }, { 3, 5 }, { 3, 6 }, { 4, 5 }, { 4, 7 }, { 5, 8 }, { 6, 7 }, { 6, 8 }, { 7, 8 } }); // C11(1,3) AddGraph(11, 4, 2, new[,] { { 0, 1 }, { 0, 10 }, { 0, 3 }, { 0, 8 }, { 1, 2 }, { 1, 4 }, { 1, 9 }, { 2, 10 }, { 2, 3 }, { 2, 5 }, { 3, 4 }, { 3, 6 }, { 4, 5 }, { 4, 7 }, { 5, 6 }, { 5, 8 }, { 6, 7 }, { 6, 9 }, { 7, 10 }, { 7, 8 }, { 8, 9 }, { 9, 10 } }); // Cml15(5:1,4:2,5:3,7:4,4:4,7) AddGraph(15, 4, 2, new[,] { { 0, 1 }, { 0, 11 }, { 0, 14 }, { 0, 8 }, { 1, 2 }, { 1, 5 }, { 1, 9 }, { 2, 12 }, { 2, 3 }, { 2, 7 }, { 3, 10 }, { 3, 14 }, { 3, 4 }, { 4, 11 }, { 4, 5 }, { 4, 8 }, { 5, 13 }, { 5, 6 }, { 6, 10 }, { 6, 14 }, { 6, 7 }, { 7, 12 }, { 7, 8 }, { 8, 9 }, { 9, 10 }, { 9, 13 }, { 10, 11 }, { 11, 12 }, { 12, 13 }, { 13, 14 } }); // C14(1,7) AddGraph(14, 3, 4, new[,] { { 0, 1 }, { 0, 13 }, { 0, 7 }, { 1, 2 }, { 1, 8 }, { 2, 3 }, { 2, 9 }, { 3, 10 }, { 3, 4 }, { 4, 11 }, { 4, 5 }, { 5, 12 }, { 5, 6 }, { 6, 13 }, { 6, 7 }, { 7, 8 }, { 8, 9 }, { 9, 10 }, { 10, 11 }, { 11, 12 }, { 12, 13 } }); // C16(1,8) AddGraph(16, 3, 4, new[,] { { 0, 1 }, { 0, 15 }, { 0, 8 }, { 1, 2 }, { 1, 9 }, { 2, 10 }, { 2, 3 }, { 3, 11 }, { 3, 4 }, { 4, 12 }, { 4, 5 }, { 5, 13 }, { 5, 6 }, { 6, 14 }, { 6, 7 }, { 7, 15 }, { 7, 8 }, { 8, 9 }, { 9, 10 }, { 10, 11 }, { 11, 12 }, { 12, 13 }, { 13, 14 }, { 14, 15 } }); // PP11(1,3) K2 AddGraph(22, 3, 4, new[,] { { 0, 1 }, { 0, 10 }, { 0, 11 }, { 1, 12 }, { 1, 2 }, { 2, 13 }, { 2, 3 }, { 3, 14 }, { 3, 4 }, { 4, 15 }, { 4, 5 }, { 5, 16 }, { 5, 6 }, { 6, 17 }, { 6, 7 }, { 7, 18 }, { 7, 8 }, { 8, 19 }, { 8, 9 }, { 9, 10 }, { 9, 20 }, { 10, 21 }, { 11, 14 }, { 11, 19 }, { 12, 15 }, { 12, 20 }, { 13, 16 }, { 13, 21 }, { 14, 17 }, { 15, 18 }, { 16, 19 }, { 17, 20 }, { 18, 21 } }); // McGee = Cml24(3:1,12:2,7:0,17) AddGraph(24, 3, 4, new[,] { { 0, 1 }, { 0, 17 }, { 0, 23 }, { 1, 13 }, { 1, 2 }, { 2, 3 }, { 2, 9 }, { 3, 20 }, { 3, 4 }, { 4, 16 }, { 4, 5 }, { 5, 12 }, { 5, 6 }, { 6, 23 }, { 6, 7 }, { 7, 19 }, { 7, 8 }, { 8, 15 }, { 8, 9 }, { 9, 10 }, { 10, 11 }, { 10, 22 }, { 11, 12 }, { 11, 18 }, { 12, 13 }, { 13, 14 }, { 14, 15 }, { 14, 21 }, { 15, 16 }, { 16, 17 }, { 17, 18 }, { 18, 19 }, { 19, 20 }, { 20, 21 }, { 21, 22 }, { 22, 23 } }); // Tutte-Coxeter = Cml30(6:1,17:2,21:3,7) AddGraph(30, 3, 4, new[,] { { 0, 1 }, { 0, 13 }, { 0, 29 }, { 1, 18 }, { 1, 2 }, { 2, 23 }, { 2, 3 }, { 3, 10 }, { 3, 4 }, { 4, 27 }, { 4, 5 }, { 5, 14 }, { 5, 6 }, { 6, 19 }, { 6, 7 }, { 7, 24 }, { 7, 8 }, { 8, 29 }, { 8, 9 }, { 9, 10 }, { 9, 16 }, { 10, 11 }, { 11, 12 }, { 11, 20 }, { 12, 13 }, { 12, 25 }, { 13, 14 }, { 14, 15 }, { 15, 16 }, { 15, 22 }, { 16, 17 }, { 17, 18 }, { 17, 26 }, { 18, 19 }, { 19, 20 }, { 20, 21 }, { 21, 22 }, { 21, 28 }, { 22, 23 }, { 23, 24 }, { 24, 25 }, { 25, 26 }, { 26, 27 }, { 27, 28 }, { 28, 29 } }); // K2 × K3,3 AddGraph(12, 4, 3, new[,] { { 0, 1 }, { 0, 10 }, { 0, 2 }, { 0, 6 }, { 1, 11 }, { 1, 3 }, { 1, 7 }, { 2, 3 }, { 2, 4 }, { 2, 8 }, { 3, 5 }, { 3, 9 }, { 4, 10 }, { 4, 5 }, { 4, 6 }, { 5, 11 }, { 5, 7 }, { 6, 7 }, { 6, 8 }, { 7, 9 }, { 8, 10 }, { 8, 9 }, { 9, 11 }, { 10, 11 } }); // K2 × P AddGraph(20, 4, 3, new[,] { { 0, 1 }, { 0, 10 }, { 0, 2 }, { 0, 8 }, { 1, 11 }, { 1, 3 }, { 1, 9 }, { 2, 12 }, { 2, 3 }, { 2, 4 }, { 3, 13 }, { 3, 5 }, { 4, 14 }, { 4, 5 }, { 4, 6 }, { 5, 15 }, { 5, 7 }, { 6, 16 }, { 6, 7 }, { 6, 8 }, { 7, 17 }, { 7, 9 }, { 8, 18 }, { 8, 9 }, { 9, 19 }, { 10, 11 }, { 10, 14 }, { 10, 16 }, { 11, 15 }, { 11, 17 }, { 12, 13 }, { 12, 16 }, { 12, 18 }, { 13, 17 }, { 13, 19 }, { 14, 15 }, { 14, 18 }, { 15, 19 }, { 16, 17 }, { 18, 19 } }); // Moebius D //AddGraph(20, 4, 3, new[,] { { 0, 10 }, { 0, 16 }, { 0, 19 }, { 0, 4 }, { 1, 11 }, { 1, 19 }, { 1, 2 }, { 1, 3 }, { 2, 12 }, { 2, 18 }, { 2, 6 }, { 3, 13 }, { 3, 4 }, { 3, 5 }, { 4, 14 }, { 4, 8 }, { 5, 15 }, { 5, 6 }, { 5, 7 }, { 6, 10 }, { 6, 16 }, { 7, 17 }, { 7, 8 }, { 7, 9 }, { 8, 12 }, { 8, 18 }, { 9, 10 }, { 9, 11 }, { 9, 19 }, { 10, 14 }, { 11, 12 }, { 11, 13 }, { 12, 16 }, { 13, 14 }, { 13, 15 }, { 14, 18 }, { 15, 16 }, { 15, 17 }, { 17, 18 }, { 17, 19 } }); // PP7(1,2,3) K3 AddGraph(21, 4, 3, new[,] { { 0, 1 }, { 0, 14 }, { 0, 6 }, { 0, 7 }, { 1, 15 }, { 1, 2 }, { 1, 8 }, { 2, 16 }, { 2, 3 }, { 2, 9 }, { 3, 10 }, { 3, 17 }, { 3, 4 }, { 4, 11 }, { 4, 18 }, { 4, 5 }, { 5, 12 }, { 5, 19 }, { 5, 6 }, { 6, 13 }, { 6, 20 }, { 7, 12 }, { 7, 14 }, { 7, 9 }, { 8, 10 }, { 8, 13 }, { 8, 15 }, { 9, 11 }, { 9, 16 }, { 10, 12 }, { 10, 17 }, { 11, 13 }, { 11, 18 }, { 12, 19 }, { 13, 20 }, { 14, 17 }, { 14, 18 }, { 15, 18 }, { 15, 19 }, { 16, 19 }, { 16, 20 }, { 17, 20 } }); // (4,6)-cage AddGraph(26, 4, 3, new[,] { { 0, 1 }, { 0, 17 }, { 0, 25 }, { 0, 5 }, { 1, 10 }, { 1, 2 }, { 1, 22 }, { 2, 19 }, { 2, 3 }, { 2, 7 }, { 3, 12 }, { 3, 24 }, { 3, 4 }, { 4, 21 }, { 4, 5 }, { 4, 9 }, { 5, 14 }, { 5, 6 }, { 6, 11 }, { 6, 23 }, { 6, 7 }, { 7, 16 }, { 7, 8 }, { 8, 13 }, { 8, 25 }, { 8, 9 }, { 9, 10 }, { 9, 18 }, { 10, 11 }, { 10, 15 }, { 11, 12 }, { 11, 20 }, { 12, 13 }, { 12, 17 }, { 13, 14 }, { 13, 22 }, { 14, 15 }, { 14, 19 }, { 15, 16 }, { 15, 24 }, { 16, 17 }, { 16, 21 }, { 17, 18 }, { 18, 19 }, { 18, 23 }, { 19, 20 }, { 20, 21 }, { 20, 25 }, { 21, 22 }, { 22, 23 }, { 23, 24 }, { 24, 25 } }); // PP7(1,2,3,2) C4 AddGraph(28, 4, 3, new[,] { { 0, 1 }, { 0, 21 }, { 0, 6 }, { 0, 7 }, { 1, 2 }, { 1, 22 }, { 1, 8 }, { 2, 23 }, { 2, 3 }, { 2, 9 }, { 3, 10 }, { 3, 24 }, { 3, 4 }, { 4, 11 }, { 4, 25 }, { 4, 5 }, { 5, 12 }, { 5, 26 }, { 5, 6 }, { 6, 13 }, { 6, 27 }, { 7, 12 }, { 7, 14 }, { 7, 9 }, { 8, 10 }, { 8, 13 }, { 8, 15 }, { 9, 11 }, { 9, 16 }, { 10, 12 }, { 10, 17 }, { 11, 13 }, { 11, 18 }, { 12, 19 }, { 13, 20 }, { 14, 17 }, { 14, 18 }, { 14, 21 }, { 15, 18 }, { 15, 19 }, { 15, 22 }, { 16, 19 }, { 16, 20 }, { 16, 23 }, { 17, 20 }, { 17, 24 }, { 18, 25 }, { 19, 26 }, { 20, 27 }, { 21, 23 }, { 21, 26 }, { 22, 24 }, { 22, 27 }, { 23, 25 }, { 24, 26 }, { 25, 27 } }); // PP9(1,3) K2 U PP9(2,4) K2 AddGraph(18, 5, 2, new[,] { { 0, 1 }, { 0, 2 }, { 0, 7 }, { 0, 8 }, { 0, 9 }, { 1, 10 }, { 1, 2 }, { 1, 3 }, { 1, 8 }, { 2, 11 }, { 2, 3 }, { 2, 4 }, { 3, 12 }, { 3, 4 }, { 3, 5 }, { 4, 13 }, { 4, 5 }, { 4, 6 }, { 5, 14 }, { 5, 6 }, { 5, 7 }, { 6, 15 }, { 6, 7 }, { 6, 8 }, { 7, 16 }, { 7, 8 }, { 8, 17 }, { 9, 12 }, { 9, 13 }, { 9, 14 }, { 9, 15 }, { 10, 13 }, { 10, 14 }, { 10, 15 }, { 10, 16 }, { 11, 14 }, { 11, 15 }, { 11, 16 }, { 11, 17 }, { 12, 15 }, { 12, 16 }, { 12, 17 }, { 13, 16 }, { 13, 17 }, { 14, 17 } }); // D AddGraph(20, 3, 5, new[,] { { 0, 16 }, { 0, 19 }, { 0, 4 }, { 1, 19 }, { 1, 2 }, { 1, 3 }, { 2, 18 }, { 2, 6 }, { 3, 4 }, { 3, 5 }, { 4, 8 }, { 5, 6 }, { 5, 7 }, { 6, 10 }, { 7, 8 }, { 7, 9 }, { 8, 12 }, { 9, 10 }, { 9, 11 }, { 10, 14 }, { 11, 12 }, { 11, 13 }, { 12, 16 }, { 13, 14 }, { 13, 15 }, { 14, 18 }, { 15, 16 }, { 15, 17 }, { 17, 18 }, { 17, 19 } }); // C × K2 AddGraph(16, 4, 4, new[,] { { 0, 1 }, { 0, 3 }, { 0, 7 }, { 0, 8 }, { 1, 2 }, { 1, 6 }, { 1, 9 }, { 2, 10 }, { 2, 3 }, { 2, 5 }, { 3, 11 }, { 3, 4 }, { 4, 12 }, { 4, 5 }, { 4, 7 }, { 5, 13 }, { 5, 6 }, { 6, 14 }, { 6, 7 }, { 7, 15 }, { 8, 11 }, { 8, 15 }, { 8, 9 }, { 9, 10 }, { 9, 14 }, { 10, 11 }, { 10, 13 }, { 11, 12 }, { 12, 13 }, { 12, 15 }, { 13, 14 }, { 14, 15 } }); // C5 × C5 AddGraph(25, 4, 4, new[,] { { 0, 1 }, { 0, 20 }, { 0, 4 }, { 0, 5 }, { 1, 2 }, { 1, 21 }, { 1, 6 }, { 2, 22 }, { 2, 3 }, { 2, 7 }, { 3, 23 }, { 3, 4 }, { 3, 8 }, { 4, 24 }, { 4, 9 }, { 5, 10 }, { 5, 6 }, { 5, 9 }, { 6, 11 }, { 6, 7 }, { 7, 12 }, { 7, 8 }, { 8, 13 }, { 8, 9 }, { 9, 14 }, { 10, 11 }, { 10, 14 }, { 10, 15 }, { 11, 12 }, { 11, 16 }, { 12, 13 }, { 12, 17 }, { 13, 14 }, { 13, 18 }, { 14, 19 }, { 15, 16 }, { 15, 19 }, { 15, 20 }, { 16, 17 }, { 16, 21 }, { 17, 18 }, { 17, 22 }, { 18, 19 }, { 18, 23 }, { 19, 24 }, { 20, 21 }, { 20, 24 }, { 21, 22 }, { 22, 23 }, { 23, 24 } }); // PP7(1,3) K2 × K2 //AddGraph(28, 4, 4, new[,] { { 0, 1 }, { 0, 14 }, { 0, 6 }, { 0, 7 }, { 1, 15 }, { 1, 2 }, { 1, 8 }, { 2, 16 }, { 2, 3 }, { 2, 9 }, { 3, 10 }, { 3, 17 }, { 3, 4 }, { 4, 11 }, { 4, 18 }, { 4, 5 }, { 5, 12 }, { 5, 19 }, { 5, 6 }, { 6, 13 }, { 6, 20 }, { 7, 10 }, { 7, 11 }, { 7, 21 }, { 8, 11 }, { 8, 12 }, { 8, 22 }, { 9, 12 }, { 9, 13 }, { 9, 23 }, { 10, 13 }, { 10, 24 }, { 11, 25 }, { 12, 26 }, { 13, 27 }, { 14, 15 }, { 14, 20 }, { 14, 21 }, { 15, 16 }, { 15, 22 }, { 16, 17 }, { 16, 23 }, { 17, 18 }, { 17, 24 }, { 18, 19 }, { 18, 25 }, { 19, 20 }, { 19, 26 }, { 20, 27 }, { 21, 24 }, { 21, 25 }, { 22, 25 }, { 22, 26 }, { 23, 26 }, { 23, 27 }, { 24, 27 } }); // Heawood × K2 AddGraph(28, 4, 4, new[,] { { 0, 1 }, { 0, 13 }, { 0, 14 }, { 0, 5 }, { 1, 10 }, { 1, 15 }, { 1, 2 }, { 2, 16 }, { 2, 3 }, { 2, 7 }, { 3, 12 }, { 3, 17 }, { 3, 4 }, { 4, 18 }, { 4, 5 }, { 4, 9 }, { 5, 19 }, { 5, 6 }, { 6, 11 }, { 6, 20 }, { 6, 7 }, { 7, 21 }, { 7, 8 }, { 8, 13 }, { 8, 22 }, { 8, 9 }, { 9, 10 }, { 9, 23 }, { 10, 11 }, { 10, 24 }, { 11, 12 }, { 11, 25 }, { 12, 13 }, { 12, 26 }, { 13, 27 }, { 14, 15 }, { 14, 19 }, { 14, 27 }, { 15, 16 }, { 15, 24 }, { 16, 17 }, { 16, 21 }, { 17, 18 }, { 17, 26 }, { 18, 19 }, { 18, 23 }, { 19, 20 }, { 20, 21 }, { 20, 25 }, { 21, 22 }, { 22, 23 }, { 22, 27 }, { 23, 24 }, { 24, 25 }, { 25, 26 }, { 26, 27 } }); // PP9(1,2,3,4) C4 AddGraph(36, 4, 4, new[,] { { 0, 1 }, { 0, 27 }, { 0, 8 }, { 0, 9 }, { 1, 10 }, { 1, 2 }, { 1, 28 }, { 2, 11 }, { 2, 29 }, { 2, 3 }, { 3, 12 }, { 3, 30 }, { 3, 4 }, { 4, 13 }, { 4, 31 }, { 4, 5 }, { 5, 14 }, { 5, 32 }, { 5, 6 }, { 6, 15 }, { 6, 33 }, { 6, 7 }, { 7, 16 }, { 7, 34 }, { 7, 8 }, { 8, 17 }, { 8, 35 }, { 9, 11 }, { 9, 16 }, { 9, 18 }, { 10, 12 }, { 10, 17 }, { 10, 19 }, { 11, 13 }, { 11, 20 }, { 12, 14 }, { 12, 21 }, { 13, 15 }, { 13, 22 }, { 14, 16 }, { 14, 23 }, { 15, 17 }, { 15, 24 }, { 16, 25 }, { 17, 26 }, { 18, 21 }, { 18, 24 }, { 18, 27 }, { 19, 22 }, { 19, 25 }, { 19, 28 }, { 20, 23 }, { 20, 26 }, { 20, 29 }, { 21, 24 }, { 21, 30 }, { 22, 25 }, { 22, 31 }, { 23, 26 }, { 23, 32 }, { 24, 33 }, { 25, 34 }, { 26, 35 }, { 27, 31 }, { 27, 32 }, { 28, 32 }, { 28, 33 }, { 29, 33 }, { 29, 34 }, { 30, 34 }, { 30, 35 }, { 31, 35 } }); // PP9(1,2,3,4,2) C5 AddGraph(45, 4, 4, new[,] { { 0, 1 }, { 0, 36 }, { 0, 8 }, { 0, 9 }, { 1, 10 }, { 1, 2 }, { 1, 37 }, { 2, 11 }, { 2, 3 }, { 2, 38 }, { 3, 12 }, { 3, 39 }, { 3, 4 }, { 4, 13 }, { 4, 40 }, { 4, 5 }, { 5, 14 }, { 5, 41 }, { 5, 6 }, { 6, 15 }, { 6, 42 }, { 6, 7 }, { 7, 16 }, { 7, 43 }, { 7, 8 }, { 8, 17 }, { 8, 44 }, { 9, 11 }, { 9, 16 }, { 9, 18 }, { 10, 12 }, { 10, 17 }, { 10, 19 }, { 11, 13 }, { 11, 20 }, { 12, 14 }, { 12, 21 }, { 13, 15 }, { 13, 22 }, { 14, 16 }, { 14, 23 }, { 15, 17 }, { 15, 24 }, { 16, 25 }, { 17, 26 }, { 18, 21 }, { 18, 24 }, { 18, 27 }, { 19, 22 }, { 19, 25 }, { 19, 28 }, { 20, 23 }, { 20, 26 }, { 20, 29 }, { 21, 24 }, { 21, 30 }, { 22, 25 }, { 22, 31 }, { 23, 26 }, { 23, 32 }, { 24, 33 }, { 25, 34 }, { 26, 35 }, { 27, 31 }, { 27, 32 }, { 27, 36 }, { 28, 32 }, { 28, 33 }, { 28, 37 }, { 29, 33 }, { 29, 34 }, { 29, 38 }, { 30, 34 }, { 30, 35 }, { 30, 39 }, { 31, 35 }, { 31, 40 }, { 32, 41 }, { 33, 42 }, { 34, 43 }, { 35, 44 }, { 36, 38 }, { 36, 43 }, { 37, 39 }, { 37, 44 }, { 38, 40 }, { 39, 41 }, { 40, 42 }, { 41, 43 }, { 42, 44 } }); // PP11(1,2,4,3,5) C5 AddGraph(55, 4, 4, new[,] { { 0, 1 }, { 0, 10 }, { 0, 11 }, { 0, 44 }, { 1, 12 }, { 1, 2 }, { 1, 45 }, { 2, 13 }, { 2, 3 }, { 2, 46 }, { 3, 14 }, { 3, 4 }, { 3, 47 }, { 4, 15 }, { 4, 48 }, { 4, 5 }, { 5, 16 }, { 5, 49 }, { 5, 6 }, { 6, 17 }, { 6, 50 }, { 6, 7 }, { 7, 18 }, { 7, 51 }, { 7, 8 }, { 8, 19 }, { 8, 52 }, { 8, 9 }, { 9, 10 }, { 9, 20 }, { 9, 53 }, { 10, 21 }, { 10, 54 }, { 11, 13 }, { 11, 20 }, { 11, 22 }, { 12, 14 }, { 12, 21 }, { 12, 23 }, { 13, 15 }, { 13, 24 }, { 14, 16 }, { 14, 25 }, { 15, 17 }, { 15, 26 }, { 16, 18 }, { 16, 27 }, { 17, 19 }, { 17, 28 }, { 18, 20 }, { 18, 29 }, { 19, 21 }, { 19, 30 }, { 20, 31 }, { 21, 32 }, { 22, 26 }, { 22, 29 }, { 22, 33 }, { 23, 27 }, { 23, 30 }, { 23, 34 }, { 24, 28 }, { 24, 31 }, { 24, 35 }, { 25, 29 }, { 25, 32 }, { 25, 36 }, { 26, 30 }, { 26, 37 }, { 27, 31 }, { 27, 38 }, { 28, 32 }, { 28, 39 }, { 29, 40 }, { 30, 41 }, { 31, 42 }, { 32, 43 }, { 33, 36 }, { 33, 41 }, { 33, 44 }, { 34, 37 }, { 34, 42 }, { 34, 45 }, { 35, 38 }, { 35, 43 }, { 35, 46 }, { 36, 39 }, { 36, 47 }, { 37, 40 }, { 37, 48 }, { 38, 41 }, { 38, 49 }, { 39, 42 }, { 39, 50 }, { 40, 43 }, { 40, 51 }, { 41, 52 }, { 42, 53 }, { 43, 54 }, { 44, 49 }, { 44, 50 }, { 45, 50 }, { 45, 51 }, { 46, 51 }, { 46, 52 }, { 47, 52 }, { 47, 53 }, { 48, 53 }, { 48, 54 }, { 49, 54 } }); // PP13(1,5,4,2,3,6) C6 AddGraph(78, 4, 4, new[,] { { 0, 1 }, { 0, 12 }, { 0, 13 }, { 0, 65 }, { 1, 14 }, { 1, 2 }, { 1, 66 }, { 2, 15 }, { 2, 3 }, { 2, 67 }, { 3, 16 }, { 3, 4 }, { 3, 68 }, { 4, 17 }, { 4, 5 }, { 4, 69 }, { 5, 18 }, { 5, 6 }, { 5, 70 }, { 6, 19 }, { 6, 7 }, { 6, 71 }, { 7, 20 }, { 7, 72 }, { 7, 8 }, { 8, 21 }, { 8, 73 }, { 8, 9 }, { 9, 10 }, { 9, 22 }, { 9, 74 }, { 10, 11 }, { 10, 23 }, { 10, 75 }, { 11, 12 }, { 11, 24 }, { 11, 76 }, { 12, 25 }, { 12, 77 }, { 13, 18 }, { 13, 21 }, { 13, 26 }, { 14, 19 }, { 14, 22 }, { 14, 27 }, { 15, 20 }, { 15, 23 }, { 15, 28 }, { 16, 21 }, { 16, 24 }, { 16, 29 }, { 17, 22 }, { 17, 25 }, { 17, 30 }, { 18, 23 }, { 18, 31 }, { 19, 24 }, { 19, 32 }, { 20, 25 }, { 20, 33 }, { 21, 34 }, { 22, 35 }, { 23, 36 }, { 24, 37 }, { 25, 38 }, { 26, 30 }, { 26, 35 }, { 26, 39 }, { 27, 31 }, { 27, 36 }, { 27, 40 }, { 28, 32 }, { 28, 37 }, { 28, 41 }, { 29, 33 }, { 29, 38 }, { 29, 42 }, { 30, 34 }, { 30, 43 }, { 31, 35 }, { 31, 44 }, { 32, 36 }, { 32, 45 }, { 33, 37 }, { 33, 46 }, { 34, 38 }, { 34, 47 }, { 35, 48 }, { 36, 49 }, { 37, 50 }, { 38, 51 }, { 39, 41 }, { 39, 50 }, { 39, 52 }, { 40, 42 }, { 40, 51 }, { 40, 53 }, { 41, 43 }, { 41, 54 }, { 42, 44 }, { 42, 55 }, { 43, 45 }, { 43, 56 }, { 44, 46 }, { 44, 57 }, { 45, 47 }, { 45, 58 }, { 46, 48 }, { 46, 59 }, { 47, 49 }, { 47, 60 }, { 48, 50 }, { 48, 61 }, { 49, 51 }, { 49, 62 }, { 50, 63 }, { 51, 64 }, { 52, 55 }, { 52, 62 }, { 52, 65 }, { 53, 56 }, { 53, 63 }, { 53, 66 }, { 54, 57 }, { 54, 64 }, { 54, 67 }, { 55, 58 }, { 55, 68 }, { 56, 59 }, { 56, 69 }, { 57, 60 }, { 57, 70 }, { 58, 61 }, { 58, 71 }, { 59, 62 }, { 59, 72 }, { 60, 63 }, { 60, 73 }, { 61, 64 }, { 61, 74 }, { 62, 75 }, { 63, 76 }, { 64, 77 }, { 65, 71 }, { 65, 72 }, { 66, 72 }, { 66, 73 }, { 67, 73 }, { 67, 74 }, { 68, 74 }, { 68, 75 }, { 69, 75 }, { 69, 76 }, { 70, 76 }, { 70, 77 }, { 71, 77 } }); // Robertson-Wegner AddGraph(30, 5, 3, new[,] { { 0, 10 }, { 0, 15 }, { 0, 19 }, { 0, 2 }, { 0, 29 }, { 1, 12 }, { 1, 2 }, { 1, 21 }, { 1, 28 }, { 1, 4 }, { 2, 26 }, { 2, 3 }, { 2, 8 }, { 3, 13 }, { 3, 18 }, { 3, 22 }, { 3, 5 }, { 4, 15 }, { 4, 24 }, { 4, 5 }, { 4, 7 }, { 5, 11 }, { 5, 29 }, { 5, 6 }, { 6, 16 }, { 6, 21 }, { 6, 25 }, { 6, 8 }, { 7, 10 }, { 7, 18 }, { 7, 27 }, { 7, 8 }, { 8, 14 }, { 8, 9 }, { 9, 11 }, { 9, 19 }, { 9, 24 }, { 9, 28 }, { 10, 11 }, { 10, 13 }, { 10, 21 }, { 11, 12 }, { 11, 17 }, { 12, 14 }, { 12, 22 }, { 12, 27 }, { 13, 14 }, { 13, 16 }, { 13, 24 }, { 14, 15 }, { 14, 20 }, { 15, 17 }, { 15, 25 }, { 16, 17 }, { 16, 19 }, { 16, 27 }, { 17, 18 }, { 17, 23 }, { 18, 20 }, { 18, 28 }, { 19, 20 }, { 19, 22 }, { 20, 21 }, { 20, 26 }, { 21, 23 }, { 22, 23 }, { 22, 25 }, { 23, 24 }, { 23, 29 }, { 24, 26 }, { 25, 26 }, { 25, 28 }, { 26, 27 }, { 27, 29 }, { 28, 29 } }); // PP9(1,2,3,4) K4 AddGraph(36, 5, 3, new[,] { { 0, 1 }, { 0, 18 }, { 0, 27 }, { 0, 8 }, { 0, 9 }, { 1, 10 }, { 1, 19 }, { 1, 2 }, { 1, 28 }, { 2, 11 }, { 2, 20 }, { 2, 29 }, { 2, 3 }, { 3, 12 }, { 3, 21 }, { 3, 30 }, { 3, 4 }, { 4, 13 }, { 4, 22 }, { 4, 31 }, { 4, 5 }, { 5, 14 }, { 5, 23 }, { 5, 32 }, { 5, 6 }, { 6, 15 }, { 6, 24 }, { 6, 33 }, { 6, 7 }, { 7, 16 }, { 7, 25 }, { 7, 34 }, { 7, 8 }, { 8, 17 }, { 8, 26 }, { 8, 35 }, { 9, 11 }, { 9, 16 }, { 9, 18 }, { 9, 27 }, { 10, 12 }, { 10, 17 }, { 10, 19 }, { 10, 28 }, { 11, 13 }, { 11, 20 }, { 11, 29 }, { 12, 14 }, { 12, 21 }, { 12, 30 }, { 13, 15 }, { 13, 22 }, { 13, 31 }, { 14, 16 }, { 14, 23 }, { 14, 32 }, { 15, 17 }, { 15, 24 }, { 15, 33 }, { 16, 25 }, { 16, 34 }, { 17, 26 }, { 17, 35 }, { 18, 21 }, { 18, 24 }, { 18, 27 }, { 19, 22 }, { 19, 25 }, { 19, 28 }, { 20, 23 }, { 20, 26 }, { 20, 29 }, { 21, 24 }, { 21, 30 }, { 22, 25 }, { 22, 31 }, { 23, 26 }, { 23, 32 }, { 24, 33 }, { 25, 34 }, { 26, 35 }, { 27, 31 }, { 27, 32 }, { 28, 32 }, { 28, 33 }, { 29, 33 }, { 29, 34 }, { 30, 34 }, { 30, 35 }, { 31, 35 } }); // PP7(1,2,3,2) C4 × K2 AddGraph(56, 5, 4, new[,] { { 0, 1 }, { 0, 21 }, { 0, 28 }, { 0, 6 }, { 0, 7 }, { 1, 2 }, { 1, 22 }, { 1, 29 }, { 1, 8 }, { 2, 23 }, { 2, 3 }, { 2, 30 }, { 2, 9 }, { 3, 10 }, { 3, 24 }, { 3, 31 }, { 3, 4 }, { 4, 11 }, { 4, 25 }, { 4, 32 }, { 4, 5 }, { 5, 12 }, { 5, 26 }, { 5, 33 }, { 5, 6 }, { 6, 13 }, { 6, 27 }, { 6, 34 }, { 7, 12 }, { 7, 14 }, { 7, 35 }, { 7, 9 }, { 8, 10 }, { 8, 13 }, { 8, 15 }, { 8, 36 }, { 9, 11 }, { 9, 16 }, { 9, 37 }, { 10, 12 }, { 10, 17 }, { 10, 38 }, { 11, 13 }, { 11, 18 }, { 11, 39 }, { 12, 19 }, { 12, 40 }, { 13, 20 }, { 13, 41 }, { 14, 17 }, { 14, 18 }, { 14, 21 }, { 14, 42 }, { 15, 18 }, { 15, 19 }, { 15, 22 }, { 15, 43 }, { 16, 19 }, { 16, 20 }, { 16, 23 }, { 16, 44 }, { 17, 20 }, { 17, 24 }, { 17, 45 }, { 18, 25 }, { 18, 46 }, { 19, 26 }, { 19, 47 }, { 20, 27 }, { 20, 48 }, { 21, 23 }, { 21, 26 }, { 21, 49 }, { 22, 24 }, { 22, 27 }, { 22, 50 }, { 23, 25 }, { 23, 51 }, { 24, 26 }, { 24, 52 }, { 25, 27 }, { 25, 53 }, { 26, 54 }, { 27, 55 }, { 28, 29 }, { 28, 34 }, { 28, 35 }, { 28, 49 }, { 29, 30 }, { 29, 36 }, { 29, 50 }, { 30, 31 }, { 30, 37 }, { 30, 51 }, { 31, 32 }, { 31, 38 }, { 31, 52 }, { 32, 33 }, { 32, 39 }, { 32, 53 }, { 33, 34 }, { 33, 40 }, { 33, 54 }, { 34, 41 }, { 34, 55 }, { 35, 37 }, { 35, 40 }, { 35, 42 }, { 36, 38 }, { 36, 41 }, { 36, 43 }, { 37, 39 }, { 37, 44 }, { 38, 40 }, { 38, 45 }, { 39, 41 }, { 39, 46 }, { 40, 47 }, { 41, 48 }, { 42, 45 }, { 42, 46 }, { 42, 49 }, { 43, 46 }, { 43, 47 }, { 43, 50 }, { 44, 47 }, { 44, 48 }, { 44, 51 }, { 45, 48 }, { 45, 52 }, { 46, 53 }, { 47, 54 }, { 48, 55 }, { 49, 51 }, { 49, 54 }, { 50, 52 }, { 50, 55 }, { 51, 53 }, { 52, 54 }, { 53, 55 } }); } public static void AddGraph(int n, int deg, int diam, int[,] array) { AddCase(new Case { N = n, Degree = deg, Diameter = diam, Action = () => { var g = new Graph(n, deg); int len = array.GetLength(0); for (int i = 0; i < len; i++) g.AddBidirectionalEdge(array[i, 0], array[i, 1]); return g; }, }); } public static void AddCase(int n, int m, int diam, Func<Graph> action) { AddCase(new Case { N= n, Degree =m, Diameter = diam, Action = action, }); } public static void AddCase(Case c) { if (!cases.ContainsKey(c.N)) cases[c.N] = new List<Case>(); cases[c.N].Add(c); } public class Case { public int N; public int Degree; public int Diameter; public Func<Graph> Action; } #endregion public class Graph { int m; int n; int version; public List<int>[] g; public Graph(int n, int m) { this.n = n; this.m = m; g = new List<int>[n]; for (int i = 0; i < n; i++) g[i] = new List<int>(m); } public List<int> this[int index] => g[index]; public static Graph CubeGraph(int m) { var n = 1 << m; var g = new Graph(n, m); for(int i=0; i<n; i++) { for (int j=0; j<m; j++) g[i].Add(i ^ (1<<j)); } return g; } public static Graph RandomGraph(int n, int degree, bool logN) { var g = CycleGraph(n, degree); if (degree == 1) return g; // Add second edges if (logN) g.ReduceDiameterToLogN(); // Add random edges for (int i = 0; i < n; i++) { var list = g[i]; while (list.Count < degree) { // Excess edges if (list.Count >= n - 1) { list.Add((i + random.Next(1, n)) % n); continue; } int attach = random.Next(0, n - 1 - list.Count); int attach2 = attach; if (attach >= i) attach2++; foreach (var v in list) if (attach >= v) attach2++; list.Add(attach2); } } return g; } public int FastDiameter() { throw new NotImplementedException(); } void ReduceDiameterToLogN() { int head = 0; int[] next = new int[n]; next[n - 1] = -1; for (int i = 0; i+1< n; i++) next[i] = i + 1; while (head != -1) { var cur = head; var prev = -1; int headorig = head; while (cur != -1) { int tmp = cur; cur = next[cur]!=-1 ? next[next[cur]] : -1; if (prev == -1) head = next[tmp]; else next[prev] = next[tmp]; next[tmp] = cur; g[tmp].Add(cur != -1 ? cur : head != -1 && g[tmp].Contains(headorig) ? head : headorig); } } } // http://combinatoricswiki.org/wiki/The_Degree/Diameter_Problem static double MaximumOrderOfGraph(int degree, int diameter) { // Moore bound return (degree * Pow(degree - 1, diameter) - 2) / (degree - 2); // Undirected graphs // complete graphs on d+1 vertices // cycles on 2k+1 vertices (k=diameter) // diameter2 - Peterseng graph // no moore graphs for K>2 amd d>2 } static double MaximumOrderOfDirectedGraph(int degree, int diameter) { // Moore bound return (Pow(degree, diameter + 1) - 1) / (degree - 1); // Directed graphs // complete digraphs on d+1 vertices // directed cycles on k+1 vertices (k=diameter) // no moore graphs for K>1 amd d>1 } // cube n=2^k nodes with both diameter and degree k / in digraph degree might equal 2k // connect any two nodes whose index differ in only one digit ( i ^ j ) & (i ^ j) - 1 == 0 public int Diameter(int abortBound = int.MaxValue) { // Could use bitarray var visited = new int[g.Length]; var queue = new Queue<int>(); int maxDiameter = 0; for (int i = 0; i < n; i++) { Array.Clear(visited, 0, visited.Length); queue.Enqueue(i); visited[i] = 1; while (queue.Count > 0) { var pop = queue.Dequeue(); var popdist = visited[pop]; foreach (var child in g[pop]) { if (visited[child] != 0) continue; visited[child] = popdist + 1; queue.Enqueue(child); if (popdist > maxDiameter) { maxDiameter = popdist; if (maxDiameter >= abortBound) return maxDiameter; } } } } return maxDiameter; } //http://research.nii.ac.jp/graphgolf/2015/candar15/graphgolf2015-mizuno.pdf public void AddBidirectionalEdge(int i, int j) { if (i == j) return; if (!g[i].Contains(j)) g[i].Add(j); if (!g[j].Contains(i)) g[j].Add(i); } public static readonly Graph K2 = Complete(2); public static Graph Complete(int n) { // Degree n-1 // Diameter 1 var g = new Graph(n, n - 1); for (int i=0; i<n; i++) for (int j=i+1; j<n; j++) g.AddBidirectionalEdge(i, j); return g; } public static Graph Graph33(int n) { // Degree and diameter 3 int[] array = null; switch(n) { case 8: array = new[] {6,3,4,1,2,7,0,5}; break; case 10: array = new[] {7,6,5,9,8,2,1,0,3,4}; break; case 12: array = new[] { 10, 3, 8, 1, 6, 11, 4, 9, 2, 7, 0, 5 }; break; case 14: array = new[] { 5, 10, 7, 12, 9, 0, 11, 2, 13, 4, 1, 6, 3, 8 }; break; case 18: array = new[] { 14, 5, 9, 16, 12, 1, 11, 15, 13, 2, 17, 6, 4, 8, 0, 7, 3, 10, }; break; } if (array == null) return null; var g = CycleGraph(n,3,true); for (int i = 0; i < array.Length; i++) g.AddBidirectionalEdge(i, array[i]); return g; } public static Graph CycleGraph(int n, int m=1, bool bidrectional = false) { var g = new Graph(n, m); g[n - 1].Add(0); for (int i = 1; i < n; i++) g[i - 1].Add(i); if (bidrectional) { g[0].Add(n-1); for (int i = 1; i< n; i++) g[i].Add(i-1); } return g; } public static Graph ConnectedGraph(int n, int m) { var g = new Graph(n, m); for (int i=0; i<n; i++) for (int j=0; j<m; j++) { g[i].Add((i*m+j+Extra)%n); } return g; } public static Graph G8(int k) { // New order = 8 * k // New degree = k + 2 // Diameter = 2 var g8 = new Graph(8 * k, k + 2); for (int i = 0; i < k; i++) { g8.AddBidirectionalEdge(i * 8 + 0, i * 8 + 2); g8.AddBidirectionalEdge(i * 8 + 0, i * 8 + 3); g8.AddBidirectionalEdge(i * 8 + 0, i * 8 + 4); g8.AddBidirectionalEdge(i * 8 + 1, i * 8 + 2); g8.AddBidirectionalEdge(i * 8 + 1, i * 8 + 3); g8.AddBidirectionalEdge(i * 8 + 1, i * 8 + 4); g8.AddBidirectionalEdge(i * 8 + 2, i * 8 + 5); g8.AddBidirectionalEdge(i * 8 + 3, i * 8 + 6); g8.AddBidirectionalEdge(i * 8 + 4, i * 8 + 7); g8.AddBidirectionalEdge(i * 8 + 5, i * 8 + 6); g8.AddBidirectionalEdge(i * 8 + 5, i * 8 + 7); g8.AddBidirectionalEdge(i * 8 + 6, i * 8 + 7); } for (int i=0; i<k; i++) for (int j=0; j<k; j++) { if (i == j) continue; g8.AddBidirectionalEdge(i * 8 + 0, j * 8 + 1); g8.AddBidirectionalEdge(i * 8 + 1, j * 8 + 0); g8.AddBidirectionalEdge(i * 8 + 2, j * 8 + 6); g8.AddBidirectionalEdge(i * 8 + 3, j * 8 + 7); g8.AddBidirectionalEdge(i * 8 + 4, j * 8 + 5); g8.AddBidirectionalEdge(i * 8 + 5, j * 8 + 4); g8.AddBidirectionalEdge(i * 8 + 6, j * 8 + 2); g8.AddBidirectionalEdge(i * 8 + 7, j * 8 + 3); } return g8; } public static Graph Product(Graph g1, Graph g2, bool strong=false) { var g = new Graph(g1.n * g2.n, g1.m * g2.m + g1.m + g2.m); var f = g2.n; for (int i = 0; i < g1.n; i++) { var iedges = g1[i]; for (int j = 0; j < g2.n; j++) { var jedges = g2[j]; foreach (var e1 in iedges) g[i * f + j].Add(e1 * f + j); foreach (var e2 in jedges) g[i * f + j].Add(i * f + e2); if (strong) { foreach (var e1 in iedges) foreach (var e2 in jedges) g[i * f + j].Add(e1 * f + e2); } } } // Preserves diameter // Order(g) = Order(g1) * Order(g2) // Weak // Degree(g) = Degree(g1)+Degree(g2) // Diameter(g) = Diameter(g1) + Diameter(g2) // Strong // if (strong) Degree(g) = Degree(g1)*Degree(g2) + Degree(g1) + Degree(g2) // Diameter(g) = Max(Diameter(g1), Diameter(g2)) // G(n/2,2) * C(2) -> G(n,5) // C(2) diameter=1 // G(n/3,2) * C(3) -> G(n/3,5) // C(2) diameter=2 // Question: Is C(3) degree 1 return g; } } #if DEBUG public static bool Verbose = true; #else public static bool Verbose = false; #endif } public class TimestampedArray<T> { public T[] Array; public int[] TimeStamp; public int Time; public T DefaultValue; public TimestampedArray(int size, T defaultValue = default(T)) { Array = new T[size]; TimeStamp = new int[size]; DefaultValue = defaultValue; } public T this[int x] { get { return TimeStamp[x] >= Time ? Array[x] : DefaultValue; } set { Array[x] = value; TimeStamp[x] = Time; } } public bool ContainsKey(int x) { return TimeStamp[x] >= Time; } public void InitializeAll() { for (int i = 0; i < Array.Length; i++) { if (TimeStamp[i] > Time) continue; Array[i] = DefaultValue; TimeStamp[i] = Time; } } public void Clear() { Time++; } } public static class HackerRankUtils { #region Reporting Answer static volatile bool _reported; static System.Threading.Timer _timer; static Func<bool> _timerAction; public static void LaunchTimer(Func<bool> action, long ms = 2800) { _timerAction = action; _timer = new System.Threading.Timer( delegate { Report(); #if !DEBUG if (_reported) Environment.Exit(0); #endif }, null, ms, 0); } public static void Report() { if (_reported) return; _reported = true; _reported = _timerAction(); } [Conditional("DEBUG")] public static void Trace(string s) { Console.WriteLine(s); } #endregion public static int TimeLimit = 2000; public static int RandomIterations = 20; public static int RandomIterationsTop = RandomIterations + 20; public static int Extra = 1; } Diameter Minimization Java Solution 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(); } } Diameter Minimization Python Solution #!/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) C# C++ HackerRank Solutions java python cppCSharpHackerrank Solutionsjavapython