CliqueGraph | Topcoder Archive

Problem Statement

Fox Ciel has an unweighted undirected connected graph G with N vertices. The vertices are numbered 0 through N-1. The graph has a special structure. You are given its description in two int[]s V and sizes. V contains a sequence of vertex numbers. Note that some vertex numbers may occur in V multiple times.

For each valid i, let S[i] be the sum of the first i elements of sizes. For example, if sizes={10,20,30} then S[0]=0, S[1]=10, S[2]=10+20=30, and S[3]=10+20+30=60.

The graph G that is described by V and sizes looks as follows: For each valid i, consider all pairs (j,k) such that S[i] <= j < k < S[i+1]. For each such pair (j,k), our graph G contains an edge between the vertices V[j] and V[k]. There are no other edges in G, only those defined above. You may assume that V and sizes are always such that the resulting graph G is connected.

For each pair of vertices, compute their distance. Return the sum of all those distances.

Definition

Class:: CliqueGraph
Method:: calcSum
Parameters:: int, int[], int[]
Returns:: long
Method signature:: long calcSum(int N, int[] V, int[] sizes)
(be sure your method is public)

Notes

For some test cases, the correct return value may overflow a signed 32-bit integer variable.

Constraints

N will be between 2 and 2,500, inclusive.
V will contain between 1 and 5,000 elements, inclusive.
Each element of V will be between 0 and N-1, inclusive.
sizes will contain between 1 and 2,500 elements, inclusive.
Each element of sizes will be between 2 and N, inclusive.
The sum of all elements of sizes will be equal to the number of elements in V.
For each valid i, the elements V[S[i]], V[S[i]+1], ..., V[S[i+1]-1] will be distinct. (See the problem statement for the definition of S[i].)
The graph G described by V and sizes will be connected.

Examples

```
4
```
```
{0,1,2,0,3}
```
```
{3,2}
```
```
Returns: 8
```
The graph looks as follows: The distance between vertex 0 and vertex 1 : 1 The distance between vertex 0 and vertex 2 : 1 The distance between vertex 0 and vertex 3 : 1 The distance between vertex 1 and vertex 2 : 1 The distance between vertex 1 and vertex 3 : 2 The distance between vertex 2 and vertex 3 : 2 The sum is 8.
```
5
```
```
{0,1,2,3,1,2,4}
```
```
{4,3}
```
```
Returns: 12
```
The graph looks as follows:

{1,3,5,7,9,11,13,0
,2,3,6,7,10,11,14,0
,4,5,6,7,12,13,14,0
,8,9,10,11,12,13,14,0}

{8,8,8,8}

Returns: 130

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.