Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Problem Statement -

Problem Statement

The task is to find the most profitable contiguous segment of tests, given a sequence of test scores, with being allowed to drop any k tests from a chosen range.

The problem appears to be a DP problem at the outset, but complexity arises when the test drop condition comes into the picture.

What modifications can be made to the classic DP approach for this problem? Or is there a completely different approach to it?

Test Range - N <= 104

Source - INOI 2011 Q Paper

share|improve this question
    
Where did this problem appear? –  Caleb Dec 24 '12 at 20:44
    
Source - INOI 2011 Q Paper –  7Aces Dec 24 '12 at 21:55
    
In this problem K <= 100, so you can try coming up with a O(NK) algorithm –  A.06 Jan 22 at 4:13
add comment

2 Answers

The original algorithm is basically:

for each position:
    calculate best range ending at this position
print best over all possible ending positions

The best possible range ending at a position is the maximum of:

  • 0 (starting from scratch here)
  • the best possible range of the previous position + new mark

Now, we need to calculate K endings, for different amount of dropped tests

for each position:
    for k = 0 to K:
        calculate best possible range ending at this position and dropping at most k tests
print best of all calculated ranges

The best possible range ending is the maximum of:

  • 0 (starting a new range at this position)
  • the best possible range of the previous position + new mark
  • the best possible range of the previous position and one less dropped test
share|improve this answer
add comment

Well, here how I would do it (without getting in too much detail)

I would keep track of the value of the all the results I dropped. I would probably put them in a sorted queue whose size is the allowed number of dropped test. It would sorted such as the dropped test the nearest to zero is at the start. As I go trough the list with the traditional algorithm, I would do the following :

if I encounter a negative number
    if the queue is not full
        add it to the queue
    else
        if the new negative number is smaller (farther from zero) than the first number in the queue
            remove the first number from the queue
            add the new number to the queue
            add the removed number to the current subsequence value
        else
            add the new negative number to the current subsequence value

That way, you always keep the subsequence without the worst mark of the sequence, and if you encounter an even worst mark, you can restore the value of a previously dropped mark to the value of your subsequence.

share|improve this answer
    
Your approach is really good, but has a few flaws. Building on your approach... –  7Aces Dec 25 '12 at 19:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.