CareerCup

The number of ways to select 2 robots such that both belong to separate models are:
pC2 * 2 * 2 + pC1 * 2 * (n-2p)C1 + (n-2p)C2

if n is total number of bots and p are distinct pairs.

I am not sure I understand the problem that well but hopefully this more general solution should cover some of the parts I don’t quite get.
If all Robots are unique choose one of the N and then chose one of the remaining N-1 robots
So you get n*(n-1) possible sets of 2
If there is a set of size M you could make up M*(M-1) pares with just the robots in this set.
So given N robots and an list of sets M[0]…. M[P] you have:
n*(n-1) - sum M[i]*(M[i] -1)

n1Cr1+n2Cr2 will give the answer.
Where n1 is total number of robots in set1, and r1 is the number robots to choose and n2 is total number of robots in set2, and r2 is the number robots to choose. And sum of both will give the required answer:-)

It should be 4* nC2, where n= number of pairs formed. In the example given n=3 (3 pairs...(4,2),(0,1),(2,3). There is a problem here though. If 4 and 2 are same type and 2,3 are same type then 4,2,3 are all same type. that should not be the case. Let's replace 2,3 with 5,3. Then the solution which I have proposed is correct.

/*
Name
Brief description of algorithm :
*/

#include <iostream>
#define MAXN 100000
#define MAXP 100000

using namespace std;

typedef unsigned long ulong;

ulong CountNoOfWays(ulong N, ulong P, ulong pairs[][2])
{
    ulong combi=0;
    ulong count=0,sum=0,x=0,count1=0;
    ulong check[N];

    for (int i=0;i<N;i++)
    {
        check[i]=0;
    }

    for (int i=0;i<P;i++)
    {

        if(check[pairs[i][0]]!=0||check[pairs[i][1]]!=0)
        {
            if(check[pairs[i][0]]!=0)
            {
                check[pairs[i][1]]=check[pairs[i][0]];
            }

            if(check[pairs[i][1]]!=0)
            {
                check[pairs[i][0]]=check[pairs[i][1]];
            }
        }

        if(check[pairs[i][0]]==0 && check[pairs[i][1]]==0)
        {
            count++;
            check[pairs[i][0]]=count;
            check[pairs[i][1]]=count;
        }

    }
/*
    for (int i=0;i<N;i++)
    {
        cout<<check[i]<<" ";
    }
    cout<<endl;
*/
    for (int i=0;i<N;i++)
    {
        if(check[i]>0)
        count1++;
    }

    ulong max=check[0];
    for (int i=1;i<N;i++)
    {
        if(max<check[i])
        max=check[i];
    }

    ulong headache[max+1];
    for (int i=0;i<=max;i++)
    {
        headache[i]=0;
    }

    for (int i=0;i<N;i++)
    {
        if(check[i]>0)
        headache[check[i]]++;
    }
/*
    for (int i=0;i<=max;i++)
    {
        cout<<headache[i]<<" ";
    }
    cout<<endl;
*/
    ulong result=1;
    for (int i=0;i<=max;i++)
    {
        if(headache[i]>0)
        result=result*headache[i];
    }
   // cout<<result<<endl;
    x=N-count1;
    sum=x*count1;
    sum=sum+(x*(x-1)/2);
    combi=combi+sum+result;
    return combi;
}

int main()
{
    ulong N, P;
    cin >> N >> P;
    ulong pairs[MAXP][2];

    for(ulong i = 0; i < P; i++)
    {
        cin >> pairs[i][0] >> pairs[i][1];
    }

    cout << CountNoOfWays(N, P, pairs);
}
/*
10 4
2 8
1 3
0 2
5 8
2,5,8,0 in one group
1,3 in another
(2,1)(2,3)(2,5)(8,1)(8,3)(8,0)(1,0)(1,5)(3,0)(3,5)(0,5)
1     2    3    4     5     6   7    8     9
*/

using System;
using System.Collections.Generic;

namespace Test
{
class Graph
{
int V; //Vertices of the graph

public int no_nodes = 0;

List<int>[] adj_node; //adjacent node fof each vertices

Graph(int V) // Constructor
{
this.V = V;

adj_node = new List<int>[V];

for (int i = 0; i < V; i++)
{
adj_node[i] = new List<int>();
}
}

void AddEdge(int x, int y)
{
adj_node[x].Add(y);
adj_node[y].Add(x);
}

void dfs(int a, bool[] vis)
{
vis[a] = true;
no_nodes++;
//Console.WriteLine(" " + a);
foreach (int x in adj_node[a])
{
if (!vis[x])
{
dfs(x, vis);
}

}
}

void Connection()
{
bool[] vis = new bool[V];

List<int> nodes = new List<int>();

for (int v = 0; v < V; v++)
{
if (!vis[v])
{
no_nodes = 0;
dfs(v, vis);
nodes.Add(no_nodes);
}

}



List<int> ans = new List<int>();
while(nodes.Count > 0)
{
int sum = 0;
for (int i = 1; i < nodes.Count; i++)
{
sum = sum + nodes[i];
}
ans.Add(nodes[0] * sum);
nodes.RemoveAt(0);
}
int res = 0;
foreach(int y in ans)
{
res = res + y;
}
Console.WriteLine(res);

}

public static void Main(String[] args)
{
Graph g = new Graph(4);

g.AddEdge(0, 1);
g.AddEdge(2, 3);

g.Connection();
Console.ReadLine();
}
}
}