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
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:
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)


Comments

There are no comments at the moment.