F: Base-2 Palindromes

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

• The key observation in this problem is that a palindrome is uniquely defined by the first half bits. Thus, the number of palindromes of length $n$ ($n>=2$) with the first bit $1$ is $2^{\lceil\frac{n-2}{2}\rceil}$.

• We can figure out the most significant bit of the $m^{th}$ palindrome by counting the number of palindromes of each length until the total number of palindromes we have counted so far exceeds $m$.

• Suppose the most significant bit of the $m^{th}$ palindrome is the $b^{th}$ bit, and suppose there are $k$ palindromes of length at most $b-1$. Then, we are interested in the $m' = (m-k)^{th}$​palindrome of length $b$ .

• Let $s$ denote the binary representation of $m-k-1$. Let $s_{rev}$ denote the string $s$ reversed. Now, we know that the answer is $1ss_{rev}1$ (expect if $b$ is odd, in which case we remove one bit from $s_{rev}$​).

  • For instance, suppose $s=0101$. If $b$ is even, the answer is $1010110101$. If b is odd, the answer is $101010101$.

• Finally, convert the binary string to an integer.