Correct Algorithm for Game of two stacks on HackerRank

Question

I just attempted a stack based problem on HackerRank

https://www.hackerrank.com/challenges/game-of-two-stacks

Alexa has two stacks of non-negative integers, stack A and stack B 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 B stack.

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 X given at the beginning of the game.

Nick's final score is the total number of integers he has removed from the two stacks.

find the maximum possible score Nick can achieve (i.e., the maximum number of integers he can remove without being disqualified) during each game and print it on a new line.

For each of the games, print an integer on a new line denoting the maximum possible score Nick can achieve without being disqualified.

Sample Input 0

1 -> Number of games
10 -> sum should not exceed 10 
4 2 4 6 1  -> Stack A
2 1 8 5 -> Stack B

Sample Output 

4

Below is my code I tried the greedy approach by taking the minimum element from the top of the stack & adding it to the sum. It works fine for some of the test cases but fails for rest like for the below input

1
67
19 9 8 13 1 7 18 0 19 19 10 5 15 19 0 0 16 12 5 10 - Stack A
11 17 1 18 14 12 9 18 14 3 4 13 4 12 6 5 12 16 5 11 16 8 16 3 7 8 3 3 0 1 13 4 10 7 14 - Stack B

My code is giving 5 but the correct solution is 6 the elements popped out in series are 19,9,8,11,17,1 First three elements from stack A & then from Stack B.

**

I don't understand the algorithm It appears like DP to me can anyone help me with the approach/algorithm?

**

public class Default {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int numOfGames = Integer.parseInt(br.readLine());
        for (int i = 0; i < numOfGames; i++) {
            String[] tmp = br.readLine().split(" ");
            int numOfElementsStackOne = Integer.parseInt(tmp[0]);
            int numOfElementsStackTwo = Integer.parseInt(tmp[1]);
            int limit = Integer.parseInt(tmp[2]);
            int sum = 0;
            int popCount = 0;

            Stack<Integer> stackOne = new Stack<Integer>();
            Stack<Integer> stackTwo = new Stack<Integer>();

            String[] stOne = br.readLine().split(" ");
            String[] stTwo = br.readLine().split(" ");

            for (int k = numOfElementsStackOne - 1; k >= 0; k--) {
                stackOne.push(Integer.parseInt(stOne[k]));
            }

            for (int j = numOfElementsStackTwo - 1; j >= 0; j--) {
                stackTwo.push(Integer.parseInt(stTwo[j]));
            }

            while (sum <= limit) {
                int pk1 = 0;
                int pk2 = 0;
                if (stackOne.isEmpty()) {
                    sum = sum + stackTwo.pop();
                    popCount++;
                } else if (stackTwo.isEmpty()) {
                    sum = sum + stackOne.pop();
                    popCount++;
                } 
                else if (!stackOne.isEmpty() && !stackTwo.isEmpty()) {
                    pk1 = stackOne.peek();
                    pk2 = stackTwo.peek();

                    if (pk1 <= pk2) {
                        sum = sum + stackOne.pop();
                        popCount++;
                    } else {
                        sum = sum + stackTwo.pop();
                        popCount++;
                    }
                } else if(stackOne.isEmpty() && stackTwo.isEmpty()){
                    break;
                }
            }

            int score = (popCount>0)?(popCount-1):0;
            System.out.println(score);
        }
    }
}

Solution 1

Ok I will try to explain an algorithm which basically can solve this issue with O(n), you need to try coding it yourself.

I will explain it on the simple example and you can reflect it

1 -> Number of games
10 -> sum should not exceed 10  
4 2 4 6 1  -> Stack A
2 1 8 5 -> Stack B

First you will need to creat 2 arrays, the array will contain the summation of all the number up to its index of the stack, for example for stack A you will have this array

4 6 10 16 17  //index 0 ->4

Same will be done for stack B

2 3 11 16

then for each array start iterating from the end of the array until you reach a number less than or equal to the "sum you should not exceed"

now your current sum is the sum of the point you reached in both arrays, should be 10 +3 = 13 so in order to reach 10 will absolutely need to remove more entries

to remove the additional entries we will be moving the indexes on the array again, to decide which array to move it's index take the entry you are pointing at (10 for array 1 and 3 for array 2) and device it by index+1 (10/3 ~ 3) , (3/2 ~1) then move the index for the highest value and recalculate the sum

Suppose we have:

a = 1 1 1 211 2
b = 1 85

and maxSum = 217 Now, on calculating prefix sums,

a' = 1 2 3 214 216
and b' = 1 86
current sum = 86+216 > 217

so to decide which index to remove, we compare `

216/5~43.2` and `86/2=43`, 

so we move pointer in a'. BUT, that doesn't solve it - `

214+86 is still > 217!!` 

Had we removed 86, it would've been better! So we should always go ahead by removing the one which has larger difference with previous element!

In case both values are equal its logical to move the index on the value which has larger difference with its previous ( remember we are moving the index in reverse order).

the result will be the sum of the indexes +2.

Solution 2

This solution works great.... i hope it helps ...

   import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int g = sc.nextInt();
        for (int tc = 0; tc < g; tc++) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int x = sc.nextInt();
            int[] a = readArray(sc, n);
            int[] b = readArray(sc, m);

            System.out.println(solve(a, b, x));
        }

        sc.close();
    }

    static int[] readArray(Scanner sc, int size) {
        int[] result = new int[size];
        for (int i = 0; i < result.length; i++) {
            result[i] = sc.nextInt();
        }
        return result;
    }

    static int solve(int[] a, int[] b, int x) {
        int lengthB = 0;
        int sum = 0;
        while (lengthB < b.length && sum + b[lengthB] <= x) {
            sum += b[lengthB];
            lengthB++;
        }

        int maxScore = lengthB;
        for (int lengthA = 1; lengthA <= a.length; lengthA++) {
            sum += a[lengthA - 1];

            while (sum > x && lengthB > 0) {
                lengthB--;
                sum -= b[lengthB];
            }

            if (sum > x) {
                break;
            }

            maxScore = Math.max(maxScore, lengthA + lengthB);
        }
        return maxScore;
    }
}

Solution 3

solution in python3

# stack implementation
class Stack:
    lis = []

    def __init__(self, l):
        self.lis = l[::-1]

    def push(self, data):
        self.lis.append(data)

    def peek(self):
        return self.lis[-1]

    def pop(self):
        self.lis.pop()

    def is_empty(self):
        return len(self.lis) == 0


# number of test cases
tests = int(input())
for i in range(tests):
    na, nb, x = map(int, input().split(' '))
    a = list(map(int, input().split(' ')))
    b = list(map(int, input().split(' ')))
    temp = []
    stk_a = Stack(a)
    stk_b = Stack(b)
    score = 0
    count = 0
# first taking elements from stack A , till score becomes just less than desired total
    for j in range(len(a)):
        if score + stk_a.peek() <= x:
            score += stk_a.peek()

            count += 1
            temp.append(stk_a.peek())
            # storing the popped elements in temporary stack such that we can again remove them from score
            # when we find better element in stack B
            stk_a.pop()
# this is maximum number of moves using only stack A
    max_now = count
# now iterating through stack B for element lets say k which on adding to total score should be less than desired
    # or else we will remove each element of stack A from score till it becomes just less than desired total.
    for k in range(len(b)):
        score += stk_b.peek()
        stk_b.pop()
        count += 1
        while score > x and count > 0 and len(temp) > 0:
            count = count - 1
            score = score - temp[-1]
            temp.pop()
        # if the score after adding element from stack B is greater than max_now then we have new set of moves which will also lead
        # to just less than desired so we should pick maximum of both
        if score <= x and count > max_now:
            max_now = count
    print(max_now)

Solution 4

I see that there exist a solution and you marked it as correct, but I have a simple solution

1. add all elements from stack one that satisfy condition <= x
2. every element you add push it on stack called elements_from_a
3. set counter to size of stack
4. try add elements from stack b if sum > x so remove last element you added you can get it from stack elements_from_a
5. increment bstack counter with each add , decrements from astack with each remove
6. compare sum of steps with count and adjust count return count

here is code sample for the solution :

def twoStacks(x, a, b):
sumx = 0
asteps = 0
bsteps = 0
elements = []
maxIndex = 0

while len(a) > 0 and sumx + a[0] <= x :
    nextvalue =  a.pop(0)
    sumx+=nextvalue
    asteps+=1
    elements.append(nextvalue)

maxIndex = asteps


while len(b) > 0 and len(elements) > 0:
    sumx += b.pop(0)
    bsteps+=1
    while sumx > x and len(elements) > 0 :
        lastValue = elements.pop()
        asteps-=1
        sumx -= lastValue



    if sumx <= x and bsteps + asteps > maxIndex :
        maxIndex = bsteps + asteps



return maxIndex

I hope this is more simple solution.

View more solutions

Comments

[underdog]

I kind of understood your solution Amer but it isn't an obvious one, is this some kind of algorithm/a specific mathematical approach to solve these kinds of questions? I initially thought of two approaches to solve this A. Take the sum of Stack A & Stack B & find the max elements. B. Greedy approach find the min element at the top each time. But the one you suggested isn't an obvious one.

[Amer Qarabsa]

@underdog there are many ways to solve it greedely , but the idea is anyway you need to visit both of the stacks, my solution aims to visit the stack reversly since this will relief me from the hug possibilities if i go the opposite, taking the max element has a problem that you do not know the number of the included elements, i agree that the solution is not obvious , i just came up with this algorithm and maybe later i will code and share it

[nanosoft]

Can u please explain the algo?

[manikanta nvsr]

can you explain the algorithm?

[black.swordsman]

Please explain the algorithm.