Editorial for Facebook Hacker Cup '19 Final Round P1 - Strings as a Service
Submitting an official solution before solving the problem yourself is a bannable offence.
We need to generate any string of length at most
If our string features a substring consisting of AAA
includes A
, AA
, and AAA
).
If we concatenate multiple such substrings together, then the total number of palindromes in the resulting string will be equal to the sum of palindrome counts within those substrings, plus any "additional palindromes" spanning multiple of the substrings. However, these additional palindromes can only exist if two substrings which are separated by at most one other substring feature the same letter. For example, additional palindromes exist in the concatenations AA
+ AA
and AA
+ BB
+ AA
, but not in the concatenation AA
+ BB
+ CC
+ AA
.
We'll attempt to build a valid string out of such a concatenation, maintaining control over the exact palindrome count by ensuring that there are no additional palindromes (for example, by cycling through at least
It may not be immediately obvious whether all values of
Two other simple approaches which require fewer letters (at most
Comments