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

## D - ABC Transform Editorial by en_translator

### Preface

In this editorial, we use $$0$$-based index, instead of $$1$$-based index, for $$S$$. In other words, when the length of $$N$$ is $$S$$, $$S = S_1 S_2 \ldots S_N$$, not $$S = S_0 S_1 \ldots S_{N-1}$$.

### Body

Let $$f(t,k)$$ be “the function that returns the $$k$$-th character of $$S^{(t)}$$.”

First, for $$t = 0$$, $$f(t,k)$$ is the $$k$$-th character of $$S$$.

Next, we consider the case where $$k = 0$$. Taking a closer look, we can see that the $$0$$-th characters of $$S^{(0)}, S^{(1)}, S^{(2)}, S^{(3)}, S^{(4)} \ldots$$ are either

• A, B, C, A, B, $$\ldots$$
• B, C, A, B, C, $$\ldots$$
• C, A, B, C, A, $$\ldots$$

which are periodic.

If the successor of A is defined to be B, B is C, and C is A, then the $$0$$-th character of $$S^{(t)}$$ is the $$t$$-th successor of the first character of $$S^{(0)}$$.

Therefore, when $$k = 0$$, $$f(t,k)$$ is the $$k$$-th successor of $$S_0$$.

Finally, let’s consider what $$f(t,k)$$ returns when $$0 \lt t,k$$.

Taking a closer look again, we can see that

• when $$k$$ is even, $$f(t,k)$$ is the first successor of $$f(t-1,\frac{k}{2})$$;
• when $$k$$ is odd, $$f(t,k)$$ is the second successor of $$f(t-1,\frac{k}{2})$$.

Thus, for $$0 \lt t,k$$, we can recursively obtain $$f(t,k)$$ based on the value of $$f(t-1,\lfloor \frac{k}{2} \rfloor)$$. Here, $$\lfloor \frac{k}{2} \rfloor$$ is $$\frac{k}{2}$$ rounded down.

Therefore, $$f(t, k)$$ is

• the $$k$$-th character of $$S$$ if $$t=0$$;
• the $$k$$-th successor of $$S_0$$ if $$k=0$$;
• the (remainder of $$k$$ by $$2$$, plus $$1$$)-th successor of $$f(t-1,\lfloor \frac{k}{2} \rfloor)$$ if $$t=0$$.

We can code the procedure as follows.

Sample code (C++)

#include<bits/stdc++.h>
using namespace std;

using ll = long long;

int main(){

string S; cin >> S;
int Q; cin >> Q;

auto g = [&](char s, ll add){
};

std::function<char(ll,ll)> f = [&](ll t, ll k){
if(t == 0) return S[k];
if(k == 0) return g(S,t);
return g(f(t-1,k/2),k%2+1);
};

while(Q--){
ll t,k; cin >> t >> k;
cout << f(t,k-1) << endl;
}

}


The time complexity is $$O(N + Q \log (\max(k)))$$, because for each query the function $$f$$ is called at most $$O(\log k)$$ times.

This is very fast, even in PyPy3 where recursive function is generally said to be slow:

Sample code (PyPy3)

posted:
last update: