CodeChef: Practical coding for everyone is the same as third problem from
http://neerc.ifmo.ru/school/archive/2015-2016/ru-olymp-regional-2016-day1.pdf
2 Likes
In case anyone wants the English version:
"Consider the string s , consisting of lowercase letters of the Latin alphabet. Example
such a string is, for example, the string “abba”.
A substring of the string s is a string composed of one or more
consecutive characters in string s . Denote by W ( s ) a set consisting of all
possible substrings of the string s . Moreover, each substring is in this set no more than
once, even if it appears on the string s several times.
For example, W (“abba”) = {“a”, “b”, “ab”, “ba”, “bb”, “abb”, “bba”, “abba”}.
A subsequence of string s is a string that can be obtained from s
deleting an arbitrary number of characters. Denote by Y ( s ) a set consisting of
all possible subsequences of the string s . Similar to W ( s ), each
the subsequence of the string s is included in Y ( s ) exactly once, even if it can
be obtained in several ways to remove characters from the string s . Since any
the substring of the string s is also its subsequence, then the set Y ( s ) includes
W (s), but may also contain other strings.
For example, Y (“abba”) = W (“abba”) ∪ {“aa”, “aba”}. ∪ means
union of sets.
We will call the string s strange if for it W ( s ) = Y ( s ). So, the string “abba” is not
is strange, and, for example, the string “abb” is, since for it W (“abb”) =
Y (“abb”) = {“a”, “b”, “ab”, “bb”, “abb”}.
We will call the strangeness of a string the number of its various strange substrings. With
calculating the strangeness of a substring is counted once, even if it occurs in the string s in
as a substring several times. So, for the string “abba” its oddity is equal to 7, any of its
A substring other than the entire string is odd.
It is required to write a program that, by a given string s, determines its
weirdness. "
(Translated using Google Translate)
Hi dalgerok,
This is unfortunate. Thanks for reporting it. We will investigate it.