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

×

Substring with least mod value - DP?

This is from IARCS Problem archive (DEVIOUS). Given a sequence of integers, how do you find the contiguous substring with the absolute value of the sum of its numbers being minimum? Is it even DP? How do you relate it to smaller subproblems?

asked 04 Jan '15, 19:14

vikramnitin9's gravatar image

2★vikramnitin9
1313
accept rate: 0%

Iterate from left to right and store the max possible sum if you include that particular integer.

(04 Jan '15, 23:33) Organic-Shilling0★

Thanks, but I don't think that applies here.
Greatest subsequence can be solved using standard DP as in the link. There, we have two cases - either we continue the sequence or we start a new one, depending on which is optimal.
But the same method fails here, because of the 'mod' value or absolute value.
Knowing the 'max possible sum if you include an integer' is of no use.
Example: 100, 20,-30,10
If you go with max possible sum until the 3rd element, then that is 100+20-30=90.
But the optimum would be 20-30+10=0, which is not related to the previous element.

link

answered 05 Jan '15, 18:53

vikramnitin9's gravatar image

2★vikramnitin9
1313
accept rate: 0%

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:

×931
×149
×109
×35
×3
×2
×2
×2

question asked: 04 Jan '15, 19:14

question was seen: 784 times

last updated: 05 Jan '15, 18:58