Editorial for COCI '09 Contest 6 #6 Gremlini
Submitting an official solution before solving the problem yourself is a bannable offence.
Let be the number of years until the birth of the first type
gremlin with
ancestors. Since there is one of each type of gremlins born in the accident we can set
, for each
.
Examine one type gremlin with
ancestors. After
years he spawns one type
egg, that needs
years to hatch. That egg has
ancestors. So we now know that
is less than or equal to
. Obviously, finding the minimum of all such values for all gremlins that hatch type
eggs we obtain
. We can observe all types at once by using matrix algebra. We have:
Where is a rectangular matrix with
row and
column equal to
if type
gremlin hatches type
egg, or
if not. Matrices
and
are self explanatory, and
marks min-plus matrix multiplication.
Matrix can be raised to arbitrary power fast using binary exponentiation. After multiplying
to the power of
and performing min-plus with
we scan the obtained
matrix. If each number is larger than
, there are no gremlins with
ancestors. Otherwise, there is at least one. Using binary search on
we find the largest possible
.
Comments