 # Uberhack tag Game of thrones solution

Can anybody check my solution for the Uberhack tag contest?

QUESTION:

In the world of game of thrones power is everything. Given a network of friends in the world of game of thrones who have different interests, you’d like to know the power of the couple who have the most common interests.

You are given integers friends_nodes and friends_edges, representing the number of nodes and edges in the network respectively. You are also given three arrays of integers, friends_from, friends_to, and friends_interest, which describe the edges between friends. The ith edge in the input is represented by its vertices - friends_from[i] and friends_to[i] and the interest these two vertices have in common - friends_interest[i].

The graph consists of nodes numbered consecutively from 1 to friends_nodes. Any two friends a and b that are connected by an edge with some interest are said to be in the same interest group. Then, for each interest, we have an interest group. Note that two members can be in an interest group even if they are not directly connected by the corresponding edge. For example, if friends 1 and 2 are connected by an edge with interest 5, as well as friends 2 and 3, all three friends are in an interest group, even though friends 1 and 3 don’t have a corresponding edge with interest 5 connecting them.

Each pair of friends in the found set are said to have a shared interest. For example, in the example above all pairs (1, 2), (1, 3), and (2, 3) will have a shared interest 5. Power is defined as the product of node pairs’ labels.

Your next step is to determine the power couple with the maximum number of shared interests. If there are multiple pairs with the maximum number of shared interests, return the maximum product among them.

EXAMPLE 1:

You are given a graph with friends_nodes = 4 and friends_edges = 5:
Each pair among the 4 friends is connected by the following interests:

Pair (1, 2) shares 2 interests (interests 1 and 2)
Pair (1, 3) shares 1 interest (interest 1)
Pair (1, 4) shares 0 interests
Pair (2, 3) shares 2 interests (interests 1 and 3)
Pair (2, 4) shares 1 interest (interest 3)
Pair (3, 4) shares 1 interest (interest 3). Note that even though these two friends are not directly connected by an edge, they still share a common interest.
The pairs with the maximal number of shared interests are (1, 2) and (2, 3). Their respective products are 1 × 2 = 2 and 2 × 3 = 6. We then return the largest of these values as our answer, which is 6.

EXAMPLE 2 :

For friends_nodes = 4, friends_edges = 4, friends_from = [1, 1, 2, 2], friends_to = [3, 3, 4, 4], and friends_weight = [1, 2, 1, 2], the output should be sharedInterests(friends_nodes, friends_edges, friends_from, friends_to, friends_weight) = 12.

SOLUTION:

``````int getPowerCouple2021(int fn, int fe, vector<int> ff, vector<int> ft, vector<int> fw) {
long long int i,j,k,l;
vector<int> vec[fn];
for(i=0;i<fe;i++)
{
vec[ff[i]-1].push_back(fw[i]);
}
for(i=0;i<fe;i++)
{
vec[ft[i]-1].push_back(fw[i]);
}
for(i=0;i<fn;i++)
{
sort(vec[i].begin(),vec[i].end());
std::unordered_set<int> s(vec[i].begin(), vec[i].end());
vec[i].assign(s.begin(), s.end());
}
int s[fn][fn];
memset(s,0,sizeof(s));
for(i=0;i<fn-1;i++)
{
for(j=i+1;j<fn;j++)
{
for(k=0;k<vec[i].size();k++)
{
for(l=0;l<vec[j].size();l++)
{
if(vec[i][k]==vec[j][l])
{
s[i][j]++;
}
}
}
}
}
long long int hel=0,ans=-1;
for(i=0;i<fn;i++)
{
for(j=0;j<fn;j++)
{
if(hel<=s[i][j])
{
ans=max(ans,(i+1)*(j+1));
hel=s[i][j];
}
}
}
return ans;
``````

}

1 Like

Which language is this?