Editorial for Baltic OI '08 P3 - Magical Stones
Submitting an official solution before solving the problem yourself is a bannable offence.
The task is, described alternatively, to find the word in the lexicographical order, of length
, composed of letters
I
and X
, satisfying two conditions:
- letters
I
andX
are next to each other at at mostpositions,
- 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 word one by one, from left to right. We start with an empty prefix of the word, which we will call
. In the
step of the algorithm (starting from
), knowing a prefix
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
I
; if is not greater than this number then — thanks to the lexicographical ordering of correct words — the
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: denotes the number of correct words that start with the prefix
.
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 . In such case, the final value of prefix in the above algorithm will be
XXX...X
and will be greater than
. However, we notice that it is sufficient to check the latter condition, because it can be satisfied if and only if
.
How to Compute Values of 
Firstly let us introduce one more notation: denotes the number of correct words that start with the prefix
and end with the suffix
. If
then the prefix and suffix overlap. Each correct word that starts with the prefix
is of exactly one of the following forms:
final letters of the word (where
) read backwards are exactly the same as
starting letters of the word,
I
is theletter from the beginning of the word and
X
is theletter from the end of the word.
final letters of the word read backwards are the same as
starting letters of the word (read from left to right). This leads directly to the following formula:
where is equal to
if
I
and otherwise. In general, expression
, where
is a logical statement, has a value of
if the
is true and
otherwise.
We now need to show how to compute the summands from the above equation. Note that we can assume that
I
, as the pseudocode only needs to know the value of . Let us assume that there are exactly
letter changes in the word
and
letter changes in the word
X
.
Lemma 1. If (this simply implies that prefix
and suffix
do not overlap) then:
Proof: The total number of words of the form over the alphabet
that satisfy condition 1 (i.e. contain at most
letter changes) equals:
This holds, because there are free positions in the middle of the word, so a letter change could take place at any of the
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
and even, as the middle part of the word is bounded by a letter
. This explains why the formula contains a sum over
.
The number of palindromic words of the form that satisfy condition 1 is:
This formula holds for even , because one half of the word can be filled arbitrarily using no more than
letter changes. The remaining part of the word is uniquely determined and contains the same number of letter changes. If
is odd, the leading
letters define
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 that satisfy condition 1 and are not palindromes is
. Exactly one half of such words are correct, as if we reverse a correct word
it becomes incorrect and non-palindromic. On the other hand, all palindromic words of the form
are correct. This gives us the following formula for the total number of correct words of the form
:
which is equivalent to the formula from Lemma 1. ■
Lemma 2. If and
I
,
I
then:
Proof: Here we can choose letter changes from positions, knowing that the total number of letter changes is odd (because
I
X
) and not greater than . Notice that the condition
I
already implies that every possible choice of middle letters of the word 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 ( or
) then the number of correct words with the desired prefix and suffix is equal to
or
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
function.
Time Complexity
Let us analyse the time complexity of the whole algorithm. In the pseudocode, values of the function are computed
times (line 4). Every such computation is done using Formula (1) and requires
computations of values of
. Finally every such value can be computed using Lemma 1, Lemma 2 or direct computation if
and
overlap — each of these requires
operations, provided that all values of binomial coefficients
for
are precomputed. This preprocessing can be done in
time complexity with a well-known formula:
and simple formulas for border cases like , or
, or
. The total time complexity is therefore
. The upper limit for
in our task is equal to
, so this solution is fast enough to receive perfect score.
Comments