# Game of Two Stacks

# Game of Two Stacks

vkreddy21 + 9 comments My c++ solution

#include <bits/stdc++.h> using namespace std; int main(){ int g; cin >> g; for(int a0 = 0; a0 < g; a0++){ int n; int m; int x; cin >> n >> m >> x; vector<int> a(n); for(int a_i = 0; a_i <n; a_i++){ cin >> a[a_i]; } vector<int> b(m); for(int b_i =0; b_i <m; b_i++){ cin >> b[b_i]; } int sum=0,count=0,temp=0,i=0,j=0; while(i<n && sum+a[i]<=x){ //considering only first stack and calculating count sum+=a[i]; i++; } count=i; while(j<m && i>=0){ //now adding one element of second stack at a time and subtracting the top element of first stack and calculating the count sum+=b[j]; j++; while(sum>x && i>0){ i--; sum-=a[i]; } if(sum<=x && i+j>count) count=i+j; } cout<<count<<endl; } return 0; }

baghad_billa + 1 comment Good solution. Can you explain how did you come up with this solution? Thanks.

vkreddy21 + 3 comments first I'm only considering one stack and calculating the sum and count number.Then I'm adding one element from second stack at a time to the calculated sum and comparing it with required sum.If the calculated sum is greater we subract the last added element of first stack from sum.

farhan_tanvir_u1 + 1 comment what's the reason for i>=0 checking in the outer while loop ? I think the code should work without this.

sagarkamdar37 + 1 comment It just restricts extra passes, since when i<0 you know that in the sum there are only numbers of second stack, you have already subtracted all the numbers of first stack. And now no need to continue.

singhjadaunatul + 0 comments [deleted]

aarce + 0 comments One of the games in test case 01 got me, your approach was very clever, help me rethink my approach, thank you.

slz250 + 0 comments i was still confused after reading this but my realization below helped clarify; so for those who still may be confused:

the whole idea of adding the recently popped 2nd stack element to the sum and removing the last 1st stack element if the sum is greater than the sum limit is to maintain the max count thus far.

therefore, the max count will never decrease and will only increase if either 1) we can add an element from the 2nd stack without removing from the sum or 2) removing an "added element from 1st stack" allows for 2 or more additional elements from 2nd stack.

Gaurav6601 + 0 comments awesome logic

hotshot47 + 3 comments I understand your logic, but this is not a stack operation. The only thing you can do is push and pop. You are accessing the 1st stack elements by index in the array.

Correct thing to do is push all the poped elements from first stack into a 3rd stack and pop back again while you traverse through second one.

emarsc + 0 comments Using an index on an array in this manner is essentially the same thing as a stack. Its more efficient.

ferran_maylinch + 0 comments I agree with emarsc's comment.

From this problem/solution you may learn that data structures can be used in different ways, or even modify them to better fit the problem. Consider for example solving the classic stack with max where all the operations are O(1), i.e. without looping.

seregaxvm + 0 comments Formally you're right, but you can easily replace indexing with buffer stack. Logic itself will not change.

Arun_Gandhi + 1 comment but where is the use of stack or atleast its concept

ferran_maylinch + 0 comments See emarsc's comment.

NishthaAhuja + 2 comments good logic my brute force solution recursive is showing timeout for almost half of cases

timbliz + 0 comments [deleted]timbliz + 1 comment Same here! Since you always have two choices for your next pick, I figured a binary search tree was the obvious answer, but no! If you take the top two from each stack, our way calculates all six paths to get that same one answer! What an exponential waste! And I thought I was so clever while coding it!

hector_h_prez + 0 comments hahaha, happened the same to me. I even tried improving this by considering the zero scenarios, that is if there are zeros I would navigate recursively only until the next non-zero element, also, I tried improving it by checking if it's convenient navigating further, given the current global Max.

rohanku_537 + 0 comments are u not facing timeout problem in some of the test cases?

sgrebenkin + 0 comments Implemented the same way on java. P.S.: With Scanner(System.in) the last test fails by TimeOut - use Fast I/O to resolve this.

vipulvikram3499 + 0 comments Nice approach. if we try greedy then there is problem in case where both corrosponding stack have same elements. Actually if we have problem in traversing both the stack simultaneously the best approach is to first traverse the 1st stack then start traversing second stack and manupulate the last added element from 1st stack as required in question.

nishantingle5 + 0 comments It gives correct answer but wrong numbers are added to the sum in following test case:

1

3 3 4

1 1 1

99 2 0

bawejakunal + 3 comments A greedy strategy to pick the smaller element from the top elements of A and B is giving me wrong answer for many test cases. Any hints for that ?

pallav_borisagar + 3 comments Consider two stacks s1 = [17,1,1,1,8] and s2 = [8,8,4,5,9] and max sum = 20. Using greedy approach you will select from s2 because 8 < 17. You will end up removing 3 ints from s2. Contrary to that if you pick from s1, you end up picking 4 ints.

krishna858606 + 0 comments any logic to overcome this?

waqas_bukhari + 0 comments Then this is a dynamic programming problem. When you say stack, you are restricting the access only to the top element.

anuragh27crony + 0 comments Thanks for the example. It solved my doubts about proposed solution.

Freak_1231 + 0 comments [deleted]julkas + 1 comment I agree with you. A and B are stacks not arrays and we canâ€™t pop and push back. Decision is based only on 4 numbers - running sum, limit and top elements of A and B. Take minimum.

tariq_p + 1 comment You can pop and push back. You are not "Nick" in the problem, you're just checking to see what the max score Nick can get is.

Lundii + 1 comment the question did not state that Nick can push back an integer.

xdavidliu + 0 comments "push back" is a term from c++ that corresponds to adding an element to the top of the stack; the commenter was not suggesting that Nick can actually put numbers back. Nick doesn't care about stacks; stacks are just something the problem suggests to use to solve the problem.

Lundii + 1 comment I think this question should be modified, as the operations performed on a stack are pop, push or peek. By the way, Nick can only see what's at the top of the stack and would definitely go for the smallest (greedy algorithm). Thanks

xdavidliu + 0 comments the question did not say that Nick could only see the top of the stack; it only suggests to use stacks to answer the question

qingl97 + 0 comments My Java solution :

static int twoStacks(int x, int[] a, int[] b) { int ai = 0; int bi = 0; int count = 0; int sum = 0; // move bi to the position where if only take elements from B, last element it can take while (bi < b.length && sum + b[bi] <= x) { sum += b[bi]; bi++; } bi--; // loop exits only when bi reaches end or sum > x; in both case bi should decrease count = bi + 1; while (ai < a.length && bi < b.length) { sum += a[ai]; if (sum > x) { while (bi >= 0) { sum -= b[bi]; bi--; if (sum <= x) break; } // if even no elements taken from B, but still sum greater than x, then a[ai] should not be chosen // and loop terminates if (sum > x && bi < 0) { ai--; break; } } count = Math.max(ai + bi + 2, count); ai++; } return count; }

The key point is that the order how each element is selected does not matter, which makes things complicated at the first galance. But if we consider through the final result, we should know that the problem is equals to that, to choose the maximum number of elements from each stack so that them sum is no greater than x. The finally selected elements come from either both stacks, either all from one stack. So let's start with assuption that all from stack B. Then everthing time try adding one element from A, if the total sum is greater than x, then we should reduce elements we took from B until the sum is no more than x which will form a valid way of selection. Keep trying until no more elements can be taken from A or B. We just need to keep track of the maximum number of total elements selected.

mkamilov + 1 comment anyone tried dp to solve this?

thismoment + 0 comments I have. Timed out with the half of test cases.

kewltek + 3 comments Since this was supposed to be a stack problem I was also annoyed by other solutions using arrays. So here is my Python solution using the python stack operations pop, append and the equiv of peek is lst[-1]. Notice I also reversed the original data since Python pop is O(n) if you pop or delete the first element.

#!/bin/python3 import sys g = int(input().strip()) for a0 in range(g): n,m,x = input().strip().split(' ') n,m,x = [int(n),int(m),int(x)] a = list(map(int, reversed(input().strip().split(' ')))) b = list(map(int, reversed(input().strip().split(' ')))) total = 0 atmp = [] for i in range(n): val = a.pop() if total + val > x: break total += val atmp.append(val) max_count = len(atmp) cur_count = max_count while m: if total + b[-1] <= x: total += b.pop() m -= 1 cur_count += 1 if cur_count > max_count: max_count = cur_count continue if not len(atmp): break aval = atmp.pop() total -= aval cur_count -= 1 print (max_count)

pareksha + 0 comments Wow, thankyou so much

makindiRunner + 0 comments I think they just mentioned stacks to help people comprehend how the game is played, I don't think this problem is intended to test our ability to use stacks.

Suyog123 + 0 comments Thank you so much!!! Your info : Python pop is O(n) if first element is popped, hence, reverse the list, enabled me to pass all the test cases from 8 to 13. I was getting an error of terminated due to timeout before for these test cases.

akash_goel + 4 comments Had to use fast reader class to get AC in Java from here: http://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/.

Anybody got AC in Java using Scanner itself?

bassam_1981 + 0 comments he's right. I did mine in Java and I failed in one test case (timeout). I succeeded with the FastReader. This challenge is the worst I have had. I like the problem but this is the first time I had to use something other than scanner to pass the tests.

ketav + 0 comments I wish I had read this comment before. My java code worked with Scanner class but it quite ugly. (Test case 9 was most troublesome for me)

`public static int getMaxRemovedItems7(int [] a, int [] b, int x) { int total = 0; int max = 0; ArrayList<Integer> aPrefix = new ArrayList<>(a.length); ArrayList<Integer> bPrefix = new ArrayList<>(b.length); for(int i=0; i<a.length && total <= x; i++) { total += a[i]; aPrefix.add(total); } aPrefix.trimToSize(); total = 0; for(int i=0; i<b.length && total <= x; i++) { total += b[i]; bPrefix.add(total); } bPrefix.trimToSize(); int i=0; while((i+1)<aPrefix.size() && aPrefix.get(i+1) == 0) i++; int jStart = 0; while((jStart+1)<bPrefix.size() && bPrefix.get(jStart+1) == 0) jStart++; for(; i<aPrefix.size() && aPrefix.get(i)<=x; i++) { int j = nearest(bPrefix, jStart, bPrefix.size()-1, x-aPrefix.get(i)); if((aPrefix.get(i)+bPrefix.get(j)) > x && (i+j+1) > max) { max = i+j+1; } else if ((aPrefix.get(i)+bPrefix.get(j)) <= x && (i+j+2) > max) { max = i+j+2; } } if(max >= aPrefix.size() + bPrefix.size()) { return max; } i=0; if((i+1)<bPrefix.size() && bPrefix.get(i+1) == 0) i++; jStart = 0; while((jStart+1)<aPrefix.size() && aPrefix.get(jStart+1) == 0) jStart++; for(; i<bPrefix.size() && bPrefix.get(i)<=x; i++) { int j = nearest(aPrefix, jStart, aPrefix.size()-1, x-bPrefix.get(i)); if((bPrefix.get(i)+aPrefix.get(j)) > x && (i+j+1) > max) { max = i+j+1; } else if ((bPrefix.get(i)+aPrefix.get(j)) <= x && (i+j+2) > max) { max = i+j+2; } } return max; } private static int nearest(List<Integer> arr, int start, int end, int total) { if(start<end) { if(start == (end-1)) { return Math.abs(arr.get(start)-total) <= Math.abs(arr.get(end)-total) ? start : end ; } else { int mid = start + (end-start)/2; if(arr.get(mid) == total) { while(mid+1 < arr.size() && arr.get(mid) == arr.get(mid+1)) mid++; return mid; } else if (arr.get(mid) > total) { while(mid-1 >= 0 && arr.get(mid) == arr.get(mid-1)) mid--; return nearest(arr, start, mid, total); } else { while(mid+1 < arr.size() && arr.get(mid) == arr.get(mid+1)) mid++; return nearest(arr, mid, end, total); } } } return start; }`

bennattj + 0 comments Got AC with Scanner. Shouldn't be too difficult as the optimal algorithm is O(n + m):

int count = 0; final Stack<Long> leftStack = new Stack<>(); for (int i = 0; i < sums1.length && sums1[i] <= x; ++i) { ++count; leftStack.push(sums1[i]); } int max = count; for (int j = 0; j < sums2.length && sums2[j] <= x; ++j) { // check whether or not you can add the next sum from // right stack (sums2) to the current top of left stack if (!leftStack.isEmpty() && sums2[j] + leftStack.peek() > x) { // count was increasing but now we have to pop off // stack before adding next element in sums2, // check count now (because it's about to // decrease from removing from the left stack) if (count > max) max = count; // keep popping off the stack until the left sum // and the right sum are <= x OR we've emptied // the left stack while (!leftStack.isEmpty() && sums2[j] + leftStack.peek() > x){ --count; leftStack.pop(); } } // we just added from the right stack, so increment ++count; } if (count > max) max = count;

mhmdk + 0 comments Thanks for the tip. I got AC using scanner , but barely AC

jimcodeman123 + 0 comments can someone help me this code fails in 3 testcases

#include <bits/stdc++.h> using namespace std; int sizeA , sizeB , maxN ; long long A[ 100001 ] = {0} , B[ 100001 ] = {0} ; void preCalculate( void ) { for( int add = 0 ; add < sizeA ; add++ ){ A[ add ] += (add>0)?A[ add - 1 ]:0 ; } for( int add = 0 ; add < sizeB ; add++ ){ B[ add ] += (add>0)?B[ add - 1 ]:0 ; } } long Answer( void ){ long answer = 0 , prev = 0 , test = 0 ; for( int parse = sizeA-1 ; parse >= 0 ; parse-- ){ if(A[parse] > maxN)continue; while( prev < sizeB ){ if(A[parse] + B[prev] > maxN)break; prev++; }prev--; if(A[parse] + B[prev] <= maxN)answer = max( parse + prev + 2 , answer ); } return answer ; } int main( void ) { int Testcases ; scanf( "%d" , &Testcases ); while(Testcases--){ scanf( "%d %d %d" , &sizeA , &sizeB , &maxN ) ; for( int read = 0 ; read < sizeA ; read++ ){ scanf( "%lld" , &A[read] ); } for( int read = 0 ; read < sizeB ; read++ ){ scanf( "%lld" , &B[read] ); } preCalculate(); printf("%ld\n",Answer()); } return 0 ; }

videetnimsarkar1 + 0 comments y = [] a.reverse() b.reverse()

while True: if sum(y)< x:

`if a[-1]<b[-1]: y.append(a[-1]) a.pop() else: y.append(b[-1]) b.pop() else: break`

if sum(y)>x: y.pop() return(len(y))

arjuntirumalase1 + 0 comments Hello All,

Please help me to analyse below scenario. 20 35 67 19 9 8 13 1 7 18 0 19 19 10 5 15 19 0 0 16 12 5 10 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

As i was getting result is

**5**. But in solution it was**6**Thanks, Arjun

Sort 159 Discussions, By:

Please Login in order to post a comment