You are not logged in. Please login at www.codechef.com to post your questions!

×

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.

This question is marked "community wiki".

asked 28 Nov '12, 17:57 19.8k350498541
accept rate: 36%

 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,359
×12
×1

question asked: 28 Nov '12, 17:57

question was seen: 2,139 times

last updated: 28 Nov '12, 17:59