Discussion on Tripartite Matching Challenge

Sort 10 Discussions, By:

4 years ago+ 0 comments

In the task description it is written that:

the graphs are unweighted and undirected
"Each graph contains no cycles and any pair of directly connected nodes is connected by a maximum of edge."

But in the sample input the second graph is the following:

Which contains a cycle. What am I misunderstanding? I would really appriciate some help.

1 year ago+ 0 comments

import sys

def main():
    N = int(sys.stdin.readline())
    M = []
    G = []
    for i in range(3):
        M.append(int(sys.stdin.readline()))
        G.append([set() for _ in range(N)])
        for _ in range(M[i]):
            u, v = map(int, sys.stdin.readline().split())
            u, v = u - 1, v - 1
            G[i][u].add(v)
            G[i][v].add(u)
    cpt = 0
    for a in range(N):
        for b in G[0][a]:
            for c in G[1][b]:
                if a in G[2][c]:
                    #print a,b,c
                    cpt += 1
    print(cpt)

main()

2 years ago+ 0 comments

Its impossible to complete in c# without modfying the process of reading data from console (one must modify Main method)

5 years ago+ 0 comments

Are there not 6 possible triples on the sample input?

5 years ago+ 0 comments

Just a very unelegant approach ,the first two graphs are lists so that I can go through them in a for loop which is faster than a for each and the third is a hashset because I need a O(1) contains. Only one testcase times out.The others pass.

using System;
using System.Collections.Generic;

class Triparte_Matching
{
    static int n;
    static List<int>[] firstGraph, secondGraph;
    static HashSet<int>[] thirdGraph;

    static void Main(string[] args)
    {
        ReadInput();
        Console.WriteLine(Solve());
    }

    private static int Solve()
    {
        var res = 0;

        for (int i = 0; i < firstGraph.Length; i++)
        {
            if (firstGraph[i] == null)
            {
                continue;
            }

            for (int j = 0; j < firstGraph[i].Count; j++)
            {
                var num = firstGraph[i][j];
                if (secondGraph[num] == null || num == i)
                {
                    continue;
                }

                for (int p = 0; p < secondGraph[num].Count; p++)
                {
                    var secondNum = secondGraph[num][p];
                    if (num != i && secondNum != i && thirdGraph[secondNum] != null && thirdGraph[secondNum].Contains(i))
                    {
                        res++;
                    }
                }
            }
        }

        return res;
    }

    private static void ReadInput()
    {
        n = int.Parse(Console.ReadLine());
        firstGraph = new List<int>[n + 1];
        secondGraph = new List<int>[n + 1];
        thirdGraph = new HashSet<int>[n + 1];

        var m = int.Parse(Console.ReadLine());
        string[] args;

        for (int i = 0; i < m; i++)
        {
            args = Console.ReadLine().Split(' ');
            var start = int.Parse(args[0]);
            var end = int.Parse(args[1]);
            if (firstGraph[start] == null)
            {
                firstGraph[start] = new List<int>();
            }
            if (firstGraph[end] == null)
            {
                firstGraph[end] = new List<int>();
            }
            firstGraph[start].Add(end);
            firstGraph[end].Add(start);
        }

        m = int.Parse(Console.ReadLine());
        for (int i = 0; i < m; i++)
        {
            args = Console.ReadLine().Split(' ');
            var start = int.Parse(args[0]);
            var end = int.Parse(args[1]);
            if (secondGraph[start] == null)
            {
                secondGraph[start] = new List<int>();
            }
            if (secondGraph[end] == null)
            {
                secondGraph[end] = new List<int>();
            }
            secondGraph[start].Add(end);
            secondGraph[end].Add(start);
        }

        m = int.Parse(Console.ReadLine());
        for (int i = 0; i < m; i++)
        {
            args = Console.ReadLine().Split(' ');
            var start = int.Parse(args[0]);
            var end = int.Parse(args[1]);
            if (thirdGraph[start] == null)
            {
                thirdGraph[start] = new HashSet<int>();
            }
            if (thirdGraph[end] == null)
            {
                thirdGraph[end] = new HashSet<int>();
            }
            thirdGraph[start].Add(end);
            thirdGraph[end].Add(start);
        }
    }
}

Load more conversations