GraphInversions | Topcoder Archive

Problem Statement

You are given a connected undirected graph with N vertices. The vertices are numbered 0 through N-1. The graph is special: the number of edges is exactly equal to the number of vertices. You are given the description of the graph as three int[]s: A, B, and V. Each of these int[]s has N elements. For each valid i, there's an edge between vertices A[i] and B[i]. There are no self-loops and no duplicate edges. For each valid i, we associate the value V[i] with the vertex i.

We will be interested in some simple paths in this graph. A simple path is a sequence of vertices such that no vertex is used twice, and each pair of consecutive vertices is connected by an edge. For any simple path, we can write down a sequence of integers: the values associated with the vertices on the path, in order of appearance. We will call such a sequence the value list of the given simple path.

An inversion in a sequence S is a pair of valid indices (i,j) into the sequence S such that i < j but S[i] > S[j]. For example, the sequence S = {10, 30, 20, 20} has two inversions: (1,2) and (1,3). (The indices are 0-based.)

You are given a graph G in the format described above, and an int K. In the graph G, consider all simple paths with K or more vertices. If there is no such simple path, return -1. Otherwise, return the smallest number of inversions in the value list of such path.

Definition

Class:: GraphInversions
Method:: getMinimumInversions
Parameters:: int[], int[], int[], int
Returns:: int
Method signature:: int getMinimumInversions(int[] A, int[] B, int[] V, int K)
(be sure your method is public)

Constraints

N will be between 3 and 1000, inclusive.
A, B, and V will each have N elements.
Each element of A and B will be between 0 and N-1, inclusive.
For all valid i, A[i] will not be equal to B[i]. (I.e., there are no self loops.)
No two edges will connect the same pair of vertices.
The graph described by A and B will be connected.
Each element of V will be between 1 and 1000, inclusive.
K will be between 1 and N, inclusive.

Examples

```
{0,1,2}
```
```
{1,2,0}
```
```
{40,50,60}
```
```
3
```
```
Returns: 0
```
The best path is the path {0, 1, 2}. Its value list is the sequence {40, 50, 60}, and there are 0 inversions in this sequence.
```
{0,1,2,3}
```
```
{1,2,3,0}
```
```
{60,40,50,30}
```
```
3
```
```
Returns: 1
```
As K=3, we are interested in simple paths of lengths 3 or more. Each simple path of length 3 or more gives us at least one inversion. The path {3, 2, 1} is an example of an optimal path. Its value list is {30, 50, 40}. There is 1 inversion: the 50 occurring before the 40.
```
{0,1,2,3,0}
```
```
{1,2,3,0,4}
```
```
{10,10,10,5,5}
```
```
5
```
```
Returns: 1
```
Two or more nodes can have the same associated value.

{0,1,2,3,0,2}

{1,2,3,0,4,5}

{10,2,5,3,7,1}

Returns: -1

There are no simple paths with length 6.

{5,7,7,5,5,7,6,4}

{2,0,2,0,1,4,7,3}

{15,10,5,30,22,10,5,2}

Returns: 3

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)2024, Topcoder, Inc. All rights reserved.