Dear all, ABBYY Cup 3.0 online-part is over!
Thank you for participating! We are sorry for inconveniences with testings. MikeMirzayanov has informed us about plans to buy new testing machins. So we hope that there won't be such cases in the future.
Solutions are the following:
It was one of the easiest problems in the contest. A solution consists of considering several cases. The initial answer equals one. Firstly, let’s note that if there is a "?" in a string, so the number of every possible codes increases in 10 times. With the exception when "?" is at the beginning if a string so the number of every possible codes increases in 9 times. Next let’s consider the case when the letters are found in the strings. There are two cases here:
It is no need to realize long arithmetic here. As all the operations (with the exception of multiplying be 10 because of the "?" can be done by standard arithmetic. For multiplying by 10 you can simply output the number of required zeros.
To begin with the term “order of balls” conforms to commutation. And the constraint to number of kicking a ball conforms to the number of transpositions. The problem is to calculate the number of “suitable” commutations. The commutation is “suitable” means the following: if to divide the commutation into the loops then every loop will consist of no more than two elements with the maximum number of inversions equals 1. So you can solve the problem with the help on dynamic programming. For this purpose the function f(a, b) should be calculated, where a — is the digit 1 and b — is the digit 2 used in the problem. f(a, b) is the number of “suitable” commutations. One should note here that f(a, b) can be calculated using the following formula: 
, where I(n) = I(n - 1) + (n - 1) * I(n - 2) You can prove it yourselves.
This problem has different solutions. Let’s consider one of them. Denote the initial image as T. There are two operations for T: erosion and delation. Erosion is an operation of substitution of all the pixels which refer to image and are contiguous with pixels of background for the pixels of background. Dilation is an operation which is similar to inverse erosion: we substitute the pixels of background which are contiguous with pixels of image for the pixels of image. For determination neighbouring pixels you can use 4-connected neighborhood. The beams will vanish and the sun will stay as only a circle after applying erosion operation to T for several times. Then we should apply dilation operation for several times. Note that number of applied dilation operation should be more than number of applied erosion operation. Denote the obtained image as P. Then let’s consider initial image T and sort out connected components corresponding to the suns. After that you should sort out parts corresponding to the beams. How do it? The pixels which are in the image T and which are not P are corresponding to the beams.
Firstly one should sort out the chains in the waiting line. The chain is a sequence of the beavers which stay one after another. After that the length of all the chains and the chain in which are Smart Beaver are known. Secondly one can simply apply methods of dynamic programming for further calculation.
Let’s move from initial matrix to the bipartite graph. The matrix elements (i, j) for which i + j are even should be place to one part, the matrix elements (i, j) for which i + j are uneven should be place to another part. The edges are corresponding to squares which are situated side by side. After that let’s weigh the edges. The edges which connect equal elements of matrix have weights 0, for unequal elements – weight 1. After that the problem is reduced to finding of the maximum independent edge set with minimal weight. Substantiation of above-stated is following: an answer to the problem represents a partitioning of initial matrix for pairs. Note that for any partitioning minimal number of changing matrix elements corresponds to the number of pairs on unequal elements. So in the optimal partitioning the number of pairs of equal elements is maximum. For solving minimum-cost flow problem is needed to use some effective algorithm. For example, Dijkstra algorithm with heap adding conversion of edges weights from Johnson's algorithm.
To solve this problem one should use segment tree. Let’s consider line segment [l;r] on this tree. For this purpose let’s introduce S(x), where x is integer. S(x) = F0 + xAl + F1 + xAl + 1 + … + Fr - l + xAr, where Fi – i-th Fibonacci number, Ai – the array which consists of even numbers. One should note that S(x) with x = 0, 1, 2… are similar to Fibonacci numbers. Id est S(x) = S(x - 1) + S(x - 2) for x ≥ 2. This means that for every line segment [l;r] one should memorize S(0) and S(1). To calculate S(x) for x ≤ 2 one could use the formula: S(x) = S(0)Fx - 2 + S(1)Fx - 1. So solving 2-type query is reduced to calculation no more than 
values if S(x) for different segment lines. The 1-type modification can be done by walking down the tree. For 3-type query one should use additional information in the tree and partial sums of Fibonacci number.
For a start one needs to learn to compare quickly any two substrings, which could be taken from the source string or from one of the strings, which corresponds to the rules. It can be done, for example, with the help of suffix array, that contains every possible input strings. After construction of such an array and calculation of LCP (longest common prefix) values the problem of comparison of two substrings reduces to computation the number of identical characters and comparison the characters, that come after identical blocks. Computation the numbers of identical characters are equivalent to a problem of calculation of minimum on the interval of an array of LCP values. Because the LCP array does not change, efficient resolution of such requests can be earned with help of RMQ algorithms. Thus, in time O(1) we can compare any two substrings. Note, that time of precomputing depends on algorithms used for suffix array building and construction of RMQ.
Further we need to find the number of entries of a certain substring from the source string into the string of one of the rules. It can be done with help of binary search of string of rule in suffix array. Note, that we are able to compare two substrings in time O(1). Therefore complexity of search of the number of entries of a substring into a string will be 
.
Now let’s consider a certain suffix of a source string. We know its LCP with the previous suffix. This is the lower limit for the number of the characters, which we are considering in this suffix. Note, that the number of entries of a certain prefix of considered suffix monotonously depends on length of this prefix. Therefore for each rule one can define by binary search what minimum and maximum length of a prefix can be, to fit this prefix for the rule. After, it is essential to cross all received intervals. It is likely that using another structures of data on strings can get a simpler solution. Technical realization of considered solution is fairly laborious.
It will be 10 training days. The school includes lectures by Saratov state university coaches, joint trainings, problems tutorials and topical workshops. The curriculum is designed for younger university students who aspire to achieve high results at programming competitions. Official language is Russian.
