Hi Everyone,
I will be discussing one of problem from yesterday's contest CF #504.
You can access problem at http://codeforces.com/contest/1023/problem/C
Problem Statement:
Given a regular bracket sequence "S" of length "n", find another regular bracket sequence "T" having length "k" such that "T" is sub sequence of "S". Also "n" is strictly greater than "k".
Constraints:
2<=k<=n<=200000
Approach:
Basically we need to take out some of characters from "S" such that it remains regular bracket and meanwhile length reduces to k. Thus we need to remove [(n-k)/2] pairs of [()] from "S" to make a valid "T".
I decided to make a stack of characters and processed "S" keeping count of remaining pairs which we need to remove. So if at any point we encounter "(" in "S", we can simply put it in stack while if we encounter ")", we can be sure that current top of stack is "(". Thus we can pop that character from stack, ignore current ")" and continue as if we didn't have this "()" pair at all. This reduces our remaining variable by 1.
Gradually we will remove all required pairs. Now we will have some elements in stack which will be all "(". Thus we need to have a string will same number of "(" as size of stack. All other elements in out answer string will be remaining character of "S".
Implementation:
I hope code helps in clearing further doubts. Please feel free to drop a comment in case you are not able to understand approach.
I will be discussing one of problem from yesterday's contest CF #504.
You can access problem at http://codeforces.com/contest/1023/problem/C
Problem Statement:
Given a regular bracket sequence "S" of length "n", find another regular bracket sequence "T" having length "k" such that "T" is sub sequence of "S". Also "n" is strictly greater than "k".
Constraints:
2<=k<=n<=200000
Approach:
Basically we need to take out some of characters from "S" such that it remains regular bracket and meanwhile length reduces to k. Thus we need to remove [(n-k)/2] pairs of [()] from "S" to make a valid "T".
I decided to make a stack of characters and processed "S" keeping count of remaining pairs which we need to remove. So if at any point we encounter "(" in "S", we can simply put it in stack while if we encounter ")", we can be sure that current top of stack is "(". Thus we can pop that character from stack, ignore current ")" and continue as if we didn't have this "()" pair at all. This reduces our remaining variable by 1.
Gradually we will remove all required pairs. Now we will have some elements in stack which will be all "(". Thus we need to have a string will same number of "(" as size of stack. All other elements in out answer string will be remaining character of "S".
Implementation:
I hope code helps in clearing further doubts. Please feel free to drop a comment in case you are not able to understand approach.
No comments:
Post a Comment