Connection Status:
Competition Arena > NumberGraph

NumberGraph

TCO09 Round 5 · 2009-02-24 · by StevieT

TCO09 Round 5 · 2009-02-24 · by StevieT · Graph Theory, Math
Class Name: NumberGraph
Return Type: int
Method Name: largestSet
Arg Types: (vector<string>, vector<int>)
Problem Statement

Problem Statement

Two integers X and Y are joined by a positive integer P if the magnitude of their difference |X-Y| = P. X and Y are joined by a set of integers if they are joined by one of the numbers in that set. You are given a set of positive integers joiningSet, with the property that the number of trailing zeros in the binary representation of each integer in joiningSet is the same. You are also given a set of integers in a String[] graphSet. Concatenate the elements of graphSet to obtain a space-separated list of these integers. Consider the graph G with an edge joining each pair of numbers in graphSet that is joined by joiningSet. Determine the size of the largest subgraph of G, such that no pair of vertices in the subgraph is separated by a distance greater than 2.

Notes

  • In this problem, the size of a graph is equal to the number of vertices it contains.
  • The distance between two vertices is the length of the shortest path joining them, and can be considered infinite if the vertices are not connected.
  • The distance is measured within the taken subgraph, not within the whole graph.

Constraints

  • graphSet and joiningSet will each contain between 1 and 50 elements, inclusive.
  • Each element of joiningSet will be between 1 and 1000000 (10^6), inclusive.
  • Each element of graphSet will contain between 1 and 50 characters, inclusive.
  • The concatenation of the elements of graphSet will be a single-space-delimited list of integers, formatted without extra leading zeros.
  • graphSet will contain between 1 and 80 integers, inclusive.
  • Each integer in graphSet will be between 0 and 1000000 (10^6), inclusive.
  • The integers within each of graphSet and joiningSet will be distinct.
  • The lowest set bit in the binary representation of each element of joiningSet will be the same.

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
{"1 2 3 4 6 9 13 15 16 18 21 26"}
{2,6,10}
Returns: 4

The subgraph induced by {3,9,13,15} is optimal in this case. 3 and 15 are both joined to 9 and 13, so any distance in this subgraph is no greater than 2.

1)
{"4 11 12 10 9 6 2 7 1 8 5"}
{3,5,1,7}
Returns: 9

The subgraph induced by {4, 12, 10, 9, 6, 2, 7, 8, 5} is optimal here.

2)
{"100 260 164 244 84 340 52 2"
,"12 388 4 308 180 228 484"}
{16,176,208,48,240,80}
Returns: 8

The number "212" has been separated into two parts "2" and "12". Make sure you concatenate the Strings before splitting into numbers.

3)
{"15905 3"
,"29 20905 11041 17193"
," 9697 26489 210"
,"73 5425 21273 23417 2324"
,"9 3601 11649 1019"
,"3"}
{2392,5096,7880,10712,15576
,8824,6056,9368,9864,3880
,15144,13720,3272,16792,2056
,28760,3464,11768,11320,7272}
Returns: 8
4)
{"2847 79 3075 4811 5003 3195 2663 1907 24"
,"67 2891 1459 3315 1287 1867 2363"
," "
,"147"
,"1 2795 1483 2667 1695"}
{756,156,1500,988,1100,212,772,612
,588,28,556,668,1180,420,172,1212
,796,596,1404,972,412,236,1116,1196
,780,572}
Returns: 11

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

Coding Area

Language: C++17 · define a public class NumberGraph with a public method int largestSet(vector<string> graphSet, vector<int> joiningSet) · 224 test cases · 2 s / 256 MB per case

Submitting as anonymous