### Romok007's blog

By Romok007, history, 6 months ago, ,

Hello everyone. It would be great if someone gives a solution for this problem https://www.codechef.com/problems/CZ17R2Q2. Thank you.

• -1

 » 6 months ago, # | ← Rev. 2 →   +1 Maintain a stack of length n. For every i-th element, if it is positive, push it into the stack. If it is negative, let's call it x. Check if stack.top() == -x. If yes, pop stack.top() and increase the counter by 2. Solution complexity — O(n).
•  » » 6 months ago, # ^ |   0 I think for the input : 1 2 3 -1. Your solution will give 0 as the answer whereas the ans should be 2. Correct me if i am wrong.
•  » » » 6 months ago, # ^ |   +1 How do you get answer 2 for 1 2 3 -1 ?
•  » » » » 6 months ago, # ^ |   0 The question asks for the longest balanced subsequence. So if we take 1 -1 as the subsequence from 1 2 3 -1, we end up with a balanced subsequence of length 2.
•  » » » » » 6 months ago, # ^ |   0 I guess you have to pick consecutive positions because for sample testcase 1 -1 2 3 -2 answer is 2 (1 and -1). The answer could be 4 (1, -1, 2, -2) if it would be allowed to pick any positions. So for input 1 2 3 -1 answer is 0.
•  » » » » » » 6 months ago, # ^ |   0 Ahh, you got a point. The question was poorly stated anyways thank you for your help :).
 » 6 months ago, # |   0 I think that for this problem, it is easy enough to figure out the solution from AC codes.
•  » » 6 months ago, # ^ |   0 The AC codes fail for the input : 1 2 3 -1.I guess the solutions get accepted due to weak test cases.So I was really curious to know the correct solution.
 » 6 months ago, # |   0 Basically, you have to find the largest subarray whose sum is equal to zero. You can look at my submission here