Skip to content
TheChatArchiveThe Chat Archive
o1-preview-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

Can you make this MUCH faster? The output is correct nut the code is to slow, dont add…

  1. 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;
        }
    }
    

    }

  2. 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];
            }
        }
    }