5
\$\begingroup\$

Problem statement

You're researching friendships between groups \$n\$ of new college students where each student is distinctly numbered from \$1\$ to \$n\$. At the beginning of the semester, no student knew any other student; instead, they met and formed individual friendships as the semester went on. The friendships between students are:

  • Bidirectional

    If student \$a\$ is friends with student \$b\$, then student \$b\$ is also friends with student \$a\$.

  • Transitive

    If student \$a\$ is friends with student \$b\$ and student \$b\$ is friends with student \$c\$ , then student \$a\$ is friends with student \$c\$. In other words, two students are considered to be friends even if they are only indirectly linked through a network of mutual (i.e., directly connected) friends. The purpose of your research is to find the maximum total value of a group's friendships, denoted by \$total\$. Each time a direct friendship forms between two students, you sum the number of friends that each of the \$n\$ students has and add the sum to \$total\$.

You are given \$q\$ queries, where each query is in the form of an unordered list of \$m\$ distinct direct friendships between \$n\$ students. For each query, find the maximum value of \$total\$ among all possible orderings of formed friendships and print it on a new line.

Input Format

The first line contains an integer, \$q\$, denoting the number of queries. The subsequent lines describe each query in the following format:

The first line contains two space-separated integers describing the respective values of \$n\$ (the number of students) and \$m\$ (the number of distinct direct friendships). Each of the \$m\$ subsequent lines contains two space-separated integers describing the respective values of \$x\$ and \$y\$ (where \$x<>y\$) describing a friendship between student \$x\$ and student \$y\$.

Constraints

1. 1 <= q <= 16

2. 1 <= n <= 100000

3. 1 <= m <= min(n(n-1)/2, 200000)

  1. Output Format

For each query, print the maximum value of \$total\$ on a new line.

Sample Input 0

1

5 4

1 2

3 2

4 2

4 3

Sample Output 0

32

Explanation 0

The value of \$total\$ is maximal if the students form the m = 4 direct friendships in the following order:

enter image description here

  1. Students \$1\$ and \$2\$ become friends:

    enter image description here

We then sum the number of friends that each student has to get 1 + 1 + 0 + 0 + 0 = 2.

  1. Students \$2\$ and \$4\$ become friends:

    enter image description here

We then sum the number of friends that each student has to get 2 + 2 + 0 + 2 + 0 = 6.

  1. Students 3 and 4 become friends:

    enter image description here

We then sum the number of friends that each student has to get 3 + 3 + 3 + 3 + 0 = 12.

  1. Students 3 and 2 become friends:

    enter image description here

We then sum the number of friends that each student has to get 3 + 3 + 3 + 3 + 0 = 12.

When we add the sums from each step, we get total = 2 + 6 + 12 + 12 = 32. We then print 32 on a new line.

My introduction of algorithm

The algorithm is the hard one and also one of Hackerrank weekcode \$28\$ contest in January 2017, I spent a few hours in the contest to read the problem statement and also read all the discussion. I did some study on disjoint set, but I did not come out clear ideas how to divide groups, implement a graph. I learned through the discussion that the friendship should be added to maximize the value, and studied the test case in the following (5 nodes in the graph):

enter image description here

 1. student 1 and 2 become friends

   1-2 3 4 5,  we then sum the number of friends that each student has
  to get 1 + 1 + 0 + 0 + 0 = 2. 

 2. Student 2 and 3 become friends:

   1-2-3 4 5, we then sum the number of friends that each student has to get
  2 + 2 + 2 + 0 + 0 = 6. 

  3. Student 4 and 5 become friends:

  1-2-3 4-5, we then sum the number of friends that each student has to get 
  2 + 2 + 2 + 1 + 1 = 8. 

  4. Student 1 and 3 become friends: (we hold to add 1 and 3 until 4 and 5 are added to maximize the value.)

  1-2-3 4-5, we then sum the number of friends that each student has to get
  2 + 2 + 2 + 1 + 1 = 8. 

  Total is 2 + 6 + 8 + 8 = 24. 

If the friendship \$1\$ and \$3\$ are added before adding 4 and 5, then the value is less than \$24\$.

After the contest, I studied one of C# submission with maximum score, and then did some code review, tried to understand the graph design and also read the hackerrank editorial notes, understood the process to get maximum value of friendship. I put together C# code and also tested on hackerrank, the code passed all test cases. Please help me to review my C# code.

Hightlights of changes

Add name variable in the class GraphNode to help identify node; add the test case to help understand the algorithm, and be able to add comment to explain the function Connect; use meaningful variable names after code review. I already spent hours on the algorithm and really look forward to work hard on graph algorithm and be able to perform one graph algorithm in week of code contest in short future.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;

class Solution
{

  public class Group
  {
    public int totalNumberNodes = 1;
  }

  /*
  * GraphNode class
  */
  public class GraphNode
  {
    /* Julia added the variable: name, so she can track GraphNode and 
     * work on the test case with 5 nodes: 0, 1, 2, 3, 4
     */
    public string name; 

    // variables are defined by original author, study code from 
    // one of submissions with maximum score
    public Group group;
    public List<Edge> edges = new List<Edge>();

    public GraphNode(string s)
    {
        this.name = s; 
    }

    /*
     * Work on the test case, illustrate the process using specific examples. 
     * 
     * Use name to track with edge, which node in the test case: 
     * 1-2-3 4-5
     * 5 nodes in the graph, 4 connections, 1-3 is redundant. 
     * 
     * Go over each edge, and then remove friend node from nodes 
     * HashSet, edge from edges HashSet, and share the group to 
     * friend node, add one more to variable n, push friendNode 
     * to the stack. 
     */
    public void Connect(
     HashSet<GraphNode> nodes, 
     HashSet<Edge> edges, 
     Stack<GraphNode> neighbours)
    {
        foreach (var edge in this.edges)
        {
            var friendNode = (edge.id_1 != this) ? edge.id_1 : edge.id_2;

            if (friendNode.group == null)
            {
                nodes.Remove(friendNode);
                edges.Remove(edge);

                friendNode.group = group;
                group.totalNumberNodes++;        
                neighbours.Push(friendNode);   
            }
        }
    }
}

public class Edge
{
    public GraphNode id_1;
    public GraphNode id_2;
}

static void Main(string[] args)
{
    ProcessInput();
    //RunSampleTestcase(); 
}

/*
 * Need to work on the sample test case
 * 1. student 1 and 2 become friends
 *  1-2 3 4 5,  we then sum the number of friends that each student has
 * to get 1 + 1 + 0 + 0 + 0 = 2. 
 * 2. Student 2 and 3 become friends:
 *  1-2-3 4 5, we then sum the number of friends that each student has to get
 * 2 + 2 + 2 + 0 + 0 = 6. 
 * 3. Student 4 and 5 become friends:
 * 1-2-3 4-5, we then sum the number of friends that each student has to get 
 * 2 + 2 + 2 + 1 + 1 = 8. 
 * 4. Student 1 and 3 become friends: (we hold to add 1 and 3 until 4 and 5
 *    are added to maximize the value.)
 * 1-2-3 4-5, we then sum the number of friends that each student has to get
 * 2 + 2 + 2 + 1 + 1 = 8. 
 * Total is 2 + 6 + 8 + 8 = 24. 
 */
public static void RunSampleTestcase()
{
    int queries = 1; 
    string[][] datas = new string[1][]; 
    datas[0] = new string[2]; 
    datas[0][0] = "5"; 
    datas[0][1] = "4"; 

    string[][] allFriendships = new string[1][]; 
    allFriendships[0] = new string[4];

    allFriendships[0][0] = "1 2";
    allFriendships[0][1] = "2 3";
    allFriendships[0][2] = "1 3";
    allFriendships[0][3] = "4 5"; 

    IList<long> result = MaximizeValues( queries,   datas,  allFriendships);
    Debug.Assert(result[0] == 24); 
}

/*
 * code review:
 * Everything is in one function, should break down a few of pieces
 * 1. Input
 * 2. Set up multiple graphes
 * 3. minimum edges to connect the graph
 * 4. extra edges to hold for maximum output, added by descending order. 
 * 4. Output
 */
public static void ProcessInput()
{
    int queries = Convert.ToInt32(Console.ReadLine());
    string[][] graphData = new string[queries][];
    string[][] allFriendships = new string[queries][];        

    for (int query = 0; query < queries; query++)
    {
        string[] data = Console.ReadLine().Split(' ');
        int totalNodes  = Convert.ToInt32(data[0]);
        int friendships = Convert.ToInt32(data[1]);

        graphData[query] = new string[] { totalNodes.ToString(), friendships.ToString() };

        allFriendships[query] = new string[friendships]; 

        for (int i = 0; i < friendships; i++)
        {                
            allFriendships[query][i] = Console.ReadLine();                               
        }
    } // end of process input

    IList<long> result = MaximizeValues(queries, graphData, allFriendships); 
    foreach(long value in result)
    {
        Console.WriteLine(value); 
    }
}

/*
 * Maximum value to add the friendship 
 * 3 rules to follow - check editorial notes:
 *    The graph is comprised of several components. 
 *    Each component has its own size. 
 *   1. At first if a component has S nodes, you just need to add S - 1 
 *   edges to make the component connected (a subtree of the component), 
 *   add the rest of the edges at the end when all the components 
 *   are connected in themselves. 
 *   2. At the end, when all of the components are connected, add 
 *   the extra edges. 
 *   3. But what about the order of the components? Its better to 
 *      add larger components first
 *      so that larger numbers are repeated more. 
 *   4. What about a component in itself? Try to make a tree from that component. 
*/
public static IList<long> MaximizeValues(
int queries, 
string[][] datas, 
string[][] allFriendships)
{
    IList<long> output = new List<long>(); 

    for (int query = 0; query < queries; query++)
    {
        string[] data = datas[query];
        int totalNodes = Convert.ToInt32(data[0]);
        int friendships = Convert.ToInt32(data[1]);

        var map = new GraphNode[totalNodes];
        var nodes = new HashSet<GraphNode>();

        for (int node = 0; node < totalNodes; node++)
        {
            map[node] = new GraphNode(node.ToString());
            nodes.Add(map[node]);
        }

        var edges = new HashSet<Edge>();

        var friendship = allFriendships[query];

        for (int i = 0; i < friendships; i++)
        {
            string[] relationship = friendship[i].Split(' '); 

            var edge = new Edge();

            edge.id_1 = map[Convert.ToInt32(relationship[0]) - 1];
            edge.id_2 = map[Convert.ToInt32(relationship[1]) - 1];

            edges.Add(edge);

            edge.id_1.edges.Add(edge);
            edge.id_2.edges.Add(edge);
        }
        // end of process input 

        var groups = new List<Group>();

        // use stack - how to understand the stack's functionality here? 
        // write down something here - go over a test case to understand 
        // the code
        while (nodes.Count > 0)
        {
            var node = nodes.First();
            nodes.Remove(node);

            groups.Add(node.group = new Group());

            var neighbours = new Stack<GraphNode>();
            node.Connect(nodes, edges, neighbours);

            while (neighbours.Count > 0)
            {
                GraphNode current = neighbours.Pop();
                current.Connect(nodes, edges, neighbours);
            }
        }

        long result = 0;
        long sum = 0;

        foreach (var edge in groups.OrderByDescending(g => g.totalNumberNodes))
        {
            for (int i = 1; i < edge.totalNumberNodes; i++)
            {
                result += (i + 1) * (long)i + sum;
            }

            sum += (long)edge.totalNumberNodes * (edge.totalNumberNodes - 1);
        }

        output.Add(result + edges.Count * sum);
    }

    return output; 
  }
}
\$\endgroup\$
4
\$\begingroup\$
  • code review:
  • Everything is in one function, should break down a few of pieces

Good idea. Why don't you actually implement it? It makes sense. The same can be done to MaximizeValues method. Right now it does at least three distinct things:

  • it converts string values to numbers for every test case
  • it builds graph for every test case
  • it solves the problem for every test case

Those should be three different methods.


You can further simplify MaximizeValues method if you change its signature to:

public static long MaximizeValues(string[] datas, string[] allFriendships)

and call it once for every query instead.


Your code does not follow C# naming conventions. Public fields and properties should use PascalCase. Also the names themselves could be better. What is id_1? How is it different from id_2? Hard to tell.


Your algorithm is pretty hard to follow, at least for me (I am no expert in graph theory). If you add some local variables with descriptive names - that might help. For example, instead of writing:

result += (i + 1) * (long)i + sum;

you could write:

var explainWhatThatIs = (i + 1) * (long)i + sum;
result += explainWhatThatIs;
\$\endgroup\$
  • \$\begingroup\$ I did not write the code as the first author, I had to set up a test case and then understand the algorithm first. It took hours to go over the algorithm with a test case. I also thought about GraphNode class Connect function name is not accurate, should call ShareGroup. \$\endgroup\$ – Jianmin Chen Jan 18 '17 at 6:55
  • \$\begingroup\$ I learned from C# Tuple class item1, item2, so I name the Edge class two variable same style, should be Id1, Id2, PascalCase, _ is not needed. \$\endgroup\$ – Jianmin Chen Jan 18 '17 at 7:01
  • \$\begingroup\$ I had hard time to design the algorithm as the code does, put together a graph, and then, go over the set of all nodes to set up components in the graph using depth first search (DFS). Each time the set of all nodes will be updated to remove visited node. The graph algorithm discussion will be helpful, but I think that the code review will take more time if getting into algorithm design. \$\endgroup\$ – Jianmin Chen Jan 18 '17 at 7:13
  • \$\begingroup\$ I have a question about function MaximizeValues, because comments are added to help user understand the tasks to be completed, do that make an exception when you write a function to compromise single responsibility principle (SRP), called a pragmatic approach? \$\endgroup\$ – Jianmin Chen Jan 18 '17 at 7:20
  • 2
    \$\begingroup\$ @JianminChen, those two things are not mutually-exclusive. You can do both: follow SRP and write comments and/or XML-documentation. However, if you find yourself using comments (or #region statement) to break down long method into smaller blocks, that's usually a good indication that SRP was violated and you should refactor this long method into multiple smaller methods. \$\endgroup\$ – Nikita B Jan 18 '17 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.