Editorial for COCI '08 Contest 1 #5 Skakavac


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Suppose first that the grasshopper can jump to any flower in the neighbouring rows and columns.

We can use dynamic programming to solve the problem. First sort the flowers by numbers of petals. For each flower F, we calculate best(F), the largest number of flowers the grasshopper can visit if it starts at flower F. We calculate this by considering all flowers G in the neighbouring rows and columns; then best(F) = \max\{best(G)\} + 1.

To calculate best(F) more quickly, we can keep track of the largest best(G) value for each row and column.

If we reintroduce the restriction from the problem statement on which flowers the grasshopper can jump to, this last improvement no longer works, since the grasshopper may not be allowed to jump to the best flower in a row or column. However, keeping track of the four best flowers in a row or column will do because at most three flowers in a row or column are forbidden.


Comments

There are no comments at the moment.