o1-preview-2024-09-12· OpenAI
WildChat-4.8M (AI2)
Can you make this MUCH faster? The output is correct nut the code is to slow, dont add…
- User
Can you make this MUCH faster? The output is correct nut the code is to slow, dont add comments in code using System; using System.Buffers; using System.Runtime.CompilerServices;
public class TranslatorsDinner { public static void Main() { Span input = stackalloc int[2]; ParseInts(Console.ReadLine(), input); int N = input[0], M = input[1];
if ((M & 1) != 0) { Console.WriteLine("impossible"); return; } Span<int> translators = stackalloc int[M * 2]; Span<int> adjacencyList = stackalloc int[M * M]; Span<int> adjacencyCounts = stackalloc int[M]; for (int i = 0; i < M; i++) { ParseInts(Console.ReadLine(), translators.Slice(i * 2, 2)); } for (int i = 0; i < M; i++) { int lang1A = translators[i * 2], lang2A = translators[i * 2 + 1]; for (int j = i + 1; j < M; j++) { int lang1B = translators[j * 2], lang2B = translators[j * 2 + 1]; if (lang1A == lang1B || lang1A == lang2B || lang2A == lang1B || lang2A == lang2B) { adjacencyList[i * M + adjacencyCounts[i]++] = j; adjacencyList[j * M + adjacencyCounts[j]++] = i; } } } Span<bool> matched = stackalloc bool[M]; Span<int> pairs = stackalloc int[M]; int pairCount = 0; if (!MatchTranslators(0, matched, pairs, ref pairCount, adjacencyList, adjacencyCounts, M)) { Console.WriteLine("impossible"); return; } for (int i = 0; i < pairCount; i++) { Console.WriteLine($"{pairs[i * 2]} {pairs[i * 2 + 1]}"); } } [MethodImpl(MethodImplOptions.AggressiveInlining)] private static bool MatchTranslators(int current, Span<bool> matched, Span<int> pairs, ref int pairCount, Span<int> adjacencyList, Span<int> adjacencyCounts, int M) { while (current < M && matched[current]) { current++; } if (current >= M) { return pairCount == M / 2; } matched[current] = true; int start = current * M; for (int i = 0; i < adjacencyCounts[current]; i++) { int next = adjacencyList[start + i]; if (!matched[next]) { matched[next] = true; pairs[pairCount * 2] = current; pairs[pairCount * 2 + 1] = next; pairCount++; if (MatchTranslators(current + 1, matched, pairs, ref pairCount, adjacencyList, adjacencyCounts, M)) { return true; } pairCount--; matched[next] = false; } } matched[current] = false; return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] private static void ParseInts(string s, Span<int> result) { int index = 0, num = 0, resultIndex = 0; while (index < s.Length) { char c = s[index++]; if (c >= '0' && c <= '9') { num = num * 10 + (c - '0'); } else if (num > 0) { result[resultIndex++] = num; num = 0; } } if (num > 0) { result[resultIndex] = num; } }}
- Assistant
Yes, I can optimize your code significantly by implementing the Edmonds' Blossom algorithm for finding a maximum matching in general graphs. This will reduce the time complexity from exponential to polynomial time, making your program much faster. Here's the optimized code:
using System; using System.Collections.Generic; public class TranslatorsDinner { public static void Main() { var input = Console.ReadLine().Split(); int N = int.Parse(input[0]), M = int.Parse(input[1]); if ((M & 1) != 0) { Console.WriteLine("impossible"); return; } int[] lang1 = new int[M]; int[] lang2 = new int[M]; Dictionary<int, List<int>> langToTranslators = new Dictionary<int, List<int>>(); for (int i = 0; i < M; i++) { var nums = Console.ReadLine().Split(); lang1[i] = int.Parse(nums[0]); lang2[i] = int.Parse(nums[1]); if (!langToTranslators.ContainsKey(lang1[i])) langToTranslators[lang1[i]] = new List<int>(); if (!langToTranslators.ContainsKey(lang2[i])) langToTranslators[lang2[i]] = new List<int>(); langToTranslators[lang1[i]].Add(i); langToTranslators[lang2[i]].Add(i); } List<int>[] graph = new List<int>[M]; for (int i = 0; i < M; i++) graph[i] = new List<int>(); for (int i = 0; i < M; i++) { foreach (int j in langToTranslators[lang1[i]]) { if (i != j) graph[i].Add(j); } foreach (int j in langToTranslators[lang2[i]]) { if (i != j && !graph[i].Contains(j)) graph[i].Add(j); } } int[] match = new int[M]; for (int i = 0; i < M; i++) match[i] = -1; if (!BlossomAlgorithm(M, graph, match)) { Console.WriteLine("impossible"); return; } for (int i = 0; i < M; i++) { if (i < match[i]) Console.WriteLine($"{i} {match[i]}"); } } static bool BlossomAlgorithm(int n, List<int>[] graph, int[] match) { int[] baseArray = new int[n]; int[] parent = new int[n]; int[] label = new int[n]; int[] queue = new int[n]; int[] inBlossom = new int[n]; bool[] inQueue = new bool[n]; int[] blossomParent = new int[n]; int[] blossomChildren = new int[n]; int[] blossomEndps = new int[n]; while (true) { Queue<int> q = new Queue<int>(); for (int i = 0; i < n; i++) { parent[i] = -1; baseArray[i] = i; label[i] = 0; inQueue[i] = false; } for (int i = 0; i < n; i++) { if (match[i] == -1) { q.Enqueue(i); label[i] = 1; inQueue[i] = true; } } int augmentingPathFound = -1; while (q.Count > 0) { int v = q.Dequeue(); foreach (int u in graph[v]) { if (baseArray[v] == baseArray[u] || match[v] == u) continue; if (label[u] == 0) { label[u] = 2; parent[u] = v; if (match[u] == -1) { augmentingPathFound = u; break; } label[match[u]] = 1; q.Enqueue(match[u]); } else if (label[u] == 1) { int basePoint = LCA(baseArray, parent, v, u); bool[] blossom = new bool[n]; MarkBlossom(baseArray, parent, label, blossom, v, u, basePoint, inQueue, q); MarkBlossom(baseArray, parent, label, blossom, u, v, basePoint, inQueue, q); } } if (augmentingPathFound != -1) break; } if (augmentingPathFound == -1) break; int v = augmentingPathFound; while (v != -1) { int pv = parent[v]; int ppv = match[pv]; match[v] = pv; match[pv] = v; v = ppv; } } for (int i = 0; i < n; i++) if (match[i] == -1) return false; return true; } static int LCA(int[] baseArray, int[] parent, int a, int b) { bool[] visited = new bool[baseArray.Length]; while (true) { a = baseArray[a]; visited[a] = true; if (match[a] == -1) break; a = parent[match[a]]; } while (true) { b = baseArray[b]; if (visited[b]) return b; if (match[b] == -1) break; b = parent[match[b]]; } return -1; } static void MarkBlossom(int[] baseArray, int[] parent, int[] label, bool[] blossom, int v, int w, int basePoint, bool[] inQueue, Queue<int> q) { while (baseArray[v] != basePoint) { blossom[baseArray[v]] = blossom[baseArray[match[v]]] = true; parent[v] = w; if (!inQueue[match[v]]) { q.Enqueue(match[v]); inQueue[match[v]] = true; } w = match[v]; v = parent[w]; } } }