Looking for a dynamic programming solution

Posted by krammer on Programmers See other posts from Programmers or by krammer
Published on 2012-09-30T13:11:16Z Indexed on 2012/09/30 15:48 UTC
Read the original article Hit count: 188

Filed under:

algorithms

|

dynamic-programming

Given a sequence of integers in range 1 to n. Each number can appear at most once. Let there be a symbol X in the sequence which means remove the minimum element from the list. There can be an arbitrarily number of X in the sequence. Example: 1,3,4,X,5,2,X The output is 1,2.

We need to find the best way to perform this operation.

The solution I have been thinking is:

Scan the sequence from left to right and count number of X which takes O(n) time. Perform partial sorting and find the k smallest elements (k = number of X) which takes O(n+klogk) time using median of medians.

Is there a better way to solve this problem using dynamic programming or any other way ?

© Programmers or respective owner

Related posts about algorithms

Finding a problem in some task [closed]

as seen on Programmers - Search for 'Programmers'
Recently I competed in nation wide programming contest finals. Not unexpectedly all problems were algorithmic. I lost (40 points out of 600. Winner got ~300). I know why I lost very well - I don't know how to find actual problem in those obfuscated tasks which are life-blood of every competition.… >>> More
Genetic algorithms

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm trying to implement a genetic algorithm that will calculate the minimum of the Rastrigin functon and I'm having some issues. I need to represent the chromosome as a binary string and as the Rastrigin's function takes a list of numbers as a parameter, how can decode the chromosome to a list of… >>> More
understanding evaluation function

as seen on Programmers - Search for 'Programmers'
I am developing a chess program. And have made use of an alpha beta algorithm and a static evaluation function. I have successfully implemented both but I want to improve the evaluation function by automatically tuning the weights assigned to its features. At this point am totally confused about the… >>> More
How to know whether to create a general system or to hack a solution

as seen on Programmers - Search for 'Programmers'
I'm new to coding , learning it since last year actually. One of my worst habits is the following: Often I'm trying to create a solution that is too big , too complex and doesn't achieve what needs to be achieved, when a hacky kludge can make the fit. One last example was the following (see paste… >>> More
How to implement a genetic algorithm with distance, time, and cost

as seen on Programmers - Search for 'Programmers'
I want to make a solution to find the optimum route of school visit. For example, I want to visit 5 schools (A, B, C, D, E) in my city. Then I must find out what school I should visit first, then the second, then the third etc. with distance, time, and cost criteria. The problem is, I am confused… >>> More

Related posts about dynamic-programming

dynamic programming [closed]

as seen on Stack Overflow - Search for 'Stack Overflow'
the input to this problem is a sequence S of integers(not necessarily positive). the problem is to find consecutive subsequence of S with maximum sum using dynamic programming. consecutive means that you are not allowed to skip numbers. for example: if the input was 12,-14,1,23,-6,22,-34,-13. the… >>> More
Dynamic Programming Recursion and a sprinkle of Memoization

as seen on Stack Overflow - Search for 'Stack Overflow'
I have this massive array of ints from 0-4 in this triangle. I am trying to learn dynamic programming with Ruby and would like some assistance in calculating the number of paths in the triangle that meet three criterion: You must start at one of the zero points in the row with 70 elements. Your… >>> More
Need help with dynamic programming problem

as seen on Stack Overflow - Search for 'Stack Overflow'
I have the following problem : I am given a tree with N apples, for each apple I am given it's weight and height,I can pick apples up to a given height H,each time I pick an apple the height of every apple is increased with U(also given).I have to find out the maximum weight of apples I can pick.… >>> More
Algorithm and data structure learning resources for dynamic programming

as seen on Stack Overflow - Search for 'Stack Overflow'
Im learning dynamic programming now, and while I know the theory well, designing DP algorithms for new problems is still difficult. This is what i would really like now- A book or a website, which poses a problem which can be solved by dynamic programming. Also there is the solution with an explanation… >>> More
How to speed up calculation of length of longest common substring?

as seen on Stack Overflow - Search for 'Stack Overflow'
I have two very large strings and I am trying to find out their Longest Common Substring. One way is using suffix trees (supposed to have a very good complexity, though a complex implementation), and the another is the dynamic programming method (both are mentioned on the Wikipedia page linked above)… >>> More