Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections.Generic;
- using System.IO;
- using System.Linq;
- class Solution
- {
- /*
- * January 19, 2016
- */
- public struct Group
- {
- public int Links;
- public Stack<int> Nodes;
- /*
- * Small group will join the bigger group.
- */
- public static void MergeSmallGroupToLargeOne(
- Group[] groups,
- int smallGroupId,
- int bigGroupId,
- int[] nodeGroupId)
- {
- groups[bigGroupId].Links += groups[smallGroupId].Links + 1;
- Stack<int> destination = groups[bigGroupId].Nodes;
- Stack<int> source = groups[smallGroupId].Nodes;
- while (source.Count > 0)
- {
- int node = source.Pop();
- nodeGroupId[node] = bigGroupId;
- destination.Push(node);
- }
- }
- /*
- * Go over the calculation formula
- *
- */
- public static ulong CalculateValue(Group[] sortedGroups)
- {
- ulong additionalLinks = 0;
- ulong totalValueOfFriendship = 0;
- ulong totalFriends = 0;
- // Each group is maximized in order... additionalLinks added at end
- foreach (Group group in sortedGroups)
- {
- ulong links = (ulong)(group.Nodes.Count - 1);
- ulong lookupValue = FriendshipValueCalculation.GetLookupTable()[links];
- totalValueOfFriendship += lookupValue + totalFriends * links;
- additionalLinks += (ulong)group.Links - links;
- totalFriends += links * (links + 1);
- }
- totalValueOfFriendship += additionalLinks * totalFriends;
- return totalValueOfFriendship;
- }
- /*
- * filter out empty group, check Group class member
- * @groupCount - total groups, excluding merged groups
- * @groupIndex - total groups, including merged groups
- *
- * check Nodes in the stack, if the stack is empty, then the group is empty.
- */
- public static Group[] GetNonemptyGroups(int groupCount, int groupIndex, Group[] groups)
- {
- Group[] nonEmptyGroups = new Group[groupCount];
- int index = 0;
- for (int i = 1; i <= groupIndex; i++)
- {
- if (groups[i].Nodes.Count > 0)
- {
- nonEmptyGroups[index++] = groups[i];
- }
- }
- return nonEmptyGroups;
- }
- }
- /*
- * Design talk:
- * 1 <= n <= 100,000, n is the total students
- * 1 <= m <= 2 * 100,000, m is the total friendship
- * @groups -
- * @groupIdMap -
- */
- public class GroupManagement
- {
- public Group[] groups;
- public int[] groupIdMap;
- public int groupIndex = 0;
- public int groupCount = 0;
- public GroupManagement(int totalStudents)
- {
- groups = new Group[totalStudents / 2 + 1]; //
- groupIdMap = new int[totalStudents + 1]; // less than 2MB
- groupIndex = 0;
- groupCount = 0;
- }
- /*
- 1) neither in a group: create new group with 2 nodes
- 2) only one in a group: add the other
- 3) both already in same group - increase Links
- 4) both already in different groups... join groups
- *
- */
- public void AddFriendshipToGroups(int id1, int id2)
- {
- int groupId1 = groupIdMap[id1];
- int groupId2 = groupIdMap[id2];
- if (groupId1 == 0 || groupId2 == 0)
- {
- if (groupId1 == 0 && groupId2 == 0)
- {
- groupIndex++;
- groupCount++;
- groups[groupIndex].Links = 1;
- groups[groupIndex].Nodes = new Stack<int>();
- groups[groupIndex].Nodes.Push(id1);
- groups[groupIndex].Nodes.Push(id2);
- groupIdMap[id1] = groupIndex;
- groupIdMap[id2] = groupIndex;
- }
- else if (groupId1 == 0)
- {
- // add student1 into student2's group
- groups[groupId2].Nodes.Push(id1);
- groups[groupId2].Links++;
- groupIdMap[id1] = groupId2;
- }
- else
- {
- // add student2 into studnet1's group
- groups[groupId1].Nodes.Push(id2);
- groups[groupId1].Links++;
- groupIdMap[id2] = groupId1;
- }
- }
- else
- {
- if (groupId1 == groupId2)
- {
- groups[groupId1].Links++;
- }
- else // merge two groups
- {
- groupCount--;
- int groupSize1 = groups[groupId1].Nodes.Count;
- int groupSize2 = groups[groupId2].Nodes.Count;
- if (groupSize1 < groupSize2)
- {
- // small, big, groupId, nodeGroupId
- Group.MergeSmallGroupToLargeOne(groups, groupId1, groupId2, groupIdMap);
- }
- else
- {
- Group.MergeSmallGroupToLargeOne(groups, groupId2, groupId1, groupIdMap);
- }
- }
- }
- }
- }
- /*
- * descending
- */
- public class GroupComparer : Comparer<Group>
- {
- public override int Compare(Group x, Group y)
- {
- return (y.Nodes.Count - x.Nodes.Count);
- }
- }
- /*
- * add some calculation description here.
- */
- public class FriendshipValueCalculation
- {
- public static long FRIENDSHIPS_MAXIMUM = 200000;
- public static ulong[] GetLookupTable()
- {
- ulong[] friendshipsLookupTable = new ulong[FRIENDSHIPS_MAXIMUM]; // 1.6 MB
- ulong valueOfFriendship = 0;
- for (int i = 1; i < FRIENDSHIPS_MAXIMUM; i++)
- {
- valueOfFriendship += (ulong)i * (ulong)(i + 1);
- friendshipsLookupTable[i] = valueOfFriendship;
- }
- return friendshipsLookupTable;
- }
- }
- static void Main(String[] args)
- {
- ProcessInput();
- //RunSampleTestcase();
- //RunSampleTestcase2();
- }
- public static void ProcessInput()
- {
- GroupComparer headComparer = new GroupComparer();
- int queries = Convert.ToInt32(Console.ReadLine());
- for (int query = 0; query < queries; query++)
- {
- string[] tokens_n = Console.ReadLine().Split(' ');
- int studentsCount = Convert.ToInt32(tokens_n[0]);
- int friendshipsCount = Convert.ToInt32(tokens_n[1]);
- GroupManagement groupManager = new GroupManagement(studentsCount);
- for (int i = 0; i < friendshipsCount; i++)
- {
- string[] relationship = Console.ReadLine().Split(' ');
- int id1 = Convert.ToInt32(relationship[0]);
- int id2 = Convert.ToInt32(relationship[1]);
- groupManager.AddFriendshipToGroups(id1, id2);
- }
- // Get all groups large to small
- Group[] sortedGroups =
- Group.GetNonemptyGroups(
- groupManager.groupCount,
- groupManager.groupIndex,
- groupManager.groups);
- Array.Sort(sortedGroups, headComparer);
- Console.WriteLine(Group.CalculateValue(sortedGroups));
- }
- }
- /*
- *
- * 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()
- {
- 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";
- Console.WriteLine(HelpTestCase(datas, allFriendships));
- }
- public static void RunSampleTestcase2()
- {
- 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] = "3 2";
- allFriendships[0][2] = "4 2";
- allFriendships[0][3] = "4 3";
- Console.WriteLine(HelpTestCase(datas, allFriendships));
- }
- private static ulong HelpTestCase(string[][] datas, string[][] allFriendships)
- {
- GroupComparer headComparer = new GroupComparer();
- int studentsCount = Convert.ToInt32(datas[0][0]);
- int friendshipsCount = Convert.ToInt32(datas[0][1]);
- GroupManagement groupManager = new GroupManagement(studentsCount);
- for (int i = 0; i < friendshipsCount; i++)
- {
- string[] relationship = allFriendships[0][i].Split(' ');
- int id1 = Convert.ToInt32(relationship[0]);
- int id2 = Convert.ToInt32(relationship[1]);
- groupManager.AddFriendshipToGroups(id1, id2);
- }
- // Get all groups large to small
- Group[] sortedGroups =
- Group.GetNonemptyGroups(
- groupManager.groupCount,
- groupManager.groupIndex,
- groupManager.groups);
- Array.Sort(sortedGroups, headComparer);
- return Group.CalculateValue(sortedGroups);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement