Editorial for COCI '16 Contest 3 #2 Pohlepko


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.

The solution that was good enough for 50\% of points works under the assumption that a field's right and down neighbours are different. This way, we can start from the initial field and in each step compare the neighbours - we will always move the token to a field that is alphabetically smaller.

The problem arises when both neighbours are the same. This problem can be solved by keeping track of, in each step, a list of all optimal positions in which we could have ended up after a certain amount of steps. We start with the list containing the initial field (0, 0) and in each step update the list so that we first check the minimal value of the neighbours of all positions in the current list, and then create a new list that will contain all neighbouring positions with that value. Since we can reach a field in 2 ways, we must be careful not to add the same position twice to the list, because this way we would copy the number of appearances of the same position in each iteration.


Comments

There are no comments at the moment.