# Problem Link:

# Difficulty:

Challenge

# Pre-requisites:

local-search

# Problem:

Given a set of numbers, find a subset of maximum size that does not contain an arithmetic progression.

# Explanation:

Let us consider maximal AP-free subsets. By maximal, we mean that adding any more element into the set would cause it to form an AP. We would now like to perform a local search over such sets.

In order to define a local move, we should have a good neighborhood relation. For this, we define a “ready” number as one which is not in the set, but when added to it would cause only one AP to form. With this in mind, a natural local move would involve adding a ready number, removing one of the two other numbers that formed the AP, and then trying to make the set maximal.

The next thing to look out for, is to try to incorporate a metric on our local search - some way of knowing we’re doing better. Here, from a set of size M, we will always move to sets of size M, and then try to increase their size. So merely having the size of solution as the metric is vague. Setter uses Number of ready numbers as the metric, so that we have more options to move to a better solution.

Finally, use simulated annealing with the above metric.

In order to find a good initial solution, setter used the following approach.

Choose a base B, and write all the numbers in base B - lets say they have k digits.

Now, let each digit be a dimension in space, and then write map the numbers onto “Spheres” of that space - here, consider only numbers whose all digits are <= B/2. Then, taking all numbers of any sphere will be a valid solution, since the sum of any two such numbers, divided by two, will be a point outside this sphere.

This solution gave Setter a score of ~5.2 - while the contest’s best was ~5.8.

# Setter’s Solution:

Will be updated soon.

# Tester’s Solution:

Can be found here