natalia's blog

By natalia, 13 years ago, translation, In English
Problem A

To get the maximal possible result you have just to sort summands in non-decreasing order by coefficients (counting coefficients with preceeding signs + and -). You should not pay attention to 'a++' or '++a'! The question is: why is it true? 

First, consider an expression with only 'a++'. Then our assertion is obvious: it is better to multiply 'a' by small coefficients when it has small value, and by large coefficients, when it becomes larger. The same also takes place in case of negative coefficients or a-value. Of course, it is not a rigorous proof. I hope you will think on it if you haven't get it yet.

Second, consider the expression k * a +  +  + k *  +  + a, where k is some coefficient equal for both summands. Let initial value of 'a' equals to a0. Calculating the value of the expression both ways, we obtain: k * a0 + k * (a0 + 2) = k * (a0 + 1) + k * (a0 + 1). So in this case the order is immaterial.

Third, let us have the expression k * a +  +  + l *  +  + a, where k and l are two distinct coefficients. This expression can have two different values: k * a0 + l * (a0 + 2) and k * (a0 + 1) + l * (a0 + 1). The first value is greater than the second one if and only if k < l. We can deal with the expression k*++a+l*a++ analogously.

Thus if we have two succesive summands with the same coefficient, we may swap or not to swap them. If we have two succesive summands with distinct coefficients, we must put the summand with a smaller coeficient first. Applying these considerations while it is necessary, we get a sequence of summands sorted by coefficients. 

Porblem B

For this problem, the greedy solution is acceptable. Process given numbers consequently until 1 is found. Then continue to process searching for 2, then for 3, etc.

Problem C

The authors solution takes O(n2) time and O(n2) memory. Solutions with time and O(n) memory are also acceptable.

Let us reformulate the problem. Given a set of segments on a line, and the task is to find the largest subset such that segments in it don't intersect ``partially''. Two segments [a, b] and [c, d] intersect partially, if, for instance, a < c < b < d.

Take all the ends of the given segments, sort them, and compute the dynamics: dl, r is the largest possible size of such subset that segments in don't intersect partially and located between the l-th end and the r end (in sorted order), inclusively. We want to compute dl, r having already computed di, j for all l ≤ i ≤ j ≤ r, but [i, j] ≠ [l, r]. First put dl, r = dl + 1, r if we don't take segments with the left end in l. Now process the segments with the left end in l. If the segment [l, r] exists, we undoubtedly take it to our set. If we take another segment, say, [l, i], where i < r, look at segments [l, i] and [i, r] (we have  answers for them already computed) and try to update dl, r. The asymptotics is O(n2), because  the total number of left ends is O(n). Then you have to output the certificate, i.e. the optimal set itself. It can be done in the standard way.

Problem D

The flies can NOT see each other iff they are in opposite vertices. You may use multiple ways to check this. For instance, you can check the Manhattan distance |x1 - x2| + |y1 - y2| + |z1 - z2| = 3 or the Euclidian distance . You can check if all three coorditanes are distinct (x1 != x2) && (y1 != y2) && (z1 != z2), or just (x1^x2)+(y1^y2)+(z1^z2) == 3!

Problem E

The number of ways to put b items into a boxes is, of course, ab. So we have an acyclic game for two players with positions (a, b) for which ab < n. Unfortunatly, there exists an infinite number of such positions: a = 1, b is any. But in this case, if 2b ≥ n, it is a draw position, because the only way for both players (not leading to lose) is to increase b infinitely. 

Another special case is a position with b = 1 and rather large a. Namely, if , there is also only one move from this position - to increase a. If a = n - 1 the position is losing, if a = n - 2 it is winning, for a = n - 3 it is losing again and so on.

Thus we have two kinds of positions to deal with them specially. The number of other positions is not very large, and you can compute the standard dynamics for acyclic games for them.

Problem F

The simple modelling of frog's jumps works too long, because n can be 109. The right solution is to count for each frog a number of smashed mosquitoes by checking divisibility of numbers of hills with mosquitoes by di.

Problem G

What can I say about problem G? You should parse a given function and calculate its value for all values of n. Of course, it is impossible to do it just implementing the recursion, because this can work too long (see example with Fibonacci sequence). So you should use dynamic programming.

Problem H

You have to calculate all products i * j, and output them in the system of notations with radix k.

Problem I

Consider only the part of the graph reachable from 1. The task is to find the largest number t, such that a chosen set of vertices is reachable only at moments divisible by t. Suppose we have built  such a set S0. Look at sets S1, S2, ..., St - 1 of all vertices reachable at  moments having remainders 1, 2, ..., t - 1 modulo t, respectively. One can easily check that these sets are disjoint, and their union coinside with the set of all reacheble vertices. Clearly, that the edge from u to v can exist only when u and v belong to consequetive sets, i.e. , , k + 1 is taken modulo t.

For each vertex v, find a distance dv from 1 to v (if there is multiple paths, choose any, for example, by dfs). If the edge exists from u to v, it must be . By analyzing all the edges, we come to the conclusion that the optimal value of t equals to the greatest common divisor of the numbers |du + 1 - dv|. To find the set S0 is not very difficult now.

Problem J

The simplest solution is to find two numbers l and r - the length of the longest common prefix and the length of the longest common suffix of two strings, respectively. If l + 1 < n - r then there is no solution. Here n is the length of the first string. Otherwise we should output positions from max(n - r, 1) to min(l + 1, n).

Problem K

Problem K has a great number of different solutions, so I'm surprised that there was a lack of them during the contest. Solutions with time O(k4) and even some O(k5) solutions with optimization were acceptable, but KADR describes even better solution in O(k3) (http://codeforces.com/blog/entry/793).

Here are some jury ideas of this problem. First, let us compress the coordinates. Choose a labeled point in each object and compute by the standard dynamics the number of such labels in each rectangle. It takes O(k4) to process all possible rectangles. The problem arises that a rectangle may contain a valid number of objects, but contain some objects not completely. To prevent this, we can check the borders. They are segments parallel to the coordinate axes, and their number is O(k3). So we can precalc for them if they are valid or not comparing them with each object. Then we have to come back to uncompressed coordinates.

The following solution is O(k5), and it uses the limitation on the number of objects (3) inside the rectangle. Process all the triples of objects (the same, of course, with pairs and single objects). Fix a triple, and change it by a single big object. Then move from the resulting object up (and then down), and check if a row above (or below) can be included in a striked rectangle. For each row we find a longest segment [l, r], which contains the current big object and doesn't contain others. Using this information, one can easily calculate the total number of rectangles that contain the current triple. 
  • Vote: I like it
  • +9
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What is the test 12 of Problem A?
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
So what is the test 8 of Problem C?