adzo261's blog

Help in Div1 B. Alternating Current

By adzo261, history, 5 years ago, In English

Can anyone help me with how to approach this problem?
I am completely blank on how to proceed.
I tried reading the editorial but couldn't understand it.

Problem Link

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The key idea is that if the adjacent characters are equal, then we can untangle them. So if a sequence of length n exists, we can change it to a sequence of length n-2 by deleting the adjacent ones.

For example, (-++-) -> (--) -> ()

I used a stack to do this.

  • If the stack is empty, push the current character onto the stack.

  • Else if the top symbol is same as the current one, pop it off the stack.

  • Else push it onto the stack.

  • Finally check if the stack is empty or not.

code

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for this, the official editorial is very confusing.

    → Reply