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

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.

Let's denote:

• first[x] = the position of the first occurence of x
• second[x] = the position of the second occurence of x

We can take advantage of the fact that these intervals are already sorted by their beginning.
We will proces each number from the input. Suppose we are at number i. If this is the first i we've encountered, then we will insert it in data structure. If it is the second one, then we need to query the data structure to get how many intervals are opened in the interval first[i], second[i], but close after second[i]. Because we process each point in sorted order, we can keep a segment tree or a similar DS that can provide add(pos, value) and getSum(x, y)