The task is, described alternatively, to find the ~i^\text{th}~ word in the lexicographical order, of length ~n~, composed of letters I and X, satisfying two conditions:

1. letters I and X are next to each other at at most ~k~ positions,
2. the word read backwards is not lexicographically less than the original word.

From now on, we will call each word satisfying the above conditions a correct word. Every two neighbouring positions of a word which contain different letters are called a letter change.

We will find the letters of the ~i^\text{th}~ word one by one, from left to right. We start with an empty prefix of the word, which we will call ~\epsilon~. In the ~m^\text{th}~ step of the algorithm (starting from ~m = 0~), knowing a prefix ~a_1 \dots a_m~ of the requested word, our task is to find its next letter. In order to perform this operation, we compute the number of correct words that start with the prefix ~a_1 \dots a_m~I; if ~i~ is not greater than this number then — thanks to the lexicographical ordering of correct words — the ~(m+1)^\text{st}~ letter of the requested word is I. Otherwise, it is X.

To help us precisely formulate the described idea of the solution, let us introduce the following notation: ~\sigma(a_1 \dots a_m)~ denotes the number of correct words that start with the prefix ~a_1 \dots a_m~.

With those notations, model solution can described by the following simple pseudocode:

prefix := ε;
j := i;
for m := 0 to n-1 do
  if j <= σ(prefix + I) then
    prefix := prefix + I;
  else
    prefix := prefix + X;
    j := j - σ(prefix + I);
if j > 1 then
  return NO SUCH STONE;
else
  return prefix;

The case when the correct result is NO SUCH STONE requires some explanation. This happens only if ~i > \sigma(\epsilon)~. In such case, the final value of prefix in the above algorithm will be XXX...X and ~j~ will be greater than ~1~. However, we notice that it is sufficient to check the latter condition, because it can be satisfied if and only if ~i > \sigma(\epsilon)~.

How to Compute Values of ~\sigma~

Firstly let us introduce one more notation: ~\sigma(a_1 \dots a_m, b_l \dots b_1)~ denotes the number of correct words that start with the prefix ~a_1 \dots a_m~ and end with the suffix ~b_l \dots b_1~. If ~m+l > n~ then the prefix and suffix overlap. Each correct word that starts with the prefix ~a_1 \dots a_m~ is of exactly one of the following forms:

• ~l~ final letters of the word (where ~0 \le l < m~) read backwards are exactly the same as ~l~ starting letters of the word, I is the ~(l+1)^\text{st}~ letter from the beginning of the word and X is the ~(l+1)^\text{st}~ letter from the end of the word.
• ~m~ final letters of the word read backwards are the same as ~m~ starting letters of the word (read from left to right). This leads directly to the following formula:

$$\displaystyle \sigma (a_1 \dots a_m) = \sum_{l=0}^{m-1} ([a_{l+1} = \mathtt I] \cdot \sigma(a_1 \dots a_m, \mathtt X a_l \dots a_1)) + \sigma(a_1 \dots a_m, a_m \dots a_1) \quad (1)$$

where ~[a_{l+1} = \mathtt I]~ is equal to ~1~ if ~a_{l+1} =~ I and ~0~ otherwise. In general, expression ~[condition]~, where ~condition~ is a logical statement, has a value of ~1~ if the ~condition~ is true and ~0~ otherwise.

We now need to show how to compute the summands from the above equation. Note that we can assume that ~a_m =~ I, as the pseudocode only needs to know the value of ~\sigma(prefix \mathtt I)~. Let us assume that there are exactly ~k_m~ letter changes in the word ~a_1 \dots a_m~ and ~k_l~ letter changes in the word X~a_l \dots a_1~.

Lemma 1. If ~2m \le n~ (this simply implies that prefix ~a_1 \dots a_m~ and suffix ~a_m \dots a_1~ do not overlap) then:

$$\displaystyle \sigma(a_1 \dots a_m, a_m \dots a_1) = \frac 1 2 \sum_{i=0}^{\lfloor (k-2k_m)/2 \rfloor} \binom{n-2m+1}{2i} + \frac 1 2 \sum_{i=0}^{\lfloor (k-2k_m)/2 \rfloor} \binom{\lfloor (n-2m+1)/2 \rfloor}{i}$$

Proof: The total number of words of the form ~a_1 \dots a_m \dots a_m \dots a_1~ over the alphabet ~\{\mathtt I, \mathtt X\}~ that satisfy condition 1 (i.e. contain at most ~k~ letter changes) equals:

$$\displaystyle S = \sum_{i=0}^{\lfloor (k-2k_m)/2 \rfloor} \binom{n-2m+1}{2i}$$

This holds, because there are ~n-2m~ free positions in the middle of the word, so a letter change could take place at any of the ~n-2m+1~ pairs of consecutive positions. This explains the binomial coefficients in the formula. We also know that the number of letter changes in the middle part of the word is not greater than ~k-2k_m~ and even, as the middle part of the word is bounded by a letter ~a_m~. This explains why the formula contains a sum over ~\{0, \dots, \lfloor (k-2k_m)/2 \rfloor\}~.

The number of palindromic words of the form ~a_1 \dots a_m \dots a_m \dots a_1~ that satisfy condition 1 is:

$$\displaystyle S_p = \sum_{i=0}^{\lfloor (k-2k_m)/2 \rfloor} \binom{\lfloor (n-2m+1)/2 \rfloor}{i}$$

This formula holds for even ~n~, because one half of the word can be filled arbitrarily using no more than ~\lfloor (k-2k_m)/2 \rfloor~ letter changes. The remaining part of the word is uniquely determined and contains the same number of letter changes. If ~n~ is odd, the leading ~\lfloor n/2 \rfloor~ letters define ~\lfloor n/2 \rfloor~ trailing letters, as well as the middle letter, as only one letter can be inserted in the middle of the word without adding new letter changes.

The number of words of the form ~a_1 \dots a_m \dots a_m \dots a_1~ that satisfy condition 1 and are not palindromes is ~S-S_p~. Exactly one half of such words are correct, as if we reverse a correct word ~w~ it becomes incorrect and non-palindromic. On the other hand, all palindromic words of the form ~a_1 \dots a_m \dots a_m \dots a_1~ are correct. This gives us the following formula for the total number of correct words of the form ~a_1 \dots a_m \dots a_m \dots a_1~:

$$\displaystyle \frac 1 2 (S-S_p) + S_p = \frac 1 2 S + \frac 1 2 S_p$$

which is equivalent to the formula from Lemma 1. ■

Lemma 2. If ~m+l+1 \le n~ and ~a_{l+1} =~ I, ~a_m =~ I then:

$$\displaystyle \sigma(a_1 \dots a_m, \mathtt X a_l \dots a_1) = \sum_{i=0}^{\lfloor (k-k_m-k_l-1)/2 \rfloor} \binom{n-m-l}{2i+1}$$

Proof: Here we can choose letter changes from ~n-m-l~ positions, knowing that the total number of letter changes is odd (because ~a_m =~ I ~\ne~ X) and not greater than ~k-k_m-k_l~. Notice that the condition ~a_{l+1} =~ I already implies that every possible choice of middle letters of the word ~a_1 \dots a_m \dots \mathtt X a_l \dots a_1~ leads to a correct word — this is the reason why the formula from Lemma 2 is much simpler than the previous one (from Lemma 1). ■

Finally, if the prefix and the suffix overlap (~2m > n~ or ~m+l+1 > n~) then the number of correct words with the desired prefix and suffix is equal to ~0~ or ~1~ and this number can be computed in a straightforward manner. This, together with formulas from Lemmas 1 and 2, concludes the algorithm for computing the values of the ~\sigma~ function.

Time Complexity

Let us analyse the time complexity of the whole algorithm. In the pseudocode, values of the ~\sigma~ function are computed ~\mathcal O(n)~ times (line 4). Every such computation is done using Formula (1) and requires ~\mathcal O(n)~ computations of values of ~\sigma(prefix, suffix)~. Finally every such value can be computed using Lemma 1, Lemma 2 or direct computation if ~prefix~ and ~suffix~ overlap — each of these requires ~\mathcal O(n)~ operations, provided that all values of binomial coefficients ~\binom a b~ for ~0 \le a, b \le n~ are precomputed. This preprocessing can be done in ~\mathcal O(n^2)~ time complexity with a well-known formula:

$$\displaystyle \binom a b = \binom{a-1}{b-1}+\binom{a-1}{b}\text{ for }a > b > 0$$

and simple formulas for border cases like ~a < b~, or ~a = b~, or ~b = 0~. The total time complexity is therefore ~\mathcal O(n \cdot n \cdot n) + \mathcal O(n^2) = \mathcal O(n^3)~. The upper limit for ~n~ in our task is equal to ~60~, so this solution is fast enough to receive perfect score.