### gojira's blog

By gojira, 8 years ago, translation, ## 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, 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, ..., 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)
j + 1 = 0 (mod a)
...
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, ..., 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, a)), 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, ..., 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 :) Tutorial of Codeforces Round #196 (Div. 2) Tutorial of Codeforces Round #196 (Div. 1)  Comments (37)
 » Problem D(Book of Evil), I find two marked node(node a, node b) that the distance between them is longest.Then count the shortest distances from these two node. Last, for a node c, if shortest[a][c] <= d && shortest[b][c] <= d, we add 1 to ans.
•  » » Could you please explain why this works?
•  » » » 8 years ago, # ^ | ← Rev. 3 →   This is similar to the diameter-finding algorithm in a tree. Suppose there are nodes for which dist(a,c) < dist(c,e) and dist(b,c) < dist(c,e), where A, B and E are marked, and dist(a, b) >= dist(b, e), and dist(a, b) >= dist(a, e).Let's root the tree at A. We have two cases:1) dist(a, lca(c,e)) >= dist(a, lca(c,b)) dist(c,e) > dist(c,b) -> dist(a, e) + 2*dist(a, lca(c,b)) > dist(a,b) + 2*dist(a, lca(c,e)). dist(a, e) > dist(a, b). Contradiction: in this case A->E is longer than A->B.2) dist(a, lca(c,e)) < dist(a, lca(c,b))dist(c, e) > dist(a, c) -> dist(a, e) > 2*dist(a, lca(c,e)) dist(b, e) = dist(a, b) + dist(a, e) — 2*dist(a, lca(b,e)) Then we have lca(b, e) = lca(b, c), so dist(b,e) > dist(a, b) + dist(a, e) — 2*dist(a, lca(c,e)) dist(b,e) > dist(a, b). Contradiction. B->E is longer than A->B.
•  » » » » 8 years ago, # ^ | ← Rev. 5 →   Thanks for the explanation. However it took much time from me to understand the formulas. Let me supplement it with a picture. C and E must lie inside the circles. Otherwise they would form a new diameter (with A or B). If they lie inside, they cannot form longer distances. C will always be farther from A or B than from E.UPD: In fact non-marked vertice C may lie outside the circle, as our diameter is formed by marked vertices only. However E inside the circle is sufficient. Image updated.
•  » » » » » Yes, that's the intuitive idea, but the circle is not exactly as drawn. For instance, take the midpoint of A-B and extend E to the same height as B. That is still a valid configuration. Another way to see it: if A and B are equivalent, shouldn't the valid region be symmetric with respect to the midpoint?
•  » » » » » » The circle touches the midpoint only accidentally. It is drawn as follows: let D be lca(E, B). D is the circle's center and its radius is distance DB. Why B? Because B is closer. Actually I should also draw another circle with radius DA, but since it's bigger (in this case), I skipped it. I draw a circle based on the closer point — A or B, because this one is smaller.Of course there are other cases, but for E starting at this point — I think the circle is correct. Am I missing something?
•  » » For implementation refer https://codeforces.com/contest/337/submission/84688797
 » Problem B: If the two ratios can be made exactly same, answer would be 0 and hence we can print 0/x, for any x>0 [as per problem statement:"p/q", where p is a non-negative integer, q is a positive integer and numbers p and q don't have a common divisor larger than 1.] but they accepted only 0/1. This is not fair. 0/x, for any x>0 is a proper reduced form. Wasted an an entire hour on this.
•  » » 0 divides by any number, so for any p>1, "0/p" has a common divisor larger than 1.
 » Why this entry is in Codeforces main page?
•  » » Why there is no response?
 » Thanks for ur nice work.All the problems are interestring and easy to understand.
 » The description of last problem solution is complicated.
 » 8 years ago, # | ← Rev. 3 →   Hello, int problem 337E, I wonder why the numbers should not be same?
•  » » This is just for the sake of simplicity of the statement. I.e., if duplicate numbers are allowed, you can either ask for a tree that contains the numbers at least as many times as they are given in the input, or just ask to ignore the duplicates. The problem does not become more interesting in any case.
 » 6 years ago, # | ← Rev. 3 →   Edit: Got my mistake.
 » 6 years ago, # | ← Rev. 3 →   337D — Book of EvilI use a different idea. My idea:1.Find two settlements a and b which are affected and dis(a,b) is maximum among all affected settlements.It can be easily done by diameter of tree. Evil has got a damage range d. So how many nodes can be visited from a by distance d and from b by distance d.Now the number of common nodes which can be visited from a and b by distance d is answer.It can be done easily by dfs and colouring.
•  » » Can you prove why your method is correct? There can be multiple possible candidates for (a,b) ?
 » Is there a way to solve Div2 A(337A) using 2-D dp?If yes, can someone explain it to me please?
 » In problem D can someone elaborate on how the two cases were approached while calculating distUp[]!
 » In problem 337A how is the difference of greatest and smallest element obtained as F [k+n-1]-F[k]?
•  » » After sorting the array, the greatest value is F[k+n-1], and the smallest value is F[k]. These two result in the greatest difference.
•  » » » Why this tagged as dp problem. Whats the Optimal substructure ? What are the intersecting sub problems?
•  » » » 2 years ago, # ^ | ← Rev. 2 →   .
 » why the tag of A probelm are dp and graph matching...?????? thanks in advance .....
 » In 337A why are we taking m-n? Shouldn't that just give the extra puzzles in the shop?
 » I really spent an hour finding the bug in my code in 2C and then I realized that it was 10e9+9 and not 10e9+7.
 » Didn't notice in Div2E(Divisor Tree) that $n \le 8.$ I misread it as $n \le 12$ and found an $O(4^n)$ solution. This approach doesn't seem to have been discussed in the comments. I never faced a problem before that required iterating over subsets of subsets of subsets, so I think it's worth a mention. We start with the following easy observation copied from the editorial: In an optimal divisor tree only the root or a leaf can hold a value other than one of $a[i].$ 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. Let's consider each subset of the set of $n$ numbers as a mask. Let, dp[up_mask][down_mask], where up_mask and down_mask are disjoint, be true if there exists a tree where the numbers corresponding to up_mask are direct children of the root and the numbers corresponding to down_mask lies in subtrees of the up_mask numbers. Now, to evaluate dp[up_mask][down_mask], we split up_mask into two smaller sets,up_lsb = least significant bit of up_mask, andup_rest = up_mask ^ up_lsb. Then, we iterate over all possible ways to split down_mask into two partitions down_mask1 and down_mask2, and check if we can put down_mask1 under up_lsb and down_mask2 under up_rest by checking if both dp[up_lsb][down_mask1] and dp[up_rest][down_mask2] are true. To get our final answer, we first set our answer ans as the sum of the exponents in prime factorizations of the given numbers. We then iterate over all subsets of $[(1 \lt\lt n) - 1]$ as up_mask and set down_mask = $[(1 \lt\lt n) - 1]\ \oplus$ up_mask. If dp[up_mask][down_mask] is true, then we consider it as a candidate answer and subtract the sum of exponents in prime factorizations of the down_mask numbers from ans. Total states in the dp is $O(3^n)$ and considering transitions, time complexity becomes $O(4^n).$ And the memory complexity is $O(4^n)$ for dp. Here is a submission using this idea.
 » In 337C Quiz Can anyone please explain how X*k + (n-X*k) / k * (k-1) >= m= X + (n - n mod k) / k * (k-1) + n mod k >= m whereas I reduced it to X+(n/k)*(k-1)>=mwhich gives WA. Thank you.
 » Hey guys,I tried this problem but somehow I am facing TLE on case#4.I am pretty sure that my code is having O(n) or O(V) time complexity.Please help me figure out where exactly am I going wrong. Link to my code:https://codeforces.com/contest/337/submission/80845068 Thanks in advance
•  » » 13 months ago, # ^ | ← Rev. 2 →   Refer this.
 » In Div2-A Book of Evils. Can someone please explain why we use neg infinity and not positive infinity. because I'm confused by the fact that farthest marked node will be too far(i.e. positive inf).
 » Anyone solved 337A - Puzzles using graphs??
 » 9 months ago, # | ← Rev. 2 →   337C,How did the final formula arrived?from: X*k + (n — X*k — (n — X*k) mod k) / k * (k-1) + (n — X*k) mod k >= mto: X + (n — n mod k) / k * (k-1) + n mod k >= mHow did it arrived?Can anyone explain.Thanks...
 » really helpful
 » How can we use binary search to find x? Although I understood how does the formula work, it's true that most of the times binary search is easier to come up with than the formula.Thanks.
 » Can Problem D ( Book Of Evil ) be solved using centroid decomposition ??