CF #98, prob 137

I had 4 problems AC in this div2 contest and rating got up a little bit. Ranked 89 overall.

A, B are trivial problems and didn't take much thought.

C is asking how many intervals are included inside another interval. All (left,right) are distinct. It is all too natural to sort them by left, then from increasing left, use current interval to include as many follow up intervals as possible. Then move to next not included interval. The observation is that, if [a2,b2] is included in [a1,b1], then any [ai,bi] included in [a2,b2] is also included in [a1,b1] so we are not missing anything by throwing away [a2,b2]. On the other hand, any [ai,bi] not included in [a1,b1] cannot be included in any of [a2,b2].

D is a DP problem. Given a string of length 500, find a way to break it into at most k<=500 palindromes. Let dp(npal,pos) be the cost of the solution to break string [0,pos) into at most npal palindromes. The answer is then dp(k,n). The recurrence is dp(npal,pos) = min of dp(npal-1, p) + cost to make str[p,pos) a palindrome where p range from 0 to pos-1. Base case is true when pos=0 and npal>=0.

E It does not look difficult but couldn't figure out an algorithm fast enough. the problem is that given a string of length <= 10^5, find all maximum length substr with nvowel <= 2*nconsonant. It looks apparent that you need O(n) or O(nlogn) algorithm, the question is how?

After two days I finally got a solution that works. I don't know why I am so determined to solve it and I have much confidence that I will get it, although several attempts failed.

Let vow[n], con[n] be the count of vow and con from 0 to pos.
The first observation is that vow[n] and con[n] change at most 1 as we move along the string. So we can compute vow[n] and con[n] in one scan of the string.

Now consider the substr with maximum length. If it does not reach pos=0 or pos=n-1, then it is bounded inside the string. Therefore, it must be the case that nvow=2*ncon in this substring, otherwise it can get longer by expand left or right. Let the start be i and end+1 be j. we know that vow[j]-vow[i]=2*(con[j]-con[i]), rearrange it gives vow[i]-2*con[i]=vow[j]-2*con[j]. So we can build an array diff[i]=pair(vow[i]-2*con[i], i) and sort diff[]. Those with same diff[i] value will be consecutive after sorting and for elements with same diff[i], we seek the index of first and last, and currlen=last-first is a candidate for maxlen.

After that we check the maxlen if we begin from pos=0, and maxlen if we begin from pos=n-1.

After we have maxlen known, we can check all substr of length maxlen to see if they qualify as a solution, that is nvow<=2*ncon. This check can be done in O(n) time.

Overall the algorithm is O(n) time except sorting the diff[] array.

With even a simple implementation, my solution runs within 60ms in CF machine.

Approaches that does not quite work:
1. binary search maxlen. Unfortunately there is no monotone property as a valid substr of length k does not include a valid substr of length k-1.
2. start from a pos with a consonant and build a substring. The problem is that you could hit a block of vows and then a block of cons. So each pos might require O(n), which amounts to O(n^2).