Editorial for WC '15 Finals S1 - Fuzzbiz
Submitting an official solution before solving the problem yourself is a bannable offence.
Let be
if
is a valid number at which the given sequence of
words could've started at (in other words, if
could've been the
-th last number in the game), and
otherwise. For a given
, we can determine the value of
in
time with simulation by testing if, for each
from
to
, the
-th words are the correct words for number
.
The simulation is very similar to naively searching through a string, where all rounds of the game form a "haystack" to be searched through and the
words is the "needle" of which we must count occurrences.
To test all possible starting indices, the overall running time is
since
is significantly larger than
. However, this will not pass since
is as big as
. Even using faster string searching algorithms such as the KMP or Aho-Corasick algorithms will not pass, as their time complexities all depend on
.
To get full marks, we will have to eliminate the bottleneck of generating the words of all rounds of the game. The trick is to notice that in a perfect game of FizzBuzzOok, the sequence of words repeats after every
terms. This also means that
repeats every
terms – that is, if the sequence could have started at number
, it could have also started at number
(for any non-negative integer
). Therefore, we only need to compute
using the above approach (in a total of
time), and can then observe that
,
, and so on.
To compute the answer, then, we should consider each value of between
and
for which
, and count the number of non-negative integers
such that
(which is the largest number that could've been the first word in the given sequence). Using some algebra to rearrange this inequality, we get
, which ultimately implies that
.
Assuming the left-hand side formula is non-negative, then the number of possible non-negative integers is equal to the expression rounded down, plus
to account for
being a valid value of
. If it happens that the left-hand side expression is negative, then we should report
as the answer. These two cases can be merged into the expressions
. A solution which implements this idea has a running time of
.
Comments