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$.