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

Before contest

Codeforces Round #606 (Div. 1, based on Technocup 2020 Elimination Round 4)

17:55:53

Register now »

Codeforces Round #606 (Div. 1, based on Technocup 2020 Elimination Round 4)

17:55:53

Register now »

*has extra registration

Before contest

Codeforces Round #606 (Div. 2, based on Technocup 2020 Elimination Round 4)

17:55:52

Register now »

Codeforces Round #606 (Div. 2, based on Technocup 2020 Elimination Round 4)

17:55:52

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3556 |

2 | wxhtxdy | 3520 |

3 | Radewoosh | 3409 |

4 | Benq | 3368 |

5 | mnbvmar | 3280 |

6 | ecnerwala | 3278 |

7 | LHiC | 3276 |

8 | sunset | 3264 |

9 | maroonrk | 3159 |

10 | TLE | 3145 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 189 |

2 | Radewoosh | 177 |

3 | tourist | 173 |

4 | antontrygubO_o | 172 |

5 | Vovuh | 168 |

6 | PikMike | 166 |

7 | rng_58 | 157 |

8 | majk | 156 |

9 | farmersrice | 153 |

9 | Um_nik | 153 |

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

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/13/2019 20:09:08 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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).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.

Ahh, you got a point. The question was poorly stated anyways thank you for your help :).

I think that for this problem, it is easy enough to figure out the solution from AC codes.

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.

Basically, you have to find the largest subarray whose sum is equal to zero. You can look at my submission here