http://codeforces.com/contest/877/problem/B
i am not getting the tutorial(just a few line ) …need some help on how to approach
The tutorial does this by using prefix and suffix arrays.
In 1 prefix arrays, we store the number of 'a’s encountered till now FROM START. In another prefix array, number of ‘b’ we encountered till now FROM START.
Now, start from the end of string. Can you see how we can use this information for final answer?
What I think the editorial does is, that it takes a pair of indices i and j, and fixes them as “We will consider b’s inside this block” (number of b inside block can be found using prefix array we made) and then counts a’s outside the block. The sum is the final answer.
But you can also get an O(N) solution for it. I havent tested it yet, but I think if we go from end, keeping a count of ‘a’ encountered till now, then we can use the prefix array of ‘a’ and ‘b’ directly to find the max length. Like, keep going on till its ‘a’, on encountering a ‘b’, make a second pointer and make it go to the start of that block of ‘b’ char, and then sue prefix arrays. Then resume from the start of block. Did not test it yet, but should be correct.
I didnt read the editorial but let me explain my approach if it helps.See first you need to be sure a solution always exists which is clear from the line “subsets can be empty”. Now i define my dp states. Let n be the index i am currently at,changes be the no.of switches i have made till now(switching means i have completed forming a subarray and is forming another one now. I.e suppose i was forming a subarray of a’s when i start forming a subarray of b’s i say i am switching. So its clear maximum no.of switches can be 2, first from a to b then from b to a.) And last which is 0 if i chose last element in my current subarray as a or 1 if b.(so its clear switching occurs when i change last from 1 to 0 or vice versa). Now my dp state reduces to:
F(n,change,last)={
If s[n]==last
F(n-1,change,last)+1
else
max(F(n-1,change,last),F(n-1,change+1,last^1)+1)
}
At any step if last==s[n](s[n]=0 if str[n]=a else 1)
we will include it in forming our subarray so we add it to our set else
we can either choose to add it in our set or not. To add it we need to make a change.
hope this helps. Here is the link to my solution:http://codeforces.com/contest/877/submission/31640788. If u have any doubts feel free to ask else if it helped please give a thumbs up 