PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
If a trip from i to j is taxed, so is a trip from i-1 to j+1, i - 1 to j, and i to j + 1. We can use this to show that g[i][j] + g[i+1][j+1] <= g[i+1][j] + g[i][j+1]. Thus, the cost matrix is Monge.
A monge array can be shown to satisfy the Demidenko conditions. These conditions are necessary and sufficient conditions that a cost matrix should satisfy in order that the optimal tour be bitonic (first
increasing and then decreasing) For example an optimal tour can be something like : 1 3 4 5 9 8 7 6 2 1.
This allows a DP solution, with state (i,j) which is the value of the optimal tour passing through all nodes between indices i to j. (Treat the optimal tour as two paths, one from 0 to n - 1, and the other from
n - 1 to 0, having no vertices except 0 and n - 1 in common). Time complexity : O(n^2 + K)
There is also an O(n) solution to the problem too, once the g matrix is known. Each entry of the g matrix can be computed in O(log ^2 K) time using a data structure such as a segment tree. This leads to an
O(n log ^2 K + K) solution.