337A - Puzzles

First, let's sort the numbers f[i] in ascending order. Now assume that the smallest jigsaw puzzle which the teacher purchases consists of f[k] pieces. Obviously, she should buy the smallest n puzzles which are of size f[k] or greater to minimize the difference. These are the puzzles f[k], f[k+1], ..., f[k+n-1] (this is not correct when f[i] are not distinct and f[k]=f[k-1], but such cases can be skipped). The difference between the greatest and the least size of the puzzles in such set is f[k+n-1]-f[k].

To choose the optimal f[k], we can test every k between 1 and m-n and pick the one producing the least difference. The full algorithm is as follows:

read(n, m, f[1..m])
sort(f[1..m])
best = INFINITY
for k = 1 to m-n
  best = min(best, f[k+n-1] - f[k])
print best

337B - Routine Problem

Suppose that the width and height of the screen are W and H correspondingly. Since W:H = a:b, we have H=W*b/a. Similarly, the width and height of the film frame w and h are related as h=w*d/c. Imagine that Manao stretches/constricts the frame until it fits the screen horizontally or vertically, whichever happens first. There are three cases to consider: the horizontal to vertical ratio of the screen is less, equal or more than the corresponding ratio of the frame.

In the first case (a/b < c/d) the stretching process ends when the frame reaches the same width as the screen. That is, the frame will enlarge in W/w times and its new width will be W. Thus, its new height is h*W/w = w*c/d * W/w = W*d/c. We are interested in the ratio of unoccupied portion of the screen to its full size, which is (screen height - frame height) / (screen height) = (W*b/a - W*d/c) / (W*b/a) = (bc-ad)/bc.

In the second case (a/b > c/d) the process ends when the frame reaches the same height as the screen. Its height will become H and its width will become w*H/h = w * W*b/a / (w*d/c) = W*b/a * c/d. The unoccupied portion of the screen's horizontal is (W - W*b/a * c/d)/W = (ad-bc)/ad.

In the third case, the frame fills the screen entirely and the answer will be 0.

All that's left is to print the answer as an irreducible fraction. We need to find the greatest common divisor of its nominator and denominator for this. It can be done using Euclidean algorithm or just through trial division by every number from 1 to q. Since q is no more than a product of two numbers from the input and these numbers are constrained by 1000, we need to try at most million numbers in the worst case.

337C - Quiz

Assume that Manao has doubled his score (i.e. gave k consecutive correct answers) exactly X times. Then the least possible score is obtained when this doublings happen in the beginning of the game, i.e., when he answers the first X*k questions and never manages to answer k consecutive questions after that. The correctness of this statement follows from the following: for any other scenario with X doublings, all of these doublings can be moved into the beginning and the total score will not increase. Hence, for X=1 Manao's minimum score is k*2+m-k: he answers k consecutive questions, the score doubles, then he answers m-k questions. For X=2 the minimum possible score is (k*2+k)*2+m-2*k, for X=3 — ((k*2+k)*2+k)*2+m-3*k. For the general case, a formula (2^1+2^2+...+2^X)*k + m-X*k = (2^(X+1)-2)*k + m-X*k is derived.

The abovementioned observation shows that the minimum score grows monotonically when X is increased, so all we need is to find the minimum feasible X. It should satisfy the inequalities X*k <= n and X + (n - n mod k) / k * (k-1) + n mod k >= m. More on the second inequality: Manao answered the first X*k questions, thus there are n-X*k left. Now he can answer at most k-1 question from each k questions. If k divides n-X*k (which is the same as k divides n), the inequality becomes X*k + (n-X*k) / k * (k-1) >= m, but the remainder complicates it a bit: X*k + (n - X*k - (n - X*k) mod k) / k * (k-1) + (n - X*k) mod k >= m. This formula can be simplified to the one written earlier. So, the minimum X is equal to max(0, m - (n - n mod k) / k * (k-1) - n mod k). You'll need exponentiation by squaring to compute the score corresponding to this value of X. Thus, the overall complexity of this solution is O(log(n)).

337D - Book of Evil

Obviously, in graph theory language our problem is: given a tree with n vertices, m of which are marked, find the number of vertices which are at most distance d apart from each of the marked vertices.

Let us hang the tree by some vertex r, that is, assume that it is a rooted tree with root in vertex r. Let us also rephrase the condition imposed on sought vertices: we need to count such vertices v that the maximum distance from v to a marked vertex is at most d.

For any inner vertex v, the marked vertex which is the farthest from it is either in the subtree of v or outside it — in the latter case the path from v to the farthest marked vertex traverses the parent of v. Using this observation, we can recompute the distances to the farthest marked vertices when transiting from a vertex to its child.

First, we will compute the distance from every vertex v to the farthest marked vertex within the subtree of v. Let us call this distance distDown[v]. The values of distDown[] can be computed in a single depth-first search: for each leaf of the tree this distance is either 0 (when the leaf is marked) or nominal negative infinity (when the leaf is not marked), and for each inner vertex v distDown[v]=max(distDown[child1], distDown[child2], ..., distDown[childK])+1, where childi are the children of v.

Now we will compute the distances from each vertex to the farthest marked vertex outside its subtree. Let's denote this distance with distUp[v]. We will use DFS again to compute values of distUp[]. For the root, distUp[r] is equal to nominal negative infinity, and for any other vertex v there are two cases: either the farthest marked vertex is located in the subtree of v-s parent p, or it is even "farther", i.e., the path to it traverses vertex p-s parent. In the first case, the distance from v to such vertex is equal to max(distDown[sibling1], ..., distDown[siblingK])+2, where siblingi are the brothers (other children of the parent) of vertex v. In the second case, it is equal to distUp[p]+1. Thus, distUp[v] is equal to the maximum of these two values. Note that you need to be clever to perform the computations in the first case in overall linear time. For this, you can find the maximum max1 and second maximum max2 of values distDown[sibling1], ..., distDown[siblingK]. After that, when distDown[v] < max1, we have max(distDown[sibling1], ..., distDown[siblingK])=max1, otherwise we have distDown[v] = max1 and max(distDown[sibling1], ..., distDown[siblingK])=max2.

After computing distDown[] и distUp[], it is easy to derive the answers: it is the count of such vertices v that distDown[v] <= d && distUp[v] <= d.

You can check 4302127 for an implementation of the described approach.

337E - Divisor Tree

Let us first show that in an optimal divisor tree only the root or a leaf can hold a value other than one of a[i]. Suppose that we have an inner vertex different from the root which holds a number X not equal to any of a[i]. Then we can exclude this vertex from the tree and tie its children to its parent without violating any of the tree's properties.

Hence, our tree consists of the root, vertices with numbers a[i] tied to each other or to the root, and leaves, which are tied to vertices with numbers a[i] and contain these numbers' prime factorizations. The exception is the case when one of a[i] is written in root itself, and the case when some a[i]-s are prime themselves. Also note that in general case it's easy to count how many leaves the tree will have. This count is equal to the sum of exponents of primes in prime factorizations of those a[i]-s which are the children of the root.

Since N <= 8, we can build all divisor trees which satisfy the observations we made. Let's sort numbers a[i] in descending order and recursively choose a parent for each of them from the vertices already present in the tree. Of course, tying a number X to some vertex v is only possible if the product of X and the numbers in children of v divides the number in v itself. For a[1], we have a choice — we can make it the root of the tree or a child of the root (in this case the root will hold a nominal infinity which is divisible by any number). For every next a[i], the choice is whether to tie it to the root or a vertex containing one of the previous numbers. Therefore, we only consider O(N!) trees in total.

You can check 4302171 for an implementation of this idea.

338D - GCD Table

Observation 1. If the sequence a occurs in table G, then it should occur in row i = LCM(a[1], ..., a[k]). The proof follows. It is clear that theoretically it may only occur in rows with numbers which are multiple to i, since the row number should divide by each of a[index]. Consider some a row with number i*x, where x>1. The rows i and i*x differ only in such elements j that i*x and j both divide by some p^q (where p is prime) which does not divide i (hence, G(i*x, j) is divisible by p^q). But none of the a[index] may divide by such p^q, since then i would be also divisible by it. Therefore, if a occurs in row i*x, then it does not intersect with index j. Since it can only reside on indices where i and i*x coincide, checking only the i-th row is enough. It also clear that if i > n, the answer is NO.

Observation 2. The sought index j should satisfy the following modular linear equations system:

j = 0 (mod a[1])
j + 1 = 0 (mod a[2])
...
j + l = 0 (mod a[l + 1])
...
j + k - 1 = 0 (mod a[k])

<=>

{j = -l (mod a[l + 1])}

In other words, j + l must divide by a[l+1] for each l=0..k-1.

According to Chinese Remainder Theorem, such a system has a solution iff for each pair of indices x, y (0 <= x, y <= k-1) we have -x = -y (mod GCD(a[x+1], a[y+1])). Let's denote L = LCM(a[1], ..., a[k]). If the system has a solution, then it is singular on interval [0, L) and all the other solutions are congruent to it modulo L. Suppose that we have found the minimum non-negative j which satisfies the given system. Then, if a occurs in G, it will start from the j-th element of the i-th row. Theoretically, it may begin at any index of form j+x*L, x>=0, but since i = L, we have G(i, j+X*L) = GCD(i, j+X*i) = GCD(i, j). So it is sufficient to check whether the k consecutive elements which begin at index j in row i coincide with sequence a. It is also clear that when j > m-k+1, the answer is NO.

Finally, let's consider how to solve a system of modular linear equations. We can use an auxiliary method which, given r1, m1, r2, m2, finds minimum X such that X = r1 (mod m1) and X = r2 (mod m2), or determines that such number does not exist. Let X = m1*x + r1, then we have m1*x + r1 = r2 (mod m2). This can be represented as a Diophantine equation m1*x + m2*y = r2-r1 and solved using Extended Euclidean Algorithm. The least non-negative x, if it exists, yields the sought X = m1*x + r1. Now this method can be used to find the minimum X1 which satisfies the first two equations. After that, we can say that we have a system with k-1 equation, where the first two old equations are replaced with a new j = X1 (mod LCM(a[1], a[2])), and repeat the same procedure again. After using this method k-1 times, we obtain the solution to the whole system.

Also note that the proposed solution does not require long arithmetics: — The computation of LCM(a[1], ..., a[k]) can be implemented with a check before each multiplication: if the result will become larger than n, the answer is NO; — When it comes to solving the system of equations, we already know that L <= n <= 10^12, thus all the intermediate moduli will also obide to this constraint; — The Extended Euclidean Algorithm can find a solution in the same bounds as its inputs, so it will also use numbers up to 10^12.

The overall complexity of the algorithm is O(k logn).

338E - Optimize!

Decyphering Manao's pseudocode, we unearth the following problem: you are given arrays a[1..n] and b[1..len] and a number h. Consider each subarray of a of length L. Let us call it s. Count how many of them have the property that the elements of b can be shuffled in such a way that each sum s[i]+b[i] (1<=i<=L) is at least h.

First, let's solve a problem for one subarray. That is, we need to determine whether the elements of two arrays s and b can be matched in such a way that each sum is h or more. We can do the following: for each element of s, find the least element of b such that the two's sum is at least h, and erase the corresponding element from b. If we managed to pair each of the elements from s, then the arrays hold the property. Note that the elements of s can be processed in any order. If both s and b are sorted, then the idea described can be implemented in linear time.

We can not achieve better complexity when considering each subarray separately, so we will try to solve the problem for several subarrays at the same time. Suppose that b is already sorted. We choose some X < len and consider a subarray a[i..i+X-1]. Let's process all the numbers from this subarray, i.e., for each of them find the least b[j] which pairs up with this number and erase it from b. The whole processing can be done in time O(n) if we have a sorted version of a and the corresponding indices computed beforehand.

Now we can find the answer for every subarray s of length len which begins in segment [i-Y, i] using O(YlogY) operations, where Y=len-X. For this, we just take the Y elements which are in s but not in a[i..i+X-1] and process them against the numbers left in b. If each of them has been paired, then subarray s holds the required property, otherwise it does not. Moreover, since the subarrays we consider are overlapping, we can optimize even further and obtain amortized O(Y) complexity per subarray. To understand this, note that for processing a subarray in O(Y) time we only need to obtain its sorted version (to be more specific, the sorted version of the portion which does not overlap with a[i..i+X-1]). For the leftmost subarray we consider, we can sort its elements in usual way. For every next subarray (which differs from its predecessor in exactly two elements) we only need O(Y) operations to obtain its sorted version by updating the information from the previous subarray. Thus we have complexity O(YlogY + Y^2) of processing Y segments in total, which gives O(Y) per segment on average.

Now let us take a look at the full picture. To process all subarrays of length len, we need to use the method given above for each of the segments a[Y..Y+len-1], a[2Y+1..2Y+len], a[3Y+2..3Y+len+1], .... Therefore, we have O(N/Y) iterations of algorithm with comlexity O(N+Y^2). We need to find a value of Y that minimizes N*N/Y + N*Y, which is Y=~sqrt(N). The overall complexity is O(Nsqrt(N)). However, we need to consider the case len < sqrt(N) separately, since then Y = len - X < len. In this case, the problem can be solved in time O(N*len) with ideas similar to those described above.

You can check the implementation of this idea in 4302344.

P.S. The statement of the "problem" that Manao is solving actually contains a Georgian fairy tale. You can copy almost the same text from here and try to guess what he tale is about :)