Editorial for Baltic OI '08 P3 - Magical Stones - Olympiads Online Judge

Editorial for Baltic OI '08 P3 - Magical Stones

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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

letters I and X are next to each other at at most $k$ $k$ positions,
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}$ $i^{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}$ $m^{th}$ step of the algorithm (starting from $m = 0$ $m = 0$ ), knowing a prefix $a_1 \dots a_m$ $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$ $a_{1} \dots a_{m}$ I; if $i$ $i$ is not greater than this number then — thanks to the lexicographical ordering of correct words — the $(m+1)^\text{st}$ $(m + 1)^{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)$ $σ (a_{1} \dots a_{m})$ denotes the number of correct words that start with the prefix $a_1 \dots a_m$ $a_{1} \dots a_{m}$ .

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

Copy

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)$ $i > σ (ϵ)$ . In such case, the final value of prefix in the above algorithm will be XXX...X and $j$ $j$ will be greater than $1$ $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)$ $i > σ (ϵ)$ .

How to Compute Values of $\sigma$ $σ$

Firstly let us introduce one more notation: $\sigma(a_1 \dots a_m, b_l \dots b_1)$ $σ (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$ $a_{1} \dots a_{m}$ and end with the suffix $b_l \dots b_1$ $b_{l} \dots b_{1}$ . If $m+l > n$ $m + l > n$ then the prefix and suffix overlap. Each correct word that starts with the prefix $a_1 \dots a_m$ $a_{1} \dots a_{m}$ is of exactly one of the following forms:

$l$ $l$ final letters of the word (where $0 \le l < m$ $0 \leq l < m$ ) read backwards are exactly the same as $l$ $l$ starting letters of the word, I is the $(l+1)^\text{st}$ $(l + 1)^{st}$ letter from the beginning of the word and X is the $(l+1)^\text{st}$ $(l + 1)^{st}$ letter from the end of the word.
$m$ $m$ final letters of the word read backwards are the same as $m$ $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)$ $σ (a_{1} \dots a_{m}) = \sum_{l = 0}^{m - 1} ([a_{l + 1} = I] \cdot σ (a_{1} \dots a_{m}, X a_{l} \dots a_{1})) + σ (a_{1} \dots a_{m}, a_{m} \dots a_{1}) (1)$

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

We now need to show how to compute the summands from the above equation. Note that we can assume that $a_m =$ $a_{m} =$ I, as the pseudocode only needs to know the value of $\sigma(prefix \mathtt I)$ $σ (p r e f i x I)$ . Let us assume that there are exactly $k_m$ $k_{m}$ letter changes in the word $a_1 \dots a_m$ $a_{1} \dots a_{m}$ and $k_l$ $k_{l}$ letter changes in the word X $a_l \dots a_1$ $a_{l} \dots a_{1}$ .

Lemma 1. If $2m \le n$ $2 m \leq n$ (this simply implies that prefix $a_1 \dots a_m$ $a_{1} \dots a_{m}$ and suffix $a_m \dots a_1$ $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}$ $σ (a_{1} \dots a_{m}, a_{m} \dots a_{1}) = \frac{1}{2} \sum_{i = 0}^{⌊ (k - 2 k_{m}) / 2 ⌋} (\binom{n - 2 m + 1}{2 i}) + \frac{1}{2} \sum_{i = 0}^{⌊ (k - 2 k_{m}) / 2 ⌋} (\binom{⌊ (n - 2 m + 1) / 2 ⌋}{i})$

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

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

This holds, because there are $n-2m$ $n - 2 m$ free positions in the middle of the word, so a letter change could take place at any of the $n-2m+1$ $n - 2 m + 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$ $k - 2 k_{m}$ and even, as the middle part of the word is bounded by a letter $a_m$ $a_{m}$ . This explains why the formula contains a sum over $\{0, \dots, \lfloor (k-2k_m)/2 \rfloor\}$ ${0, \dots, ⌊ (k - 2 k_{m}) / 2 ⌋}$ .

The number of palindromic words of the form $a_1 \dots a_m \dots a_m \dots a_1$ $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}$ $S_{p} = \sum_{i = 0}^{⌊ (k - 2 k_{m}) / 2 ⌋} (\binom{⌊ (n - 2 m + 1) / 2 ⌋}{i})$

This formula holds for even $n$ $n$ , because one half of the word can be filled arbitrarily using no more than $\lfloor (k-2k_m)/2 \rfloor$ $⌊ (k - 2 k_{m}) / 2 ⌋$ letter changes. The remaining part of the word is uniquely determined and contains the same number of letter changes. If $n$ $n$ is odd, the leading $\lfloor n/2 \rfloor$ $⌊ n / 2 ⌋$ letters define $\lfloor n/2 \rfloor$ $⌊ n / 2 ⌋$ 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$ $a_{1} \dots a_{m} \dots a_{m} \dots a_{1}$ that satisfy condition 1 and are not palindromes is $S-S_p$ $S - S_{p}$ . Exactly one half of such words are correct, as if we reverse a correct word $w$ $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$ $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$ $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$ $\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$ $m + l + 1 \leq n$ and $a_{l+1} =$ $a_{l + 1} =$ I, $a_m =$ $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}$ $σ (a_{1} \dots a_{m}, X a_{l} \dots a_{1}) = \sum_{i = 0}^{⌊ (k - k_{m} - k_{l} - 1) / 2 ⌋} (\binom{n - m - l}{2 i + 1})$

Proof: Here we can choose letter changes from $n-m-l$ $n - m - l$ positions, knowing that the total number of letter changes is odd (because $a_m =$ $a_{m} =$ I $\ne$ $\neq$ X) and not greater than $k-k_m-k_l$ $k - k_{m} - k_{l}$ . Notice that the condition $a_{l+1} =$ $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$ $a_{1} \dots a_{m} \dots 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$ $2 m > n$ or $m+l+1 > n$ $m + l + 1 > n$ ) then the number of correct words with the desired prefix and suffix is equal to $0$ $0$ or $1$ $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)$ $O (n)$ times (line 4). Every such computation is done using Formula (1) and requires $\mathcal O(n)$ $O (n)$ computations of values of $\sigma(prefix, suffix)$ $σ (p r e f i x, s u f f i x)$ . Finally every such value can be computed using Lemma 1, Lemma 2 or direct computation if $prefix$ $p r e f i x$ and $suffix$ $s u f f i x$ overlap — each of these requires $\mathcal O(n)$ $O (n)$ operations, provided that all values of binomial coefficients $\binom a b$ $(\binom{a}{b})$ for $0 \le a, b \le n$ $0 \leq a, b \leq n$ are precomputed. This preprocessing can be done in $\mathcal O(n^2)$ $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$ $(\binom{a}{b}) = (\binom{a - 1}{b - 1}) + (\binom{a - 1}{b}) for a > b > 0$

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

Comments

There are no comments at the moment.