ruzana.miniakhmetova's blog

By ruzana.miniakhmetova, 11 years ago, translation, In English

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:

Problem "Special task"

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:

  • The first symbol of the string is not a letter. So one should multiply the answer by number of the arrangements of 10 figures for the number of different letters in the string.
  • The first symbol of the string is a letter. So one should multiply the answer by 9 and the number of the arrangements of 9 figures for the N - 1, where N is the number of different letters in the string.

    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.

    Problem "PE Lesson"

    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.

    Problem "Suns and Rays"

    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.

    Problem "EKG"

    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.

    Problem "Tidying up"

    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.

    Problem "Summer Homework"

    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 Fii-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.

    Prblem "Good substrings"

    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.

  • Tutorial of ABBYY Cup 3.0
    | Write comment?
    »
    11 years ago, # |
      Vote: I like it +25 Vote: I do not like it

    The problems were interesting enough! Thank you!

    »
    11 years ago, # |
      Vote: I like it +8 Vote: I do not like it
    Really nice problem set and really fast editorial. Solving small testcases is funny, that much better than staring at the screen and do nothing. 
    What is I(n) mean in "PE Lesson"? According to the recurrence, I(n) means the number of results for all 1, right? Thank you. 
    
    • »
      »
      11 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      First, consider the case that all people can only throw one time. Let's define the number of this cases of n people is I(n). The nth people have two possible ways to make loop.

      (1) He himself is a group. The number of this case equals I(n-1), because he has nothing to do with other people.

      (2) He and another one form a group. There are n-1 ways to choose another people, then these two person have nothing to do with others, so the number of this case (n-1) * I(n-2) So, I(n) = I(n-1) + (n-1) * I(n-2)

      Now Consider the case that there're some people can throw twice, there's no limitation to these people, so they can insert to any loop's any position. If a loop has n people, then there're n positions can be inserted. So the number of all positions is the number of people. And an addition is he doesn't insert to any loop but to form a new loop.

      Assume there're n people can throw only once, m people can throw twice, so the answer is (n + 1) * (n + 1 + 1) ... *(n + m — 1 + 1) * I(n) = I(n) * (n + m)! / n!

      • »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What does "loop" mean here?

      • »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Thank you for your detailed explanation. Why no limitation to these people can swap twice? I also cannot understand the exact mean of "loop", it will be highly appreciated that if someone can tell me.
        
        • »
          »
          »
          »
          11 years ago, # ^ |
          Rev. 2   Vote: I like it +14 Vote: I do not like it

          Assume there're 5 people ,consider the permutation [2, 1, 4, 5, 3].

          The first people's ball go to the second people.

          The second people's ball go to the first people .

          The third people's ball go to the fifth people.

          ...

          We can use a directed graph to describe the case: (please forgive my baoman style)

          And there're two loops in this permutation —— [1,2] [5,3,4]

          To insert a people to a loop, just break one edge and add two new edges.

          The limitation is only that a loop contains at most two people that can throw ball once, so the people who can throw twice can be inserted to any position.

      • »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        I completely know I(n) through your excellent explanation.But if you can explain the proof of l(n)*(n+m)!/n! in detail,I would be very grateful.

    »
    11 years ago, # |
    Rev. 8   Vote: I like it +25 Vote: I do not like it

    It seems that S(x)   =   F0   +   xAl   +   F1   +   xAl   +   1   +   …   +   Fr   -   l   +   xAr must be S(x)  =  F0  +  x  ×  Al  +  F1  +  x  × Al  +  1  +  ...  +  Fr  -  l  +  x  ×  Ar in the solution of "Summer Homework". And there are more typos because it uses Fx + 1 instead of Fx + 1.

    • »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      any hints on why S(x) = S(0)Fx-2 + S(1)Fx-1?

      • »
        »
        »
        11 years ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        This formula holds for all fibonacci-formed sequence a0, a1, a2, ..., an. We can prove this by induction.

        1. a2 = a0 + a1 = a0 × f0 + a1 × f1, so the formula holds for n = 2.
        2. a3 = a1 + a2 = a0 × f0 + a1 × (f1 + 1) = a0 × f1 + a1 × f2, so the formula holds for n = 3.
        3. For all 3 ≤ n, an + 1 = an - 1 + an = (a0 × fn - 3 + a1 × fn - 2) + (a0 × fn - 2 + a1 × fn - 1) = a0 × fn - 1 + a1 × fn.
    »
    11 years ago, # |
      Vote: I like it +2 Vote: I do not like it

    The inconvenience caused with the testing part was really frustrating. There was a time when I accidentally submitted a C solution while I had selected python, and I got to know after half an hour the mistake. Caused me a lot of rank loss. Anyways, nice problems and fast editorials.

    »
    11 years ago, # |
      Vote: I like it -52 Vote: I do not like it

    my submission no. 3872882 was judged correct during the contest but after the contest it was judged as skipped can u check into the matter . i am losing 30 points because of that.

    »
    11 years ago, # |
      Vote: I like it +1 Vote: I do not like it

    Suffix Automation is a good way to solve Prblem "Good substrings".It is very easy to implement and the code is short!

    »
    11 years ago, # |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Hi,

    Somebody could explain for me the "Tidying up" problem? :) I read this editorial and check some of solutions (e.g. 3873637 it is nice clean solution), but I don't see why this flow problem is equivalent with the original problem. Thank you..

    • »
      »
      11 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Well, let's notice an obvious fact that if we want to put a pair of shoes into two adjacent squares, it's never efficient to remove both old shoes and replace them with two new ones. So, we build a bipartite graph, in which we need to find a perfect matching (an edge taken into matching means that we've put a pair of shoes into this pair of adjacent squares). So, 0-weighted edges mean that we just leave both shoes on their original place, and 1-weighted edges mean that we remove one shoe (and replace it with another).

      • »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you for your answer! Why this is obvious fact? What is the mathematical explanation?

        • »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          Why do you make me think instead of you? :)

          Let's consider some facts.

          1. Layout of pairs of shoes is a perfect matching in a bipartite graph (seems to be obvious).
          2. If the shoes on the ends of an edge for a pair and we take this edge into matching, we can just do nothing (obvious).
          3. If the shoes do not form a pair, we need to move at least one shoe (obvious).
          4. If the shoes do not form a pair, we need to move at most one shoe (need to prove).

          Let's prove statement 4. Let's consider edges from matching as pairs (a[i], a[i + 1]). Since we have exactly two shoes of each type, these pairs can be split into cycles of the following form: (a[1], a[2]), (a[2], a[3]), ..., (a[n — 1], a[n]), (a[n], a[1]). So, you can fix either the first element of each pair, or the second one, and move the remaining element. So, for each edge from matching that connects shoes of different types, we need to move exactly one shoe. Q.E.D.

    »
    4 years ago, # |
      Vote: I like it 0 Vote: I do not like it

    Can anybody plz explain why my solution gets RTE when i used long long int but gets AC when i used int data type...? i submitted same solution in different versions of C++ language... it's not the first time i faced this kind of problem... my solution link--> https://codeforces.net/contest/316/my