First observe that you never need to move to the left. You can prove this by contradiction: if you assume there is an optimal path that needs to move to the left from some column \(x\) to column \(x-1\), you will later need to move right from column \(x-1\) to column \(x\), and there is no room to do so in \(3\) rows that won’t create a shorter path. You could more rigorously prove this via casework which we shall omit.

Given this, we can represent each segment of one or more columns by a \(3 \times 3\) matrix, where each element \(M_{i, j} \in \mathbb Z \cup \{ \infty \}\) and represents the cost of starting in the leftmost column in row \(i\) and ending in the rightmost column in row \(j\). We can combine two such matrices \(A \otimes B = C\) via \(C_{i, j} = \min _{k=1} ^3 A_{i, k} + B_{k, j} + 1\), representing moving from rows \(i\) to \(k\) in segment \(A\), stepping to the right to segment \(B\), then moving from rows \(k\) to \(j\). We could easily precalculate the matrices that represent a single column for each of the \(2^3\) possibilities, then use a segment tree to update the “product”, obtaining the required answer from \(M_{1, 3}\).

Optional discussion follows involving abstract algebra:

A semiring is an algebraic structure consisting of some set \(R\) and two binary operations \(\oplus\) (“addition”) and \(\otimes\) (“multiplication”) that satisfies the following axioms:

“Addition” is a monoid (i.e. a binary operation that is closed, associative, and has an identity element) over \(R\), and is also commutative. We call its identity element \(\theta\) (“zero”)

• \((a \oplus b) \oplus c = a \oplus (b \oplus c)\)
• \(\theta \oplus a = a \oplus \theta = a\)
• \(a \oplus b = b \oplus a\)

“Multiplication” is a monoid over \(R\) with an identity element \(\iota\) (“one”) [but need not be commutative]

• \((a \otimes b) \otimes c = a \otimes (b \otimes c)\)
• \(a \otimes \iota = \iota \otimes a = a\)

Anything “multiplied” by “zero”, either to the left or right, is “zero”

• \(\theta \otimes a = a \otimes \theta = \theta\)

“Multiplication” left- and right-distributes over “addition”:

• \(a \otimes (b \oplus c) = (a \otimes b) \oplus (a \otimes c)\)
• \((b \oplus c) \otimes a= (b \otimes a) \oplus (c \otimes a)\)

Note that the set \(R = \mathbb Z \cup \{ \infty \}\) forms a semiring if we define the operators as follows:

• \(a \oplus b = \min \{ a, b\},\, \theta = \infty\)
• \(a \otimes b = a + b + 1,\, \iota = -1\)

This is similar to what is known as the “tropical semiring” or “tropical algebra”, but with a slightly different \(\otimes\) operator and corresponding identity.

Furthermore, it can be proven that the set of square matrices of some size \(n\) over a semiring \(R\), denoted \(\mathcal M _ n (R)\), is also a semiring, where the concepts of matrix addition, multiplication, zero matrix, and identity matrix are all similar, except with the individual elements having their operators and identities replaced by the corresponding concepts in the semiring.

We can thus note that our special combining operator for two matrices representing segments is in fact multiplication over \(\mathcal M_3(R)\).

We can further note that the “identity matrix” is:

\[ \begin{bmatrix} \iota & \theta & \theta \\ \theta & \iota & \theta \\ \theta & \theta & \iota \end{bmatrix} = \begin{bmatrix} -1 & \infty & \infty \\ \infty & -1 & \infty \\ \infty & \infty & -1 \end{bmatrix} \]

which is thus the identity for the monoid required for the segment tree, which won’t be obvious otherwise. This isn’t strictly required for the problem however, as one can easily use a sentinel “null” value as an identity for a semigroup where the identity element is missing or unknown (similar to how \(\infty\) serves as an identity for \(\min\)); it’s just nice to know.