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.

M = 1

Just output 1.

M = 2

\displaystyle f(n) = \begin{cases}0 & \text{if }n \le 0 \\ 1 & \text{if }n = 1 \\ f(n-1) + f(n-3) & \text{otherwise}\end{cases}

M = 3

This one's tricky:

\displaystyle \begin{align*}
A(n) &= A(n-1) + B(n-2) + C_1(n-3) \\
B(n) &= A(n-2) + C_2(n-3) + D(n-1) + D(n-3) \\
C_1(n) &= A(n-2) + C_2(n) \\
C_2(n) &= A(n-1) + A(n-2) + C_2(n-3) + D(n-1) + D(n-3) \\
D(n) &= A(n) + B(n-1)

Base cases are all 0 except that A(1) = 1. The answer to the problem is A(N).

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

  • A(N) is the number of ways to satisfy the conditions if you're at the beginning of a line of length N, with every tile behind you already visited.
  • B(N) is similar, but exactly one tile right behind you is unvisited.
  • C_1(N) is similar, but exactly two tiles right behind you are unvisited.
  • C_2(N) 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.
  • D(N) is similar to A(N), but you can choose whether to start at the first tile or the second.

Complexity: \mathcal O(N)


There are no comments at the moment.