Edvard's blog

By Edvard, 13 years ago, translation, In English

A. Postcards and photos

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).

B. Permutation

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).

C. History

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).

D. Palindromes

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).

E. Last Chance

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).

  • Vote: I like it
  • +23
  • Vote: I do not like it

| Write comment?
»
13 years ago, # |
  Vote: I like it +8 Vote: I do not like it
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 (i1,j1) with i> i0, there must be p[i1] < p[i0] and j> 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.
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That is very cool. Is computing the s[] array a common trick? Thanks!

»
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
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.
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    Maybe mistake in compareTo ?
    Add this in method:
    if (this.start > arg0.start)
        return 1;
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I made the same mistake in my C++ code when implement my own comparison function %>_<%
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can someone please explain problem D Div 2 ? What are we supposed to do ? 
 Thank you ver much .
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 39

My code: Code

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

problem E can be solved using a single map 69492668