Connection Status:
Competition Arena > Gperm

Gperm

SRM 696 · 2016-07-09 · by subscriber

SRM 696 · 2016-07-09 · by subscriber · Brute Force
Class Name: Gperm
Return Type: int
Method Name: countfee
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

Hero has an undirected multigraph. (Each pair of vertices can be connected by arbitrarily many undirected edges. There may also be arbitrarily many self-loops at each vertex.) Hero's graph has exactly 50 vertices, labeled 0 through 49. The graph has at most 20 edges. You are given the list of those edges: the int[]s x and y. For each valid i, there is an edge that connects the vertices x[i] and y[i]. (Self-loops have x[i] = y[i].) Hero needs to paint all vertices red. He can paint the vertices in any order he likes, one vertex at a time. Each time he paints a vertex he has to pay a fee. The fee is computed as the number of edges that already have both endpoints red. Hero wants to minimize the sum of all fees he has to pay. Find the order in which he should paint the vertices, and return the corresponding total fee.

Constraints

  • x will contain between 1 and 20 elements, inclusive.
  • x and y will contain the same number of elements.
  • Each element in x and y will be between 0 and 49, inclusive.
Examples
0)
{0}
{1}
Returns: 1

One optimal order of painting the vertices is 49, 48, 47, ..., 3, 2, 1, 0. The first 49 times the fee is 0. After Hero paints the last vertex, the last fee is 1.

1)
{0,1}
{1,2}
Returns: 2

One optimal order of painting these vertices is 49, 48, ..., 5, 4, 3, 0, 2, 1. The last three fees will be 0, 0, and 2.

2)
{4,7,7}
{7,4,4}
Returns: 3
3)
{0,0,1}
{1,2,2}
Returns: 4

Hero should first paint the 47 isolated vertices and then the remaining three vertices in any order. Regardless of the order in which Hero paints the last three vertices, the last three fees will be 0, 1, and 3.

4)
{7,8,9}
{4,5,6}
Returns: 6

Submissions are judged against all 166 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Gperm with a public method int countfee(vector<int> x, vector<int> y) · 166 test cases · 2 s / 256 MB per case

Submitting as anonymous