codeforces #297 B. Pasha and String

you can get the problem statement from here.

One important point we have to remember here is that if there are two update operation x, y (x < y < n/2) then the positions from y to n - y + 1 remain same as before the update operations.

One easy of looking the problem is as a simple lazy segment tree propagation problem O(n*log(n)). Using the segment tree's we have to record the number of swaps at each position. i.e we just have to perform the update operations(adding 1) in a lazy manner. and after that we have to swap the character if the number of swaps are odd.

https://gist.github.com/546ca7fe7e624fab615a

but this problem can also solved in O(n). i.e counting the number of swaps.

https://gist.github.com/546ca7fe7e624fab615a

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s