Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

http://community.topcoder.com/stat?c=problem_statement&pm=12329

I was practicing on TopCoder and found this problem. I solved it by noticing that it looks a little like the 0-1 knapsack, but I do not have even the smallest clue why this assumption was correct.

I will simplify the problem statement here:

Given a ordered list of cards, each with a level and a damage, you can make the following steps in order to maximize your damage (assuming the first card has level Li and damage Di):

  1. play the first card and add Di to the total damage made and then discard it and the next Li - 1 cards
  2. move the first card to the end of the list (so the second card becomes the first, the third becomes second, etc)

My question is: can you always play any cards you want as long as you don't have to discard more cards than they actually are? Can you reduce this to the 0-1 knapsack problem where you can choose any items to put in the backpack as long as you do not exceed the maximum weight?

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

We can use induction to show that any set of cards can be picked as long as their levels do not add up to more than the number of cards. This is clearly true when we pick only $1$ card. Suppose this is true for $m-1$ cards. Now, let the indices of the $m$ cards to be picked be $i_1, i_2, \ldots , i_m$. As the levels add up to less than total number of cards, there must exist an $i_r$ such that $i_r + L_r \leq i_{r+1}$ (treat $i_{m+1}$ as $i_1 + n$, where $n$ is the total number of cards). Then place all cards above $i_r$ at the end of the list and discard $i_r$ first (note that this operation doesn't remove any other $i_k$ from the list). And by induction assumption, it follows that the remaining $m-1$ cards can be discarded too.

So, as you pointed out, this problem reduces to the knapsack problem.

share|improve this answer
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.