0
$\begingroup$

The problem

Given $n$ stacks of $k$ integers each. What is the maximum sum that can be achieved by removing exactly $p$ integers?

The following example illustrates the problem.

$n$ = 3, $k$ = 4, $p$ = 3

stack 1: 2, 5, 12, 5

stack 2: 10, 3, 12, 50

stack 3: 7, 4, 20, 20

Note that the top of a stack is the leftmost element.

Here, the optimal solution is to pick all the first three numbers from stack 3, which gives a sum of 31.

The algorithm

I came up with the following algorithm.

enter image description here

The idea is to calculate the best possible sum for each stack if all $p$ elements were chosen from that particular stack. This sum only considers the integers that can possibly be taken.

Then, greedily take the top element from the stack with the best possible sum. And update the sum for all stacks because now only $p-1$ integers need to be popped.

The question

is this algorithm always going to produce a correct answer? If not, when would this fail?

Disclaimer

I am aware that a dynamic programming solution can solve the problem in $O(npk)$ time.

This is based on the following problem from a previous contest on google coding competitions platform. (https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d40bb)

$\endgroup$
3
2
$\begingroup$

Here is a counterexample, with $p = 2$:

  • stack 1: $600,600$.
  • stack 2: $1000,0$.
  • stack 3: $1000,0$.

Your algorithm will choose the top element from stack 1 and one of the top elements from the other stacks, but it is better to choose the top elements of stack 2 and stack 3.

Disclaimer: This is based on your description of the algorithm. I don't understand some of the notation in the algorithm itself.

$\endgroup$
5
  • $\begingroup$ Oops, I was thinking about minimizing the sum. Let me redo the example. $\endgroup$ Apr 5 '20 at 19:00
  • $\begingroup$ could you explain what is not clear in the notation? so that I can fix it. $\endgroup$
    – JhonRM
    Apr 5 '20 at 19:01
  • $\begingroup$ For example, the definition of $R_i$ is unclear. I guess you mean that initially, $l = 0$ and $r = \min(k-1,p-1)$. Then, $S$ is undefined. It is probably just the collection of all $S_i$. $\endgroup$ Apr 5 '20 at 19:03
  • $\begingroup$ Updated my example. $\endgroup$ Apr 5 '20 at 19:03
  • $\begingroup$ Yes, that is what I meant. I will try to make that clear. Thank you for your feedback $\endgroup$
    – JhonRM
    Apr 5 '20 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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