You are not logged in. Please login at www.codechef.com to post your questions!

×

Codeforces 343B

Can somebody explain solution to this problem http://codeforces.com/contest/343/problem/B

asked 04 Oct '17, 23:27

trashmaster's gravatar image

2★trashmaster
98619
accept rate: 12%

closed 05 Oct '17, 13:36


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)
simple_case
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
1. Find a place where red or blue is on top twice consecutively -> Find any "++" or "--" in the string.
2. Entangle it -> Remove the "++" or "--" found from the string.
3. 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 :D
This approach is $\mathcal{O}(n)$ which works, and here's my solution.

link

answered 05 Oct '17, 03:13

meooow's gravatar image

6★meooow ♦
7.1k718
accept rate: 48%

1

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 .

(05 Oct '17, 13:35) trashmaster2★
1

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 :P

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.

(05 Oct '17, 16:27) meooow ♦6★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×682

question asked: 04 Oct '17, 23:27

question was seen: 465 times

last updated: 05 Oct '17, 17:47