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