Table of Contents
Tripartite Matching – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Tripartite Matching HackerRank Solution
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cstdio>
#include<numeric>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<list>
#include<cmath>
#include<bitset>
#include<cassert>
#include<queue>
#include<stack>
#include<deque>
#include<cassert>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = 100 * 1000 + 1;
typedef bitset<MAXN> bs;
int deg1[MAXN], deg2[MAXN];
vector<int>g1[MAXN], g2[MAXN];
unordered_set<long long>have1, have2;
int calc(int u, int v) // u - first, v - third
{
int res = 0;
if (deg1[u] < deg2[v])
{
for (int i = 0; i < (int)g1[u].size(); i++)
{
int to = g1[u][i];
if (to == v) continue;
res += have2.count(1LL * MAXN * v + to);
}
}
else
{
for (int i = 0; i < (int)g2[v].size(); i++)
{
int to = g2[v][i];
if (to == v) continue;
res += have1.count(1LL * MAXN * u + to);
}
}
return res;
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int n;
scanf("%d", &n);
int m;
scanf("%d", &m);
have1.rehash(10 * 1000 * 1000);
have2.rehash(10 * 1000 * 1000);
for (int i = 1; i <= m; i++)
{
int u, v;
scanf("%d %d", &u, &v);
g1[u].push_back(v);
have1.insert(1LL * MAXN * u + v);
have1.insert(1LL * MAXN * v + u);
g1[v].push_back(u);
deg1[u]++;
deg1[v]++;
}
vector<pair<int, int> >mid;
scanf("%d", &m);
for (int i = 1; i <= m; i++)
{
int u, v;
scanf("%d %d", &u, &v);
mid.push_back(make_pair(u, v));
}
scanf("%d", &m);
for (int i = 1; i <= m; i++)
{
int u, v;
scanf("%d %d", &u, &v);
deg2[u]++;
deg2[v]++;
g2[u].push_back(v);
g2[v].push_back(u);
have2.insert(1LL * MAXN * u + v);
have2.insert(1LL * MAXN * v + u);
}
ll ans = 0;
for (int i = 0; i < (int)mid.size(); i++)
{
int u = mid[i].first, v = mid[i].second;
ans += calc(u, v);
ans += calc(v, u);
}
printf("%lld\n", ans);
}
Java Tripartite Matching HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class D {
InputStream is;
PrintWriter out;
String INPUT = "";
int[][] read(int n)
{
int m = ni();
int[] from = new int[m];
int[] to = new int[m];
for(int i = 0;i < m;i++){
from[i] = ni()-1;
to[i] = ni()-1;
}
return packU(n, from, to);
}
void solve()
{
int n = ni();
int[][] ga = read(n);
int[][] gb = read(n);
int[][] gc = read(n);
int S = (int)Math.sqrt(100000);
long[][] gbb = new long[n][];
long[][] gbc = new long[n][];
for(int i = 0;i < n;i++){
if(gb[i].length >= S){
gbb[i] = new long[(n>>>6)+1];
for(int e : gb[i]){
gbb[i][e>>>6] |= 1L<<e;
}
}
if(gc[i].length >= S){
gbc[i] = new long[(n>>>6)+1];
for(int e : gc[i]){
gbc[i][e>>>6] |= 1L<<e;
}
}
Arrays.sort(gb[i]);
Arrays.sort(gc[i]);
}
int na = ga.length;
long ret = 0;
for(int a = 0;a < na;a++){
for(int b : ga[a]){
if(gbb[b] != null){
if(gbc[a] != null){
for(int i = 0;i < (n>>>6)+1;i++){
ret += Long.bitCount(gbb[b][i]&gbc[a][i]);
}
}else{
for(int e : gc[a]){
if(gbb[b][e>>>6]<<~e<0)ret++;
}
}
}else{
if(gbc[a] != null){
for(int e : gb[b]){
if(gbc[a][e>>>6]<<~e<0)ret++;
}
}else{
for(int i = 0, j = 0;i < gb[b].length && j < gc[a].length;){
if(gb[b][i] == gc[a][j]){
ret++; i++; j++;
}else if(gb[b][i] < gc[a][j]){
i++;
}else{
j++;
}
}
}
}
}
}
out.println(ret);
}
static int[][] packU(int n, int[] from, int[] to) {
int[][] g = new int[n][];
int[] p = new int[n];
for (int f : from)
p[f]++;
for (int t : to)
p[t]++;
for (int i = 0; i < n; i++)
g[i] = new int[p[i]];
for (int i = 0; i < from.length; i++) {
g[from[i]][--p[from[i]]] = to[i];
g[to[i]][--p[to[i]]] = from[i];
}
return g;
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new D().run(); }
private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
Python 3 Tripartite Matching HackerRank Solution
vertices = int(input())
graph = [[], [], [], []]
count = 0
G1 = 1
G2 = 2
G3 = 3
for i in range(1, 4):
for j in range(0, vertices + 1):
graph[i].append(None)
for i in range(1, 4):
edges = int(input())
for j in range(0, edges):
edge = list(map(int, input().split(" ")))
if graph[i][edge[0]] is None:
graph[i][edge[0]] = set()
graph[i][edge[0]].add(edge[1])
if graph[i][edge[1]] is None:
graph[i][edge[1]] = set()
graph[i][edge[1]].add(edge[0])
for vertex in range(1, vertices + 1):
verticesToG1 = graph[G1][vertex]
if verticesToG1 is not None:
verticesFromG2 = graph[G2][vertex]
if verticesFromG2 is not None:
for toVertex in verticesFromG2:
verticesFromG3 = graph[G3][toVertex]
if verticesFromG3 is not None:
count = count + len(verticesToG1.intersection(verticesFromG3))
print(count)
Python 2 Tripartite Matching HackerRank Solution
#!/usr/bin/env python
import sys
def main():
N = int(sys.stdin.readline())
M = []
G = []
for i in xrange(3):
M.append(int(sys.stdin.readline()))
G.append([set() for _ in xrange(N)])
for _ in xrange(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 xrange(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()
C Tripartite Matching HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
#define HASH_SIZE 1234555
typedef struct _node{
int x;
int y;
struct _node *next;
} node;
typedef struct _lnode{
int x;
struct _lnode *next;
} lnode;
void insert_edge(int x,int y,int *len,lnode **table,node **hash);
void insert(node **hash,int x,int y);
int search(node **hash,int x,int y);
int len1[100000],len2[100000],*t1[100000],*t2[100000];
node *hash1[HASH_SIZE],*hash2[HASH_SIZE];
lnode *table1[100000],*table2[100000];
int main(){
int n,m,x,y,i,j;
long long ans=0;
lnode *p;
scanf("%d",&n);
scanf("%d",&m);
for(i=0;i<m;i++){
scanf("%d%d",&x,&y);
insert_edge(x-1,y-1,len1,table1,hash1);
}
scanf("%d",&m);
for(i=0;i<m;i++){
scanf("%d%d",&x,&y);
insert_edge(x-1,y-1,len2,table2,hash2);
}
for(i=0;i<n;i++)
if(len1[i]){
t1[i]=(int*)malloc(len1[i]*sizeof(int));
for(p=table1[i],j=0;p;p=p->next,j++)
t1[i][j]=p->x;
}
for(i=0;i<n;i++)
if(len2[i]){
t2[i]=(int*)malloc(len2[i]*sizeof(int));
for(p=table2[i],j=0;p;p=p->next,j++)
t2[i][j]=p->x;
}
scanf("%d",&m);
for(i=0;i<m;i++){
scanf("%d%d",&x,&y);
x--;
y--;
if(len1[x]<len2[y])
for(j=0;j<len1[x];j++)
ans+=search(hash2,t1[x][j],y);
else
for(j=0;j<len2[y];j++)
ans+=search(hash1,t2[y][j],x);
if(len1[y]<len2[x])
for(j=0;j<len1[y];j++)
ans+=search(hash2,t1[y][j],x);
else
for(j=0;j<len2[x];j++)
ans+=search(hash1,t2[x][j],y);
}
printf("%lld",ans);
return 0;
}
void insert_edge(int x,int y,int *len,lnode **table,node **hash){
lnode *t=malloc(sizeof(lnode));
t->x=y;
t->next=table[x];
table[x]=t;
len[x]++;
t=malloc(sizeof(lnode));
t->x=x;
t->next=table[y];
table[y]=t;
len[y]++;
insert(hash,x,y);
insert(hash,y,x);
return;
}
void insert(node **hash,int x,int y){
int bucket=(x*100000LL+y)%HASH_SIZE;
node *t=hash[bucket];
t=(node*)malloc(sizeof(node));
t->x=x;
t->y=y;
t->next=hash[bucket];
hash[bucket]=t;
return;
}
int search(node **hash,int x,int y){
int bucket=(x*100000LL+y)%HASH_SIZE;
node *t=hash[bucket];
while(t){
if(t->x==x && t->y==y)
return 1;
t=t->next;
}
return 0;
}
Leave a comment below
