PROBLEM LINK:
Author: Vitalij Kozhukhivskij
Tester: Sergey Kulik
Editorialist: ADURY SURYA KIRAN
DIFFICULTY:
CHALLENGE
PROBLEM:
Given a graph with N vertices. N is even. You need to divide the graph into two parts each containing N/2 vertices each such that sum of weights of all the edges of which the two vertices are present in different parts is minimised.
EXPLANATION:
Let us say we have two sets of vertices, A and B. Initially Set A has all N vertices and Set B is empty.
For each vertex in A, let us store the sum of weights of all the edges which are connected to this vertex and other vertices in A, lets call this dp[u] for the vertex u. We are storing this because when we remove the vertex u from A and add it to B, the answer will increase by dp[u] (not entirely as you see in the later part of the editorial).
In the first step we select the vertex u which has least dp[u] and remove this vertex from A and throw it to B. Now update the dp[v] of all vertices v of A, which have are adjacent to vertex u. We repeat the above procedure for N/2 times to get the final answer.
Subtasks 1 and 2:
In each step, we iterate through all vertices of A, find the vertex with minimum dp[u] in O(N). As we will be performing N/2 steps, complexity of this will be O(N^2) which should be able to pass in time for subtasks 1 and 2.
Subtasks 3 and 4:
For finding the vertex u with least dp[u] in a faster way, we can use one of the following two methods:
- Build a segment tree on all the values of dp[u]. Minimum can be queried and dp[] values of vertices can be updated in O(log(N)) using the segment tree. Now after each step, update the value of dp[u] to very big value say 10^18, so that next time when we query for vertex with minimum dp[] value, this vertex u does not show up. Complexity is O(N*log(N)).
A good read on segment trees can be found here - Maintain a Heap / Set / Priority Queue. Let’s insert a pair of values into the heap for each vertex, i.e, pair(dp[u], u). This can be done using pair<long long, int> in C++. We can pop out the minimum pair, theoretically remove the corresponding vertex from the set A and add it to B, update the dp[] values for all the adjacent vertices of current vertex and insert a new pair into the heap for each updated vertex. As we are inserting more than one pair for each vertex, we also need to maintain a boolean visited array and not remove a vertex more than once. For each edge, we will add a new pair into the heap, and also we add a pair for each vertex initially. So the complexity will be O((N + M) * log(N)).
This method gives around 0.7-0.8 points.
In this method, when we are removing a vertex, we are considering only the edges which are connected to other vertices in A. The edges which are connected between vertices in A and vertices in B are not considered. So for each vertex in A, we can store the sum of weights of edges which are connected to other vertices in A minus the sum of weights of edges which are connected to other vertices in B in the variable dp[u], because when we add this vertex into set B, the edges which connect other vertices in B are not counted in the score.
For the first few vertices of A, which we throw into B in the beginning, the edges which are connected to A, are not that important than the edges which are connected to vertices in B. Because, many other vertices in A which are connected to the current vertex now will be thrown into B later.
So we can put a threshold t and for first t steps, for each vertex u in A, we store negative of sum of weights of all the edges which are connected to B, in dp[u] and throw minimum dp[] valued vertex into B, and after t steps, for each vertex u in A, we store the sum of edges which are connected to other vertices in A minus the sum of edges which are connected to other vertices in B. Making this change will give a score above 0.9.
AUTHOR’S AND TESTER’S SOLUTIONS:
To be posted soon.