# PROBLEM LINK:

Practice

Contest

**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.

asked
**27 Apr '15, 19:17**

4★adurysk ♦

928●5●24●28

accept rate:
11%