CliqueGraph
TCO14 Round 2C · 2014-03-26 · by snuke
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
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.
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.
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:
15
{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
12
{0,1,2,3,4,5,6,7,8,9,10,11}
{12}
Returns: 66
2
{0,1}
{2}
Returns: 1
64
{0,1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,53,55,57,59,61,63,0,2,3,6,7,10,11,14,15,18,19,22,23,26,27,30,31,34,35,38,39,42,43,46,47,50,51,54,55,58,59,62,63,4,5,6,7,12,13,14,15,20,21,22,23,28,29,30,31,36,37,38,39,44,45,46,47,52,53,54,55,60,61,62,63,8,9,10,11,12,13,14,15,24,25,26,27,28,29,30,31,40,41,42,43,44,45,46,47,56,57,58,59,60,61,62,63,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63}
{33,33,32,32,32,32}
Returns: 2332
(I'll add some random case.)
Submissions are judged against all 93 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CliqueGraph with a public method long long calcSum(int N, vector<int> V, vector<int> sizes) · 93 test cases · 2 s / 256 MB per case