Hello everyone. It would be great if someone gives a solution for this problem https://www.codechef.com/problems/CZ17R2Q2. Thank you.
Hello everyone. It would be great if someone gives a solution for this problem https://www.codechef.com/problems/CZ17R2Q2. Thank you.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3657 |
| 3 | jiangly | 3638 |
| 4 | turmax | 3442 |
| 5 | tourist | 3380 |
| 6 | Um_nik | 3353 |
| 7 | strapple | 3350 |
| 8 | squareOf105 | 3346 |
| 9 | heuristica | 3322 |
| 10 | maroonrk | 3310 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | AmShZ | 143 |
| 4 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 134 |
| 9 | maroonrk | 133 |
| 10 | qwexd | 130 |
Maintain a
stackof lengthn. For everyi-thelement, if it is positive, push it into the stack. If it is negative, let's call itx. Check ifstack.top() == -x. If yes, popstack.top()and increase the counter by 2.Solution complexity — O(n).
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.
How do you get answer 2 for 1 2 3 -1 ?
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.
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.
Basically, you have to find the largest subarray whose sum is equal to zero. You can look at my submission here