Hi Everyone, today we will be discussing Problem C of recently concluded Codeforces #505 (Div1 + Div2) contest. I couldn't get idea behind this during contest but then solved it after the contest.
Problem Statement:
You are given a string containing two types of characters 'b' and 'w'. Your task is to modify string is such a way that it contains longest substring having alternate characters (let's refer it as zebra length). Modification can be done by one step, which is to cut string in two halfs (possibly zero length for one of half) and merge them again after reversing both the halfs. You can access problem at http://codeforces.com/contest/1025/problem/C
My Approach:
Initially I though it will have lot of corner cases as we can cut string from any place and transformed string again may be cut at any place. We can't be concrete about what index's cut on or what order of cuts will give us maximum zebra length.
But if you imagine this closely, what exactly are we doing in modification each time? We are cutting some point, and then merging after reversal of both parts, right? So basically only way answer can be increased from this first modification is if first character and last character (which will be together now) are alternate and they make a larger zebra length. Now if you do modification again, will it change anything? As per me, no. That's because now first and last were together before last step and if this could result in better zebra length, then it can't be more than original string.
One more way to analyze is to see that we are not changing anything if we take string as circular. We cur at some point in circle, reverse it (doesn't make any sense to reverse a line if you have to join it in end) and join it. So in short, zebra length remains same for circular string with same operation.
How to Implement:
We can simply append current string with same string and check for longest zebra length in this string. But this has a corner case. Suppose string given is already zebra length of even length, in this case circular will have 2*length as zebra length which can't be true if maximum can be equal to length. So we need to take care of this separately.
Implementation:
Please feel free to drop a comment if you have any doubts.
Problem Statement:
You are given a string containing two types of characters 'b' and 'w'. Your task is to modify string is such a way that it contains longest substring having alternate characters (let's refer it as zebra length). Modification can be done by one step, which is to cut string in two halfs (possibly zero length for one of half) and merge them again after reversing both the halfs. You can access problem at http://codeforces.com/contest/1025/problem/C
My Approach:
Initially I though it will have lot of corner cases as we can cut string from any place and transformed string again may be cut at any place. We can't be concrete about what index's cut on or what order of cuts will give us maximum zebra length.
But if you imagine this closely, what exactly are we doing in modification each time? We are cutting some point, and then merging after reversal of both parts, right? So basically only way answer can be increased from this first modification is if first character and last character (which will be together now) are alternate and they make a larger zebra length. Now if you do modification again, will it change anything? As per me, no. That's because now first and last were together before last step and if this could result in better zebra length, then it can't be more than original string.
One more way to analyze is to see that we are not changing anything if we take string as circular. We cur at some point in circle, reverse it (doesn't make any sense to reverse a line if you have to join it in end) and join it. So in short, zebra length remains same for circular string with same operation.
How to Implement:
We can simply append current string with same string and check for longest zebra length in this string. But this has a corner case. Suppose string given is already zebra length of even length, in this case circular will have 2*length as zebra length which can't be true if maximum can be equal to length. So we need to take care of this separately.
Implementation:
Please feel free to drop a comment if you have any doubts.
nice
ReplyDelete