Problem 2: Batmanacci

https://open.kattis.com/problems/batmanacci

Given $N$ and $K$, find the $K^{th}$ letter in the $N^{th}$ Batmanacci string.

We can store the length of each Batmanacci string in a list. (The length of the$N^{th}$string is simply the $N^{th}$Fibonacci number.)

Recurrence relation for the lengths:

Length[i] = Length[i - 1] + Length[i - 2], with base cases Length[0] = 0 and Length[1] = 1.

We can build the list of lengths using DP.

Observe that given some$N^{th}$ string, the first part of this string is the $(N-2)^{th}$ string.

• If $K$ is within the length of that $(N-2)^{th}$ string, then we can check that $(N-2)^{th}$ string to find the answer. (Denote the length of this $(N-2)^{th}$ string as $L.$)

• Otherwise,$K$ is greater than the length of the $(N-2)^{th}$string. Then the answer corresponds to the $(K - L)^{th}$ letter in the$(N-1)^{th}$string.

We can recursively obtain the desired $K^{th}$ letter in the $N^{th}$ string, taking advantage of the word lengths we previously stored.

Base cases in the recursion:

• N = 1: answer is 'N'

• N = 2: answer is 'A'

Recurrence relation:

• If K <= Length[N-2], go to the case for N-2, K.

• Otherwise, K > Length[N-2], so we go to the case for N-1, K-L.

After these recursive calls, we will arrive at one of the base cases (which gives us the final answer).

Note: make sure to use unsigned long long because the numbers can get very large.

For large$N$, $Length[N]$may cause overflow. Thus, if $Length[N] > 10^{18}$ , we can just set it to$10^{18}$since that's the maximum input value for$K$.