Subtask 1

The answers for ~N = 3~ are ~0, 1, 2, 3~.

Suppose the answers for ~N = 3^k~ are ~a_1, a_2, \dots, a_M~. The answers for the first third of ~N = 3^{k+1}~ are

$$\displaystyle a_1, a_2, \dots, a_M$$

The Cantor set has copies of the same structure. In particular, the first third of the Cantor set is identical to the last third. The remaining answers for ~N = 3^{k+1}~ are

$$\displaystyle 2 \times 3^k + a_1, 2 \times 3^k + a_2, \dots, 2 \times 3^k + a_M$$

These observations are enough to generate the answer for any power of ~3~.

Subtask 2

Note that ~\frac{34676}{51169}~ is covered by the ~49^\text{th}~ filter, but not any earlier filter. This is the maximum record for ~N \le 10^5~. A naive approach is expected to fail on ~N = 51169~.

This subtask requires deeper observations about Alice's filters.

Property 1 (Filters are symmetric). If ~r~ is covered by the ~k~-th filter, then ~1-r~ is covered by the ~k~-th filter. Likewise, if the ~k~-th filter does not cover ~r~, then ~1-r~ is not covered by the ~k~-th filter.

Property 2 (The ~k~-th filter and ~(k+1)~-th filter are related). Let ~k~ be a positive integer, and let ~0 \le r \le \frac 1 3~. If ~r~ is covered by the ~(k+1)~-th filter, then ~3r~ is covered by the ~k~-th filter. Likewise, if ~r~ is not covered by the ~(k+1)~-th filter, then ~3r~ is not covered by the ~k~-th filter.

The proof of these 2 properties is left as an exercise. From these properties, it becomes natural to define the function ~f(r) = 3 \times \min(r, 1-r)~. Here are a few theorems about ~f~.

Theorem 1. If ~r~ is not covered by any filter, then ~f(r)~ is not covered by any filter.
Proof. Apply Property 1 and Property 2.

Theorem 2. Suppose ~r~ is covered by the ~k~-th filter. Then either ~k = 1~, or ~f(r)~ is covered by the ~(k-1)~-th filter.
Proof. Apply Property 1 and Property 2.

Here is the approach to solving subtask 2:

• Let ~r = \frac x N~. Construct this sequence: ~r, f(r), f(f(r)), f(f(f(r))), \dots~
• If ~r~ is in the Cantor set, then by Theorem 1, every term in the sequence is in the Cantor set. Since every term is a multiple of ~\frac 1 N~, the sequence will enter a cycle.
• If ~r~ is not in the Cantor set, then ~r~ is covered by a filter. By Theorem 2, a term in the sequence will be covered by the first filter.

There are 2 outcomes. Either the sequence will enter a cycle, or a term will be covered by the first filter. The algorithm needs to handle both outcomes. The intended total time complexity is ~\mathcal O(N)~ or slightly slower.

Alternatively, it is enough to ignore cycle detection and construct the first ~49~ terms. In the worst case (i.e. ~r = \frac{34676}{51169}~), the ~49^\text{th}~ term is covered by the first filter.

Subtask 3

Note that ~\frac{222534799}{867579680}~ is covered by the ~130^\text{th}~ filter, but not any earlier filter. The author believes this is the maximum record for ~N \le 10^9~.

Firstly, use the first ~18~ filters to remove most of the numbers. After this step, less than ~10^6~ numbers remain.

Next, apply the algorithm from subtask 2 on each of the remaining numbers. It may be a good idea to use memoization to improve time complexity. There are other tricks to improve performance.

The intended time complexity is ~\mathcal O(N^{0.631} \log N)~ because there are ~\mathcal O(N^{0.631})~ numbers to consider, and each number takes roughly ~\mathcal O(\log N)~ to consider. Note: The exponent is exactly ~\log_3 2~.