205A - Little Elephant and Rozdil

The key problem is to determine whether there are multiple minimum values.

205B - Little Elephant and Sorting

If a[i] ≤ a[i + 1], we do nothing; otherwise, we should increase all a[j], j ≥ i + 1 together until a[i + 1] is equal to a[i], which contributes a[i] - a[i + 1] to the final answer. Meanwhile, we don't need “really” implement the increasing operations, as one can see that only the difference between two neighboring elements matters while this difference does not change even if we really increase the values.

205C - Little Elephant and Interval

A general idea behind this problem is that when asked to answer some query with interval [l, r], it may be more convenient to establish a function f(x) which gives a result for [1, x], and thus the answer to the query is f(r) - f(l - 1), just like the prefix idea.

205D - Little Elephant and Cards

Note that each card contributes at most two different colors, and thus we have 2n colors. This implies that there are at most four colors whose total number can be equal to or larger than n / 2. Therefore, the idea is summarized as follows.

At first, we compress the data into range [1, 2 × 10⁵]. Then, we use a “hash table” to count the number of each color (notice that if a card has the same color at both sides, we increase the corresponding counter only once rather than twice). Next, we find out all the colors whose counters are equal to or larger than n / 2 (at most four). Finally, we enumerate each of these colors, and calculate the minimum number of flipping that we need.

205E - Little Elephant and Furik and Rubik

We first give a simple example to reveal the key idea behind this problem. Suppose that we have two substrings “ABC” and “ADC”. According to the rules, we can obtain two points, since both “A” and “C” have the same position. However, from another perspective, we can redistribute the two points into “A” and “C”, respectively, i.e., letter “A” contributes one point while letter “C” contributes one point.

From the above arguments, we can calculate the points for letters “A, B,...,Z” independently, and then add them together, which gives the correct answer as well. We give letter “A” as a simple example.

Suppose that letter “A” is found at position i in thr first string and position j in the second string. Then, there are min(i + 1, j + 1) × min(n - i, n - j) substring pairs that have “A” at the same position and thus contributes min(i + 1, j + 1) × min(n - i, n - j) points to the final answer (index i starts from zero).

Next, we store all the positions at which “A” appears in the first and second string in array a[i] and b[i], respectively. A trivial solution is to enumerate all the pairs and compute min(i + 1, j + 1) × min(n - i, n - j). However, the trick to reduce the complexity is that for any j > i, min(i + 1, j + 1) × min(n - i, n - j) is always equal to (i + 1) × (n - j). To take advantage of this observation, we adopt two pointers idea. We use p1 and p2 to point to arrays a and b, respectively, and these two arrays have length la and lb. As long as b[p2] ≤ a[p1], we move p2 forward, and it contributes (b[p2] + 1) × (suffixa[p1]) to the final answer, where can be viewed as a suffix sum. When we reach a b[p2] > a[p1], an extra value of (a[p1] + 1) × suffixb[p2] is added to the final answer, where . Then, we move p1 forward until b[p2] ≤ a[p1], and remember that each moving contributes (a[p1] + 1) × suffixb[p2] to the final answer.