Decouple the relation and approach in different metrics
Posted on 2015-07-27 07:49:07 +0900 in Algorithm
Problem H – Humble Captains
The problem is given an undirected graph (Vertices<=300), and need to color its vertices into red and blue in such a way that the total number of edges between the red vertices is as close as possible to the total number of edges between the blue vertices.
The key point lies in the way to count valid edges.
For each edge $e$ with two vertices $v1$, $v2$, define , then
Now try to find $count$ from vertices.
Then the final problem can be rephrased to look for a partition which minimizes the absolute difference between the sums of the numbers in each part, which could solved with dynamic programming easily.
This is really a nice problem, which requires to decouple the relations, and approach it in different metrics. The problem is found from Petr’s blog, official analysis.