Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### Edvard's blog

By Edvard, 9 years ago, translation, ,

We will move from the left of string to the right. When we passed the whole string, or in the hands of us have 5 pieces, or current object is different from what we hold in our hands, we remove all the items in the pantry. The answer to the problem is the number of visits to the pantry.

The complexity is O(n).

We can count the number of integers from 1 to n, which occur in sequence at least once. Then the answer is n minus that number.

The complexity is O(n).

Denote a[i], b[i] - ends of the i-th event. Let's sort pairs (a[i], b[i]) by a[i] and iterate over all pairs. Denote rg the maximal b[i] from already processed. If current b[i] < rg than we must increment answer by one. If b[i] > rg than we must assign rg by b[i].

The complexity is O(n logn).

Let's preprocess array cnt[i][j] - the minimal number of changes tha we must do to make substring from position i to j palindrom. We can easy calc cnt[i][j] with complexity O(n^3). Now we can calculate dynamic programming z[i][j] - minimal number of changes that we can do to split prefix of length i into j palindromes. In begining we must assign z[i][j] = infinity for all (i, j) and assign z[0][0] = 0. If we want to make updates from state (i, j) we must fix the length of j-th palindrom - len. We can update z[i + len][j + 1] by value z[i][j] + cnt[i][i + len - 1]. Answer to the problem is the min(z[n][i]), where n is the length of string and i from range [1, k].

The complexity is O(n^3).

Let's replace all vowels by -1 and all consonants by +2. Obviously substring from position i to j is good if sum in the substring [i, j] is nonnegative. Denote this sum by sum[i][j]. Obviously sum[i][j] = p[j + 1] - p[i], where p[i] is the sum of first i elements. Now for all i we want to find maximal j such that j >= i and sum[i][j] >= 0. For this let's sort the array of (p[i], i) and build segment tree on this array by i. Let's iterate over all p[i] in nondescending order. Obsiously for fixed i we have that j = max(index[i]), where index[i] is the index of i-th partial sum in nondescending order and i from range [x, n], where x is the position of the first partial sum with value p[i] in sorted array. Than we must update position i by value of negative infinity and update answer by j - i.

The complexity is O(n logn).

• +23

 » 9 years ago, # |   +8 In E, you can easily do O(n) without interval tree. Let s[k] = max{p[i] : i=k, k+1, ..., n}. The values of s[k] are non-increasing and can be computed in linear time. For every i, you want to find maximal j >= i such that p[j] >= p[i] - in other words, the last j such that s[j] >= p[i]. You can either binsearch it (an easier n log n solution), or observe that when you find a good interval (i0 ,j0 ) and want to find a better one (i 1 ,j1 ) with i1  > i0 , there must be p[i1 ] < p[i0 ] and j1  > j0 . Therefore, you increase the value of i until you find smaller value of p[i], and then increase j until s[j+1] < p[i]. As the indices i, j only move right, the complexity is linear.
•  » » 8 years ago, # ^ |   0 That is very cool. Is computing the s[] array a common trick? Thanks!
 » 9 years ago, # |   +3 Could anybody have a quick look at my solution?I tried to figure it out why I could not pass Test Case 15. However, hours passed without any good results. Link: code. Thanks so much.
•  » » 9 years ago, # ^ |   +6 Maybe mistake in compareTo ? Add this in method: if (this.start > arg0.start)     return 1;
•  » » » 9 years ago, # ^ |   0 Oh~~~You are right. It works this time, though I still have no clue about how this happen. Thanks a lot anyway.
•  » » 9 years ago, # ^ |   0 I made the same mistake in my C++ code when implement my own comparison function %>_<%
 » 9 years ago, # |   0 Can someone please explain problem D Div 2 ? What are we supposed to do ?  Thank you ver much .
•  » » 9 years ago, # ^ |   0 прикольно, O(nlog2n), решил
 » 5 years ago, # |   0 I am Trying To solve Problem E Last Chance I am using Binary Search on length to find maximum Length which satisfy the criteria. But WA in Case 39My code: Code
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Binary search on length is just wrong.Here's a case where your code fails.Test: "baaab"Your code's output: "3 2"Correct answer should be: "5 1"Why the binary search property does not hold should be evident from this example. Basically, if you can form a good substring of length X, there's no guarantee that you can form good substrings of length < X.
•  » » » 5 years ago, # ^ |   0 THANKS , I UNDERSTOOD. MY NEW CODE GETS WRONG IN 53 TEST. CODE
 » 5 months ago, # |   0 problem E can be solved using a single map 69492668