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