TopCoder problem "ArithmeticProgressions" used in SRM 365 (Division I Level Two)



Problem Statement

    You are given a String[] numbers containing a set of distinct non-negative integers (no leading zeroes). Let m be the smallest integer in numbers, and let M be the largest integer in numbers. An arithmetic progression of integers a+id, a+(i+1)d, ..., a+(j-1)d, a+jd is called proper if it satisfies all of the following conditions:
  1. It contains at least 3 distinct integers from numbers.
  2. All of the numbers in the progression are integers between m and M, inclusive.
  3. If it were extended in either direction, condition 2 would no longer be satisfied. In other words, neither a+(i-1)d nor a+(j+1)d are between m and M, inclusive. (See example 0 for further clarification.)
Given a proper arithmetic progression, let a be the number of integers in the progression that are contained in numbers, and let b be the total number of integers in the progression. The aptitude of the progression is defined as a divided by b. Given numbers, return the maximal aptitude of a proper arithmetic progression as a String[] containing exactly 2 elements representing 2 integers (with no leading zeroes), first of which divided by the second equals the maximal aptitude. The first and the second elements of String[] you return must represent non-negative integers which do not have common divisors greater than 1. Return {"0", "1"} if no proper arithmetic progression exists.
 

Definition

    
Class:ArithmeticProgressions
Method:maxAptitude
Parameters:String[]
Returns:String[]
Method signature:String[] maxAptitude(String[] numbers)
(be sure your method is public)
    
 

Constraints

-numbers will contain between 1 and 50 elements, inclusive.
-Each element of numbers will contain between 1 and 18 characters, inclusive.
-Each character of every element of numbers will be a digit ('0'-'9').
-No element of numbers will contain '0' (zero) as its first character.
-All elements of numbers will be distinct.
 

Examples

0)
    
{"1", "3", "5", "8"}
Returns: {"3", "4" }
We have two proper arithmetic progressions here: 1, 2, 3, 4, 5, 6, 7, 8 and 1, 3, 5, 7. Both of them can not be extended since neither 0, nor 9 lies in [1; 8] in the first case and neither -1, nor 9 lies in [1; 8] in the second case. 4 elements of the first progression belong to numbers and so its aptitude is 4/8 = 1/2. 3 elements of the second progression belong to numbers and so its aptitude is 3/4, which is highest possible in this case.
1)
    
{"1", "3", "5", "7", "9", "11", "13", "15", "17", "19"}
Returns: {"1", "1" }
The elements of numbers form a proper arithmetic progression, hence its aptitude is 1.
2)
    
{"1", "999999999999999999"}
Returns: {"0", "1" }
There are not enough elements in numbers to form a proper arithmetic progression.
3)
    
{"1", "7", "13", "3511", "1053", "10", "5"}
Returns: {"3", "391" }
The elements of numbers are not necessarily sorted.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10780&pm=7856

Writer:

Xixas

Testers:

PabloGilberto , Yarin , Olexiy , ivan_metelsky

Problem categories:

Math, Search