3

Problem Statement:

Alexa has two stacks of non—negative integers, stack A = [a0,a1, . . . ,an_1] and stack B = [b0, b1, . . . ,bm_1] where index 0 denotes the top of the stack. Alexa challenges Nick to play the following game:

In each move, Nick can remove one integer from the top of either stack A or stack B. Nick keeps a running sum of the integers he removes from the two stacks. Nick is disqualified from the game if, at any point, his running sum becomes greater than some integer given at the beginning of the game. Nick's fine/score is the total number of integers he has removed from the two stacks. Given A, B, and m for g games, find the maximum possible score Nick can achieve (i.e., the maximum number of integers he can remove without being disqualified)

Link to the problem: https://www.hackerrank.com/contests/university-codesprint-2/challenges/game-of-two-stacks

My solution(greedy approach):

  1. Pick(pop) the smallest element between the one present on top of the stack A and the other present on top of the stack B. Increment sum by the value of popped element and total(number of ints) by 1.
  2. Repeat 1 until either sum becomes greater than asked or one of the two stacks get empty.
  3. If one of the two stacks get empty then pop ints from the other stack until the current sum exceeds the asked limit.

Editorial solution:

This problem can be solved in linear time. We'll begin by taking as many integers as possible from stack A without exceeding the sum. Once we've done this we'll start taking integers from B, but whenever the sum becomes larger than the limit, we'll put integers back into stack A. Make sure to update the answer (the number of integers) as the traversal through stack B takes place. Break the loop when you have put back all integers that was taken from A and it's not possible to take any more integers from B.

Please explain where am I getting wrong and what is the intuition behind the editorial solution?

3
  • This only makes sense if you can only see the numbers at the top of each stack. You are not using the whole information, not surprisinly you don't get the best possible results.
    – Mandrill
    Feb 19, 2017 at 21:36
  • @Mandrill The question says that there are two stacks, in a stack you can only read the information at the top, unless you start popping values from the stack which uses CPU cycles. What algorithm you use to "see" the other values is precisely what the question is about
    – mastazi
    Feb 19, 2017 at 23:00
  • Well the editorial solution is peeking the stacks by taking integers from the stack and putting them back.
    – Mandrill
    Feb 20, 2017 at 0:06

1 Answer 1

6

Consider the case where the target is 6, A is [2, 2, 2] and B is [3, 1, 1, 1]. The solution here is 4 achieved by using all of B, but your solution gives 3.

In general greedy algorithms will not yield optimal results in cases where you are supposed to look into the future.

To answer the second part of the question: the editorial description is incomplete. The important step that the description misses is to update the answer only when you have improved it. The reason this works is the following: you can represent each game state as two numbers: the number of values taken from A (call it x) and the number of values taken from B (call it y). We can call a state (x, y) valid if summing the top x values of A and top y values of B does not exceed some target. We can call a state (x, y) maximal if (x, y) is valid but neither (x + 1, y) nor (x, y + 1) are valid. The key point is the when we maximize x + y over valid states then (x, y) must be maximal. So we can reduce the problem to maximizing the sum of the maximal states and their are at most min(size(A), size(B) of those.

The editorial solution then is very simple: enumerate all the maximal positions in the following way: start by finding x such that (x, 0) is maximal. To get the next step, increment y and keep decrementing x until (x, y) is valid: it will clearly also be maximal. Stop when y is too big for (0, y) to be valid. You then take this list of maximal (x, y) pairs (and you will have all of them) and take the max of x + y.

The editorial solution happens to fuse the "enumerate the maximal states" and "take the max of their sums" steps, but this is an optimization that does not change its complexity.

1
  • More extreme: [9, 9, 9, 9, 9, 9, 9, 9, 9, 9] vs [10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]. The greedy algorithm picks only nines. Better to pick the ten and then all ones.
    – gnasher729
    Feb 20, 2017 at 0:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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