JOIN
Get Time

   Problem Statement  

 Problem Statement for Gperm

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.
 

Definition

    
Class:Gperm
Method:countfee
Parameters:int[], int[]
Returns:int
Method signature:int countfee(int[] x, int[] y)
(be sure your method is public)
    
 

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
5)
    
{45,28,42,5,27,27,42,36,14,27,19,42,24,27,8,31,24,27,14,28}
{45,27,45,8,34,34,28,0,11,42,24,19,14,31,45,42,14,24,28,27}
Returns: 53

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 696 Round 1 - Division I, Level One