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

×

number of increasing strings of length k

I am finding it hard that how to find the number of increasing sequences of length k in n numbers. I know it has use of LIS problem and i have to modify it somehow, but now getting how. it's complexity is O(k*n^2) DP solution. Please give hint and explain me a little bit.

asked 12 Oct '12, 21:06

hellodear's gravatar image

3★hellodear
14224
accept rate: 0%


My hint is:

number of inc. seq. of length k in n elements = ( number of inc. seq. of length k - 1 in n - 1 elements ) + ( number of inc. seq. of length k in n - 1 elements )

You simply use or skip first element. Additionally you need to remember last chosen number (you need to select bigger next time) and it makes O(k*n*n) when you normalize elements in sequence to range [0,n).

link

answered 12 Oct '12, 21:34

betlista's gravatar image

3★betlista ♦♦
16.9k49115225
accept rate: 11%

Can u write that DP[i] ? that when i have calculated the LIS array, then next what i need to change in that ?

(12 Oct '12, 21:54) hellodear3★

You can look through this link and link . Basically the link provides you with pseudo code for @betlista's idea.

number of inc. seq. of length k in n elements = ( number of inc. seq. of length k - 1 in n - 1 elements ) + ( number of inc. seq. of length k in n - 1 elements )
link

answered 14 Oct '13, 16:20

tusharmakkar08's gravatar image

3★tusharmakkar08
449138
accept rate: 0%

-3

It is very effective codechef with the information of world wide. It is well written and effective also it is very informative about on There are [url=http://www.artoyster.com/]Oil paintings for sale[/url] on the market all right where you are and all all over the globe. If you cannot discover a supplier that you like or believe in, make time to look on the internet for one and you may be amazed. Usually on the internet traders and performers are able to provide you costs that are less and excellent that is fantastic.

link

answered 13 Oct '12, 22:53

paintinforsale's gravatar image

0★paintinforsale
-5
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:

×2,167

question asked: 12 Oct '12, 21:06

question was seen: 5,866 times

last updated: 14 Oct '13, 16:20