Блог пользователя Romok007

Help needed with a problem
Автор Romok007, история, 5 лет назад, По-английски

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

  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

»
5 лет назад, # |
← 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).

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 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.

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      How do you get answer 2 for 1 2 3 -1 ?

      → Ответить
      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 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.

        → Ответить
        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 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.

          → Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить