** UPD: Formulas are already fixed. **

163A - Substring and Subsequence

Solution summary: dynamic programming.

Sample jury solution: 1415300 (author = levlam)

The problem could be solved with the following dynamic programming. Let f[i, j] be the number of distinct pairs ("substring starting at position i" and "subsequence of the substring t[j... |t|]")

Then:

f[i, j] = f[i, j + 1];
if (s[i] == t[j])
  add(f[i, j], f[i + 1, j + 1] + 1)

Answer = f[i,0]

163B - Lemmings

Solution summary: sorting + binary search.

Sample jury solution: 1415306 (author: Burunduk1)

We need to find the minimal time T. Let us find it using binary search.

Once the time is fixed, one can arrange lemmings using greedy approach starting either from the top or from the bottom. In this solution we consider the way to start from the bottom. Among all lemmings, that can get on the first ledge, let's choose the lemming with the minimal weight (and among all such lemmings the one with the minimal speed). Why is it correct? Assume that we used some heavier lemming, then we can't use any lighter lemming anywhere, so we could replace it. Among all lemmings with the minimal weight we choose the slowest, as the faster ones can climb higher.

To arrange lemmings fast, we can sort them beforehand, comparing first the weight and then the speed. After if, we consider all the lemmings in that order and either choose the current one, if it can get in time, or leave it. It is useless to consider one lemming twice, as we won't be able to use it anyway.

So, the solution consists of sorting and a binary search with a linear search inside. The time is .

However, that was not enough. One also had to deal with precision problems. Let us evaluate the number of binary search iterations.

0 ≤ T ≤ H * K (the maximal time does not exceed 10⁹). We need to understand how the times can differ. In the case of "N = K = 10⁵, H = 10⁴, V about 10⁹" the times needed for two lemmings to get on some ledges, can differ by 10^- 18, as the times are fractions like , where X and Y are about 10⁹.

So we need to make log₂10²⁷ = 90 iterations. In fact, jury solution made 75 and that was enough, however 70 was not. The idea above shows that 90 will be definitely enough.

163C - Conveyor

Solution summary: events along the circle or binary search.

Sample solution: 1415310 (author: Burunduk1)

Sample solution: 1415316 (author: arseny30)

Wherever Anton starts, he will run along the conveyor a segment of length . Consider one candy. To eat it, he needs to get on the conveyor in any moment of the segment [a_i - D..a_i]. Consider all points like a_i - D and a_i (add 2l if that is negative). Also add points 0 and 2l.

Sort these points. Consider two neighboring points: x[i] и x[i+1]. If Anton starts at any moment between them, he will eat the same amount of candies.

From now on, we can create one of the solving solutions:

1. Start from every middle of the segment M = (x[i]+x[i+1]) / 2 and use binary search to find the number of candies on the segment [M..M + D].

2. Consider events along a circle like (a[i] — D, +1) and (a[i], -1). One needs to move twice along the circle and use the second run to add the current length to the answer for the current number of candies.

The both solutions require time.

163D - Large Refrigerator

Solution summary: backtracking + boundaries evalutaion.

Sample solution: 1415320 (author: Burunduk1)

The solution consists of three main ideas:

1. V = ABC, A ≤ B ≤ C тогда A ≤ N^1 / 3, B ≤ (N / A)^1 / 2.

2. A and B are divisors of V, as we are already given the factorization of V, we can run only through the divisors

3. Given fixed A, the optimal real B and C are (N / A)^1 / 2 (denote this values as X). I.e. the square will always be greater than  ≥ 2(2AX + X²). So we can use this value as a boundary for the answer.

If that still was not enough, one could optimize using the following ideas:

1. Border evaluation will be more useful while running through possible values of A in descending order

2. A and B are 32-bit integers.

3. Once we have calculated the answer for V, memoize it (this one makes possible maximal test a bit smaller).

If anyone needs any theoretical base, here's some statistical information:

1. The maximal number of divisors of numbers from 1 through 10¹⁸ is 103860 (the number 897612484786617600 = 2⁸3⁴5²7²11 ...)

2. Using only first two optimizations, the number of numbers A, found by our solution, is 10 471 (in the case of the number with maximal number of divisors)

3. Using only first two optimizations, the number of pairs of A and B, found by our solution, is 128 264 (in the case of the number with maximal number of divisors)

163E - e-Government

Solution summary: Aho-Corasick and finding the sum along a way in a tree of suffix links

Sample solution: 1415345 (author: arseny30)

We assume that the reader is familiar with the Aho-Corasick algorithm (http://en.wikipedia.org/wiki/Aho-Corasick)

Consider a trie of names and suffix links over it. For every vertex v one can calculate the number of names, ending in that vertex (end[v]).

Then, the "add name i" operation is end[v[i]] += 1, where v[i] is ending vertex of i-th name.

Similarly, "remove name i": end[v[i]] -= 1.

To answer a request "calculate how politicized the text is", one needs to know, that the suffix links form a tree. Once we move though the text and simultaneously through the trie with suffix links, we add the sum of all end[v[i]] along the path to the root of the tree of suffix links the politicization of the text.

Now, there's another problem: we need to calculate the sum of weights along a way to the root, the weights may change.

One can do it in the following way:

1. Move the weights from vertices to corresponding edges to vertices' parents

2. Build the Eulerian traversal of the tree, where the down-move will store positive weight of the edge and up-move will store its negation.

3. The sum along a path to the root if the sum on a segment of the Eulerian traversal (the endpoints are any entries of the vertices in the traversal).

A fast and short way to calculate the sum on a segment is Fenwick's tree.

Here's a solution running in O(|SumLen| * log) time and 26 * |SumLen| memory (the trie will not be compressed).