## Editorial for UTS Open '15 #3 - Pogo

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.**Just output .

This one's tricky:

Base cases are all except that . The answer to the problem is .

A diagram would be useful here but I am too lazy to draw one, so I will describe in words what each function represents:

- is the number of ways to satisfy the conditions if you're at the beginning of a line of length , with every tile behind you already visited.
- is similar, but exactly one tile right behind you is unvisited.
- is similar, but exactly two tiles right behind you are unvisited.
- is similar, but in addition to those two tiles, there might be another group of two tiles behind them, and another two, and another two, etc. Also, there might be a group of one tile at the end of that whole chain.
- is similar to , but you can choose whether to start at the first tile or the second.

Complexity:

## Comments