My friend had a coding test today and he had this question that he wasn't able to solve, like wise for me after thinking I could only see the brute force approach.
The Question.
There's an initial string given str which has only A,B,C now a sequence of strings is created S where S[0]=str and then S[i] is made from S[i-1] after replacing A by BC and B by CA and C by AB for ex. if s[0]=AB then S[1]= BCCA ( A was replaced by BC and B by CA)
Now there's m queries given, in each query there's two integers i and j and we want to print the i th character of S[j]
. Ex str=A m=1 i=1 j=2
S[1]=BC S[2]=CAAB
and 1st character of S[2] is C.
i and j goes to 10^9 m goes to 10^5
I could only think of the brute force approach which obviously wouldn't work, could you share a better approach?
For convenience, let $$$S_{i,j}$$$ be the $$$j$$$-th character of $$$S_i$$$. It is obvious that $$$S_{i,j}$$$ depends on $$$S_{i-1,\lceil j/2\rceil}$$$. So we can simply trace back $$$O(\log j)$$$ times and stop when $$$i$$$ reaches $$$0$$$ or $$$j$$$ reaches $$$1$$$.
If $$$i$$$ reaches $$$0$$$, we can find out $$$S_{0,*}, ..., S_{i-1,\lceil j/2\rceil}, S_{i,j}$$$ in order. If $$$j$$$ reaches $$$1$$$, note that $$$S_{i+3, 1} = S_{i,1}$$$ so we can find out $$$S_{*,1}$$$ first, then use the same method like previous one to find out the answer.
It works in $$$O(m \log j)$$$ time. Hope it is a correct approach.
Hi, thanks for your reply.
I am trying to understand your method(I am a bit slow).
What would you say is the difficulty of this problem?
I'm sorry, I get that we can trace back so say str='A' and I want to find i=4,j=2, I trace back to i=3,j=1 So now I have to find S 3,1 after that I am a bit lost, can you please explain a bit.
Thanks again.
I found the meanings of marks $$$i,j$$$ that I used are different from yours. Sorry for bringing confusion to you.
Let's write out $$$S$$$ to make it clearer: $$$S_0 = \mathtt{A}$$$, $$$S_1 = \mathtt{BC}$$$, $$$S_2 = \mathtt{CAAB}$$$, $$$S_3 = \mathtt{ABBCBCCA}$$$, $$$S_4 = \mathtt{BCCACA...}$$$.
Focusing on the first character of each $$$S_i$$$, it can be shown that they are $$$\mathtt{ABCABC...}$$$ or $$$\mathtt{BCABCA...}$$$ or $$$\mathtt{CABCAB...}$$$, depending on what $$$S_{0,1}$$$ is. So we can point out that $$$S_{3,1} = S_{3\bmod 3, 1} = S_{0,1} = \mathtt{A}$$$.
We want to find $$$S_{4,2}$$$ so we trace back to $$$S_{3,1}$$$, which is $$$\mathtt{A}$$$. Then we know that $$$S_{4,2}$$$ is the second character of the replacement of $$$S_{3,1} = \mathtt{A}$$$, which means $$$S_{4,2} = \mathtt{C}$$$.