Can somebody explain solution to this problem Problem - B - Codeforces
Think about how you would actually entangle such a thing if given. You cannot just pull any wire at any point in any direction. You would have to start somewhere suitable and entangle the whole mess step by step. The starting point would be anywhere that looks like the third test case (ignore the ends and pretend it’s in the middle of the long chain)
Here you would pull up the red wire and pull down the blue wire, and you have successfully removed a pair of crossover points without affecting anything else. Of course if the red and blue wires were swapped you could still do the same thing.
So this means that you need to do the following
- Find a place where red or blue is on top twice consecutively → Find any “++” or “–” in the string.
- Entangle it → Remove the “++” or “–” found from the string.
- Repeat until there are no more such double crossovers → Repeat until there are no “++” or “–”.
Now if you follow this it’s actually \mathcal{O}(n^2) where n is the length of the string, which is too slow. One solution is to use a stack, in a way very similar to the various balanced brackets problems. At each index you check whether the top of the stack is the same symbol at the current index. If so, you pop the stack (effectively removing the “++” or “–”), and if not you add the current symbol to the stack (setting it up for removal when a matching symbol is found further along the string). Then move on to the next index. At the end if all symbols added to the stack were popped off, the wires have been untangled 
This approach is \mathcal{O}(n) which works, and here’s my solution.
2 Likes
Thanks @meooww . Actually I was not able to understand the tutorial provided by them . It is completely different . Your solution is way nicer . Thank you very much for your time .
One more additional request :
Can you please advice me how to step up my level . I am stagnant from a long time now .
1 Like
Yes in the tutorial they have changed the problem to another form with A and B symbols but it doesn’t simplify the problem so I didn’t see the point of that.
And to become better just keep participating in contests and practicing, really there is no secret to it 
By the way I don’t think questions like these should be closed, because if later someone else wants to share his possibly better approach, he wouldn’t be able to.
1 Like