Editorial of MindCoding 2017 Round 4 Bitdefender (Div. 2)

Let's analyze some properties of constructing special numbers:

• We can only use prime digits: 2, 3, 5, 7.
• We can not use the same digit twice, as it would create a subnumber which is a multiple of 11.
• If we use 2 or 5, they must be the first digit in the number. Otherwise, at least one subnumber would be either even or a multiple of 5.

All of these constraints reduce the search space by a significant amount. From this point on, we can easily generate all special numbers: [2, 3, 5, 7, 23, 37, 53, 73].

The query constraint is what makes this problem tricky, as there is no special number in the interval [74, 10⁹].

Approach #1 (Costin Andrei Oncescu)

Let y = 2ⁱ be the smallest power of 2 strictly greater than K. We choose as the elements of S all values in the interval [y-k, y-1].

Consequences:

• We already have exactly K values in S. Each value will constitute a subset by itself, and provide a distinct value in F(S).
• For any two values a, b ∈ [y-k, y-1], we have (a OR b) ∈ [y-k, y-1]. In other words, there will be no additional values generated by larger subsets of S. To better understand the intuition behind this, try to imagine the binary representation of all values in the given interval.

Approach #2 (Sergiu Puscas)

Since the constraints for this problem are not very strict, we can try to construct a solution in the following way:

• Start with S = {1} (or any other value).
• While |F(S)| ≠ K:
  • If |F(S)| < K, choose a new value randomly and add it to the set.
  • If |F(S)| > K, choose an existing value randomly and remove it from the set.
• Print the elements of S.

This approach finds a solution relatively quickly, assuming an efficient implementation of the method that computes F(S).

In practice, it yields a set that is much smaller than than K elements.