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

×

TSPAGAIN - Editorial

1
1

PROBLEM LINKS

Practice
Contest

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.

This question is marked "community wiki".

asked 28 Nov '12, 17:57

admin's gravatar image

0★admin ♦♦
15.9k347484508
accept rate: 35%

edited 28 Nov '12, 17:59

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×11,588
×812
×12
×1

question asked: 28 Nov '12, 17:57

question was seen: 1,853 times

last updated: 28 Nov '12, 17:59