Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link ×

adzo261's blog

By adzo261, history, 4 weeks 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

4 weeks 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.