Contest Duration: - (local time) (120 minutes) Back to Home
Official

## F - Delete 1, 4, 7, ... Editorial by evima

### [1] Computation in $$O(NK\cdot (2/3)^K)$$ time

Let $$N_k$$ be the number of elements after $$k$$ operations. $$N_k$$ can be computed from $$N_{k+1} = \lfloor \frac{2N_k}{3}\rfloor$$. Particularly, $$N_K$$, the number of elements in the sequence in question, can be computed in $$O(K)$$ time. Let $$M$$ denote this number.

Let $$B = (b_0, b_1, \ldots)$$ be the result of applying the operation on the sequence $$A = (a_0, a_1, \ldots)$$. $$b_i$$ can be computed from the following rule: $$b_i = a_{j}$$, where $$j = \lfloor \frac{3i+2}{2}\rfloor$$.

Thus, by letting $$f(i) = \lfloor\frac{3i+2}{2}\rfloor$$, the problem can be rephrased as follows:

Find $$\sum_{n=0}^{M-1} \bigl(f^K(n) + 1\bigr)$$.

Here, $$f^K$$ is the $$K$$-times self composition of $$f$$.

An approach that directly computes this has the complexity of $$O(MK)$$. Since $$M\leq N\cdot (2/3)^K$$, it takes $$O(NK\cdot (2/3)^K)$$ time.

### [2] Computation in $$O(K\cdot 2^K)$$ time

It can be recursively verified that $$f^K$$, the self composition of $$f$$, has the following periodicy: $$f^K(n + 2^K) = f^K(n) + 3^K$$.

By computing the contributions of $$n$$ such that $$n\equiv i \pmod{2^K}$$ altogether after precomputing $$f^K(i)$$ for $$0\leq i < 2^K$$, the computation can be done in $$O(K\cdot 2^K)$$ time.

### [3] Computation in $$O((K+\log N)\cdot 2^{K/2})$$ time

Let $$X$$ and $$Y$$ be integers such that $$K = X + Y$$, and decompose the function as $$f^K(n) = f^Y(f^X(n))$$. Additionally, for $$f^X$$ and $$f^Y$$, we do the precomputation similar to the one in [2].

To compute the contributions of $$n$$ such that $$n\equiv i \pmod{2^X}$$ for each $$i$$, we need the following computation:

• Find $$\sum_{j}f^Y(a + 3^X j)$$.

This can be done fast by precomputing all sums in the form $$f^Y(a) + \cdots + f^Y(a + (2^k-1)3^X)$$.

By choosing $$X = \lceil N/2\rceil$$ and $$Y = \lfloor N/2\rfloor$$, this solves the problem in, for example, $$O((K+\log N) \cdot 2^{K/2})$$ time.

### [4] Conclusion

By choosing between the methods [1] and [3], the problem can be solved in the following time complexity: $$O(\min(NK\cdot (2/3)^K, (K+\log N) \cdot 2^{K/2}))$$.

It is possible to get accepted by, for example, using the method [1] if $$K > 40$$ and the method [3] if $$K\leq 40$$.

Below are some possible optimizations of the solution, none of which should be required to fit within the time limit.

• Optimize the computation of $$f^K(n)$$ in an approach similar to the one in [3].
• Perform the precomputation of $$f^X(i)$$ in $$O(2^X)$$ time.
• For the computation of $$\sum_j f^Y(a + 3^Xj)$$ in [3], precompute the prefix sums at every $$3^X$$ terms in $$O(2^Y)$$ time to process each query in $$O(1)$$ time, for a total of $$O(2^{K/2})$$ time.

posted:
last update: