TopCoder problem "NumberGraph" used in TCO09 Round 5 (Division I Level Three)



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.
 

Definition

    
Class:NumberGraph
Method:largestSet
Parameters:String[], int[]
Returns:int
Method signature:int largestSet(String[] graphSet, int[] joiningSet)
(be sure your method is public)
    
 

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.
 

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)
    
{"10 6 130 162 164 39 73 27 72 167 41"}
{3,63,95,123,57,91,35,137
,135,125,33,121,17,5,31
,45,67,29,157}
Returns: 8
4)
    
{"2136 2108 876 8"
,"6 348 8 1784 1146 1596 608 446 14"
,"64"
," 344 1452 1938 692 376 1482 860 1870"}
{644,844,348,604,1260,516,868,2100,260
,1492,316,1076,268,852,12,1500,4,772
,1108,188,1444,1764,84,1732,532,332
,1588,500,700,1116,252,1060,68,1092
,724,132,484,340,684,1276,28,1788,588}
Returns: 12
5)
    
{"1000000"}
{1}
Returns: 1
6)
    
{"1 2 3 4 5 6 7 8"}
{1}
Returns: 3

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10319

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13763&pm=10319

Writer:

StevieT

Testers:

PabloGilberto , legakis , ivan_metelsky , zhuzeyuan

Problem categories:

Graph Theory, Math