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

×

# number of increasing strings of length k

 0 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 14●2●2●4 accept rate: 0%

 1 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). answered 12 Oct '12, 21:34 16.9k●49●115●225 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)
 0 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 )  answered 14 Oct '13, 16:20 449●1●3●8 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. answered 13 Oct '12, 22:53 -5 accept rate: 0%
 toggle preview community wiki:
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