Hi, this is my first blog tutorial. I'll be talking about an alternative solution for 1421 D. Hexagons using total unimodularity using Linear programming and Total unimodularity.

Introduction

(Skip if familiar with Linear programming)

So what is linear programming? Linear programming aims to answer the following question:

Problem: Given real (double numbers) $$$c_1, ..., c_n$$$ and $$$b_1, ..., b_m$$$, and a matrix $$$A$$$ of size $$$m\times n$$$, you want to find $$$x_1, ..., x_n \geq 0$$$ that maximize $$$\sum_{i=1}^n c_i x_i$$$ subject to the constraints $$$\sum_{i=1}^n A_{i,j}x_i \leq b_j$$$ for all $$$j=1, ..., m$$$.

Let's take an example. Suppose $$$c=(1,2), b=(2,3),$$$ and

then we want to find $$$ x_1, x_2 \geq 0 $$$ that maximize $$$x_1+2x_2$$$ subject to $$$x_1+3x_2 \leq 2$$$ and $$$3x_1+4x_2 \leq 3$$$. In this case, one can verify graphically (by plotting objective function and the constraints) that the maximum is at $$$(x_1, x_2)=(0.2, 0.6)$$$ with value $$$0.2 + 2\times 0.6 = 1.4$$$.

For any linear program, there are three possibilities. The first is that there is an optimal solution like the example above. The second is that there is an unbounded solution (for example maximize $$$x+y$$$ subject to $$$y\leq 2$$$, since $$$x$$$ can be made arbitrarily large), and finally, there could be no solution at all! For example, maximize $$$x+y$$$ subject to $$$x\leq 5$$$ and $$$-x \leq -6$$$.

Great, now are we able to solve linear programming in polynomial time? It turns out that the answer is Yes! In $$$1972$$$, the researcher Leonid Khachiyan came up with an algorithm called the "Ellipsoid algorithm" that can solve any LP in polynomial time. However, unfortunately in practice, the algorithm suffers from major numerical instabilities so it is not very useful in a competitive programming setting (but very interesting from a theory prespective).

There is another algorithm called the Simplex algorithm than in practice is extremely fast (the observed number of steps in practice is roughly linear to $$$m$$$ and $$$n$$$), but has a worst case exponential runtime! It made researchers very confused for a long time why the Simplex algorithm did so well in practice vs its worst case, when finally in 2004, Spielman and Teng (2 theoretical CS researchers) showed that indeed the Simplex algorithm takes polynomial time under smoothed analysis.

What can you get out of all of this? Well, we have a "in-practice" fast algorithm (Simplex algorithm) that can solve very large linear programs in near linear time.

Here is an implementation from Stanford ICPC notebook for the C++ implementation of the Simplex algorithm:

Total Unimodularity

Sometimes when the stars align and god is happy, the linear programming solver will return a solution $$$x_i$$$ that is integral! This means that all the variables are integers, not fractional!

One such case happens when the matrix $$$A$$$ is totally unimodular. Now there are many examples of totally unimodular matrices, for example the network flow constraint matrix or adjacency matrix of a bipartite graph, etc. See wikipedia article above.

To verify that a matrix $$$A$$$ is indeed totally unimodular, you have to verify that every $$$2\times 2$$$ submatrix has determinant $$$0, -1$$$ or $$$1$$$.

Back to D. Hexagons

First, let's model the problem as a linear program. Let's say in our path we will take $$$x_1, x_2, x_3, x_4, x_5, x_6 \geq 0$$$ moves according to each directions (in the problem). Then our cost would be $$$\sum_{i=1}^6 c_ix_i$$$. However, we want that in the end, our coordinates is $$$x, y$$$. So we add two constraints as follows: $$$x_1-x_3-x_4+x_6 = x$$$ and $$$x_1+x_2-x_4-x_5=y$$$ so that the coordinates are $$$(x,y)$$$ in the end. So we get the linear program of maximizing $$$\sum_{i=1}^6 c_ix_i$$$ subject to the constraint matrix:

We can replace each equality $$$f=g$$$ with $$$f\leq g$$$ and $$$-f \leq -g$$$. So we get the system:

Now let's check if the constraint matrix is indeed totally unimodular:

bool is_unimodular(vector<vector<int>>& A){
  for(int i=0; i<A.size(); ++i){
    for(int j=i+1; j<A.size(); ++j){
      for(int k=0; k<A[0].size(); ++k){
        for(int l=k+1; l<A[0].size(); ++l){
          int det = A[i][k]*A[j][l] - A[i][l]*A[j][k];
          if (det!=0 and det!=1 and det!=-1)return false;
        }
      }
    }
  }
  return true;
}
int main() {
  vector<vector<int>> M {
    	{1,0,-1,-1,0,1},
    	{1,1,0,-1,-1,0},
    	{-1,0,1,1,0,-1},
    	{-1,-1,0,1,1,0}
  };
  cout << is_unimodular(M);
}

And it turns out that yes, the matrix is totally unimodular! Therefore, if we solve the linear program, we will get integral values for $$$x_i$$$, which is exactly what we want!

Implementation

Here is the code. The only difference here is that instead of maximizing $$$\sum_{i=1}^6 c_ix_i$$$, we are minimizing it. But the minimum is just negative the maximum of $$$\sum_{i=1}^6 -c_ix_i$$$.