ruzana.miniakhmetova's blog

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

Hi everyone!

For three years ABBYY Cup finalists have been meeting for ABBYY Open Day at the ABBYY Moscow office (Headquarters) in summer. This year hasn’t been an exception. As an organizer I will tell you about ABBYY Open Day 2013 which took place on July 17th.

It should be noted that it was rainy all the days before the contest day. We were very concerned: we have announced the entertainment which was strongly depending on the weather. Evidently the Universe wanted to see the outdoor part of the Open Day and decided not to spoil the weather by rain. The day began with breakfast and watching a funny video with a promising name “The truth about ABBYY”.

At 10:40 AM the contest started. For me as an organizer this is nice time. There is silence in the room, participants solve problems, I can relax for a moment watching the results and rooting for my favorites. In two hours we got the final standings. In particular, I want to congratulate with great results Mimino, who was the only non-speaking Russian participant. Every ABBYY Open Day cannot take place without the talk about the company. So, after dinner the participants met the CEO of ABBYY Sergey Andreev. Then our technical consultant for Compreno products Alexander Kostuchenko demonstrated achievements of ABBYY R&D in computer linguistics.

We’ve had a tour on the office where the participants managed to see how the working process of programmers is organized. At the end of the official part we’ve had the most pleasant event, the awarding. This year all the winners could get the gift from Smart Beaver himself, the main character of all ABBYY Cup problems. Next the unofficial part of the day began. It was the quest in the centre of Moscow. All the participants divided in teams, got the rules and the tasks and scattered throughout Moscow. In order to find the finish line the teams should have answered all the questions about Moscow sights or they could drop the quest at any time by calling us. However, nobody wanted to give up. Imagine how hard these tasks were for Mimino. We translated the rules especially for him and provided a translator to his team.

At 10 PM the teams started to gather at the finish in one of the Moscow’s anticafe. We have been waiting for them with pizza, salads and Smart Beaver! Our ABBYY Open Day has ended. We are very happy that there are participants who visit us every year. And this year we have had one international participant. It was nice to meet everyone. See you next year!

Server returned HTTP response code: 500 for URL: https://get.google.com/albumarchive/pwa/114842746780416406882/JInSLJ?authkey=Gv1sRgCLPuzoHEm4X_YQ

Read more »

 
 
 
 
  • Vote: I like it
  • +166
  • Vote: I do not like it

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

Hello!

ABBYY Cup 3.0 is finished! Many thanks to everyone: participants, people who created and prepared problems and etc! The post about ABBYY Open Day will be later but now let's consider finals' solutions:

Problem A

Claim: If the walk starts from tree i and ends at tree j, then we need to cut down all trees before i, all trees after j and all trees with negative esthetic appeal between i and j. In order to solve subproblem A1 we could use the claim for each pair of trees with equal aesthetic appeal and choose the maximum; the constraints allowed to do this either at O(n2) or O(n3). In order to solve subproblem A2 we could use the following claim: whichever is the number of trees with equal esthetic appeal, we are always better off if we consider only a pair of the leftmost and rightmost of such trees. Then the number of the pairs of trees considered is reduced from O(n2) to O(n). Then we may proceed with either taking partial sums or calculating a sum on the interval.

Problem B

In order to solve subproblem B1 we may emulate the behavior of Beavershave as it is described in the problem. In order to solve subproblem B2 it is sufficient to store a raised unity-flag for each terminal beaver, where terminal beaver is such beaver i who does not have a beaver i + 1 on his right (that is, if we make a query which includes beavers i and i + 1, then we would have to run Beavershave one more time). If we swap beavers i and j, then we have four possible positions at which the status of the flag may change: i - 1, i, j - 1, j. A response to a query is then the number of the terminal beavers in the interval which is a classical problem.

Problem C

In order to solve subproblem C1 we could either calculate dynamics or subtract the largest number using greedy algorithm. It is easy to prove that it is always better to subtract the largest number. In subproblem C2 it is sufficient to calculate dynamics for the first million, divide (in head) the number into two groups of digits — low orders and high orders — and make not one subtraction, but a series of subtractions in order to instantly minimize low orders. In order to solve subproblem C3 it is necessary to store in dynamics parameters not the number itself, but only the number of digits.

Problem D

Obviously, the Beaveractor moving along the arrows will either get out or go round a cycle. If the latter is the case, we need to find the length of the cycle l, and then we need to find the remainder of dividing the time by the length of the cycle. Thus, we have solved this case. In order to solve subproblem D1 it is sufficient to emulate the behavior of the Beaveractor saving at each step the time of the visit of the current point (this way we will know the length of the cycle the moment we come to the point in the cycle from which we started). In order to solve subproblems D2 and D3 we need to construct a graph of Beaveractor's movements and then process each of the multiple tests. In D2 we may construct the graph in a straightforward way and find an answer to each test by going through the graph. In D3 we are supposed to use logarithmic data structures. The idea of the solution is, thus, clear. The problem is interesting from the technical point of view.

Problem E

In order to solve subproblem E1 we may use the following claim: If the edge x → y has marks x and y in succession, then such edge may generate the path of interest. Call such edge "initiating". It is easy to understand that the path in both directions is constructed unambiguously from the initiating edge. Now, it is sufficient to consider only initiating edges. Indeed, consider required path in a graph. It has p nodes and p - 1 edges. By pigeonhole principle at least one edge has two or more marks. Let some edge x → y have marks a b, (a, b) ≠ (x, y). Then cut this path in two by the edge x → y and note that one of the two subpaths has more marks than it has edges. Proceeding in a similar fashion we may come to the conclusion that there is at least one edge x → y with marks x and y. If there are no initiating edges, then the path of interest does not exist. The path which is generated by the initiating edge is the shortest valid path for a given initiating edge. We may add to this path incoming and outgoing tails in such a way that the path becomes longer. The tails should not contain initiating edges, because initiating edges generate their own paths. Any valid path is a path consisting of three parts (incoming tail, path of the initiating edge, outgoing tail) which are connected by edges without marks. In order to solve subproblem E2 we may count all tails and paths generated by initiating edges beforehand and then count the number of paths with a fixed length by dynamics.

Read more »

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

By ruzana.miniakhmetova, 8 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.

  • Read more »

    Tutorial of ABBYY Cup 3.0
     
     
     
     
    • Vote: I like it
    • +93
    • Vote: I do not like it

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

    UPD2: Dear all!

    As promised, we invite ABBYY Cup 3.0 online part 25 best participants to ABBYY Open Day which takes place on the 17th of July at ABBYY Headquarters. So the onsite will be held at ABBYY Open Day.

    If you want to visit us, please, mail to abbyycup@abbyy.com in the next 5 days. Remind you that we'll privide you by food, lodging and help with transfer and visa. Transportations costs are on you.

    UPD1: Solutions!

    UPD: Dear all, ABBYY Cup 3.0 online part will take place today!

    Some notes:

  • The constest will be rated for all participants but programming problem contest winners.
  • Programming problem contest winners may register and take part in beyound the rating.
  • Our jury dicided to add 7th problem of their authorship.

    Good luck at the constest!

    Hi everyone!

    We are happy to announce ABBYY Cup 3.0, the long-expected programming contest! As promised, this year’s participants are to be given the tasks which won our programming problem contest.

    ABBYY Cup 3.0 has two parts, an online and onsite one. The first part is starting very soon – Wednesday, June 12, 17:00-21:00 Moscow time.

    We would like to give our personal thanks to Codeforces project team, especially to MikeMirzayanov and Gerald, for their help in running contests. And many-many thanks to all of you who participated there! Dear winners, please don’t get surprised that you can’t recognize the tasks you once sent to us, simply because they could easily be reserved for the onsite part and also because we could modify them seriously.

    The details

    The online round includes 6 tasks, 100 points each. All these tasks are divided in test sets and arranged either in two or three groups according to complexity level and point value. The first scheme implies there are an “easy” group and a “difficult” group of 30 and 70 points respectively. Another scheme provides three groups (ranked as “easy”, “medium” and “difficult”) of 20, 30 and 50 points per each. To add, we have a surprise in stock for you and this is a marvelous heuristic task!

    Official contest languages are C/C++, Pascal, C# and Java. You can program the tasks in any language supported by Codeforces, however the jury has no guarantee that complete solutions do exist for all the languages enlisted. Passing the whole chain of tests is necessary. When points are equal, time penalty is used according to ACM rules. Any fully completed test set means a fully completed ACM-task and is a signal flag to set time penalty for other contestants. Besides this year all participants will be in rating. Registration for ABBYY Cup 3.0 opens 12 hours before the start of the contest and closes when the contest is over. Just a brief reminder: winners of April tasks contest can take part in this one but won’t fight for ratings.

    What’s then?

    According to the online round’s results, 25 best participants are to meet in ABBYY Cup final, July 17, which takes place in company’s Moscow office along with ABBYY Open Day event. Food and lodging will be provided by ABBYY, travelling costs compensation will be dicussed individually.

    Good luck!

  • Read more »

    Announcement of ABBYY Cup 3.0
    Announcement of ABBYY Cup 3.0 - Finals
     
     
     
     
    • Vote: I like it
    • +173
    • Vote: I do not like it

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

    Hi, everyone!

    We are happy to announce the results of ABBYY programming problem contest! Congratulations to the winners:

  • Anna Kashkina (iroro) (two problems!)
  • Egor Belikov (egor-belikov)
  • Pablo Rotondo (PaulRS)
  • Ivan Shafran (IvanShafran)
  • Suchan Park (.o.) (two problems!)
  • Matvej Afanas'ev (xzibit68)
  • Aleksej Ivanin (Aliaksei)
  • Ivan Reshetnikov (Reshetnikov_Ivan)
  • Sayed Soroush Hashemi (S.HASHEMI)
  • The winners who have sent several problems must be wondering which problem has brought them to victory. You can ask me this question personally by message or by e-mail.

    We want to make a present to each of the participants! Please choose one of our products for personal use and let us know about it by e-mail. Winners can choose two products: )

    Also we want to invite all the winners to the ABBYY Open day which will take place in ABBYY’s Moscow office. A compensation format will be individually discussed with the participants by email.

    ABBYY Cup 3.0 is now supposed to consist of two parts: an online-part (in the beginning of June) and an onsite-part (in the middle of July).

    And for now we are waiting for ABBYY Cup 3.0 official announcement!

    Read more »

     
     
     
     
    • Vote: I like it
    • +91
    • Vote: I do not like it

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

    Hi everyone!

    ABBYY’s first programming problem contest is over. Many thanks to all the participants! The winners will be announced in two weeks time. As of now, there are some statistics:

  • We have received 78 problems from 45 authors.
  • 21 authors sent us one problem a head, 15 authors sent two problems each, and 3 problems at a time were sent by other 9 authors .
  • As for the age of the participants, there were 23 students, 18 pupils and 4 graduates.
  • Geography of the contest: most of the authors (23 people) are from Russia. Then comes Ukraine (6), Kazakhstan (4), and Byelorussia (3). Armenia, Bangladesh, Great Britain, Georgia, Cuba, Iran, the USA, Uruguay and South Korea had one representative each.
  • Grading: 2 international Grandmasters, 8 international Masters, 11 Master’s candidates, 12 experts and 7 specialists. Others are not included in the rating list.
  • Over the last weekends we received as many problems in total as during the previous two weeks.
  • As you can see, this contest has been a pilot one and mostly an experiment. Again, many thanks to all who joined in! We are very happy and proud to receive so many problems from you!

    Read more »

     
     
     
     
    • Vote: I like it
    • +114
    • Vote: I do not like it

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

    ABBYY Cup 3.0 is coming! Within the Cup we announce the programming problem contest. Best problems will go to ABBYY Cup 3.0 and best authors will win prizes!

    A problem should include:

  • description;
  • input/output example;
  • brief description of solution.
  • You can also add a complexity level (easy, medium, hard) and your ideas about modifications. We are interested in "heuristic" problems besides "classic". An example of a heuristic problem from the ABBYY Cup 2.0 is here.

    All problems must be new i.e. invented by you. Every contestant can send no more than three problems. If your problem does not go to ABBYY Cup 3.0, we promise to keep it in secret. Jury members are no longer participants of programming contests and they are not interested in using your problems apart from ABBYY Cup.

    Please send your problems in .pdf, .doc, .docx, or .txt format to abbyycup@abbyy.com with subject "ABBYY problem contest". Problems are accepted from 8 to 21 April. Write your name, surname, school and graduation year. It is desirable to write your Codeforces handle. Be sure that you receive the answer which confirms receiving your email!

    We hope that our problem contest will be held every year and will help to find new talants and make ABBYY Cup more interesring for contestants!

    Read more »

     
     
     
     
    • Vote: I like it
    • +118
    • Vote: I do not like it

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

    Dear all, ABBYY Cup 2.0 is completed!

    Thanks for all participants! We hope you enjoyed the problems of both divisions. It was too nice to read your good comments about heuristic problem!

    We thank Codeforces team: MikeMirzayanov, Gerald, Delinur, and sure tourist! It was too interesting and nice too work with you!

    We invite all the participants to visit ABBYY! If want, please write on brains@abbyy.com contact information about you (name, surname, handle, city and country you live in). We'll try help with organization of your arrival in our office nearest to you.

    Thank you very much! Good luck :)

    Read more »

    Announcement of ABBYY Cup 2.0 - Easy
    Announcement of ABBYY Cup 2.0 - Hard
     
     
     
     
    • Vote: I like it
    • +35
    • Vote: I do not like it

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

    UPD1:

    Editorial to Problem <>

    First of all note that merchants will pay only for those edge which are bridges. All other edges don’t match as after their deletion graph stay connected and between any nodes of graph the way stay. So first step to solve problem is to search bridges. Use this algorithm which works at O(n + m)

    After deletion all the graph bridges graph is divided for some components of connectivity (maybe one component). Let’s build new graph in which recieved components will be nodes and bridges — edges. This graph will be a tree. The graph is connected therefore the tree is connected. The edges correspond to bridges therefore there is no cycles in the tree.

    Note that the number of denarii means the pay of every merchant — is a distance between some the nodes in a new graph. But as this graph is a tree this distances can be easily find out using LCA search algorithms for two nodes. In this problem one should use the simplest LCA search algorithm which accomplish the preprocess for and handle one request for . The complexity of computations id .

    One can solve this problem easier. Let’s build a graph recursive pass-by initial graph and weight its edges. The edges with weight equals 1 will have bridges and others will have weight equals 0. So after all these reductions for solving problem it will be enough to compute the distance between two nodes in the graph recursive pass-by initial graph.

    UPD:

    Editorial to Problem <<Beaver's Problem — 2>>

    Solving this problem can be divided into two parts:

    • Noise deletion on the picture;
    • Fugures' classification.

    For noise deletion one can use the following methods:

    a. Do following steps: scan picture and build new on using it. If sone black pixel have white neighbours, we make it white. During thise steps we get rid of almost all noise on the picture. Then we make inverse opreation replacing all white pixels with black. So we get rid of almost all noise inside the picture.

    Note, that after all these opreations noise can stay as little black components. And some figures can lose their connectivity. These problems can be solved by deletion little black components and then unite near black components.

    b. But one can use easier way. Highlight black components and then cast away little ones. If to look closely to the texts in real under even distribution of the noise there is no little black components and it is not losing connectivity. However previous way is more reliable.

    The simplest way to classificate figures is to compare distributions of the distances from all the figure pixels to centre of the every figure. The centre can be calculated as average of the all points coordinates of the figure. Ditributions can be compared by expectation values and variations.

    An Editorial to Problem <>

    Let’s iterate through the cells of the hash table with step m (modulo h). So, all cells are separated into some cycles modulo h (all cycles have the same number of elements). It can be proven that the number of cycles is gcd(h, m) and the number of elements in each cycle is h / gcd(h, m). How can we use this property? The element with fixed hash-value will be added into some (next) cell in the corresponding to element’s hash-value cycle.

    So, we can process each cycle separately. To do this effectively (we want to solve large test package) we have to use any tree-structure like segment tree or combination of Fenwick tree with binary search.

    An effectiveness of solution with segment tree is , of solution with Fenwick tree — .

    An Editorial to Problem <>

    Let’s consider two different ways to solve this problem. Note that firstly (before finding correct magic square) we can easily determine the value of s. This value equal to the sum of all given numbers divided by n. So next, we will use this value.

    The first way to solve problem is brute force. This way based on two main ideas:

    • We can determine some square elements during the brute force using already fixed values. For example, if we have fixed three of values on the main diagonal, we can easily determine the fourth value. This trick decrease the number of brute force iterations.
    • We can rotate (or mirror) magic square without breaking his magic properties.

    The second way use discrete-optimization approach. Let’s consider the function Q = |sum1 - s| + ... + |sumt - s|, where |x| — the absolute value of x, t = 2 * n + 2, sum1, .., sumn — the sum of elements in one row, sumn + 1, sum2n — the sum of element in one column, sumt - 1 — the sum of elements on the main diagonal, sumt --- the sum of elements on the secondary diagonal.

    So, we want to find such permutation of the given elements that make our function as small as possible (We want to obtain zero). One way to do this: pick the random permutation. Try to make swaps in this permutation using greedy strategy (try to make swaps that make our function better). Let’s do 1000 swaps. If we obtain Q = 0 — we have found answer, else Q > 0 -- pick another random permutation and repeat this process again.

    An Editorial to Problem <>

    It is the simplest task of the set. The solution is based on greedy algorithmm.

    First of all, we need to zero out a1. One needs to make a1 steps with i = 1 and some t on each step. Which t is the most efficient? The maximum t, where 1 + 2t ≤ n. In that case later zeroing out longer prefixes of the sequence will take less steps. Having zeroed a1, we will write a current answer and notice that we reduce the task to the smaller one — sequence becomes one element shorter.

    The complexity of a solution or O(n) — depends on implementation.

    One can solve the task in a different way. To start from, the task can be solved for each element ai separately. In other words, if we fix some k, contribution of each ai to an answer can be counted separately.

    We fix some ai. Then we find maximum j so that i + 2j ≤ n. Evidently, that for every k < i + 2j, contribution of ai to the answer equals ai. In other words, one needs to make ai steps with transition to ai. Further we need to find maximum u, so that 2j + 2u ≤ n. Notice that u < j. Contribution of ai to the answer is equal 2 * ai, for every k that i + 2j ≤ k < i + 2j + 2u. Then we find q that i + 2j + 2u + 2q ≤ n, and so on ...

    A corresponding sequence of powers of 2 should be found for each element ai. Evidently, that overall complexity of this process is .

    Now we need to calculate an answer. It can be done, for example, like that: we will store the array bi — the change of the answer at the transition from i to 4i + 1. This array is formed in a trivial way during construction of sequences of powers of twos. Then it is easy to get the answer.

    The overall complexity of the solution equals .

    An Editorial to Problem <>

    Here one can see author's solution.

    Read more »

    Tutorial of ABBYY Cup 2.0 - Hard
     
     
     
     
    • Vote: I like it
    • +22
    • Vote: I do not like it

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

    **UPD1: ABBYY Cup 2.0 is completed! **

    UPD: Editorials here. They will be updated again :)

    Hey, everyone!

    We remind you that today at 16 PM the first division of ABBYY Cup 2.0 starts!

    This contest is rather hard to be solved completely and it is aimed at the first division Codeforces participants!

    Don’t forget to register for the contest!

    The duration of the contest is 5 hours. You should solve six problems (one of those is heuristic). The tests are split into three categories (easy, moderate, difficult), they are worth 20, 30 and 50 points, respectively. Only fully passing a group of tests is counted. When contestants win the same number of points, the penalty time is counted by the ACM rules. Fully solving some group of tests is counted as submitting an ACM-problem and will determine the penalty time you get. The first division (hard) contest will be a rated event for any participant despite of the participant rating and type of participation.

    We hope you’ll enjoy the contest! Good luck : )

    Read more »

    Announcement of ABBYY Cup 2.0 - Hard
    Announcement of Abbyy Cup 2.0 - Final
     
     
     
     
    • Vote: I like it
    • +75
    • Vote: I do not like it

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

    So, the second division of ABBYY Cup 2.0 is finished!

    Thanks to all participants! Have a good weekend :)

    Read more »

     
     
     
     
    • Vote: I like it
    • +30
    • Vote: I do not like it

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

    Hey everyone!

    Dear all, we remind you that today at 18 PM the second division of ABBYY Cup 2.0 starts!

    There will be a special problem from Codeforces as a present for participants!

    The duration of the contest is the same. You should solve seven problems in four hours. The tests are split into two categories (easy and difficult), they are worth 30 and 70 points, respectively. Only fully passing a group of tests is counted. When contestants win the same number of points, the penalty time is counted by the ACM rules. Fully solving some group of tests is counted as submitting an ACM-problem and will determine the penalty time you get. As MikeMirzayanov commented:

    The second division (easy) contest will be a rated event for Div. 2 Codeforces users, so it will be rated for official participants and those unofficials who is from the Codeforces Div. 2.

    These contests are officially available to those who is included in the Codeforces’ second division. The Codeforces’ first division users can take part in the second division out of competition.

    Good luck!

    Read more »

    Announcement of ABBYY Cup 2.0 - Easy
     
     
     
     
    • Vote: I like it
    • +31
    • Vote: I do not like it

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

    Dear all!

    Do you already have any plans for the nearest saturday evenings?

    If you want to spend it with ABBYY Cup click here to register! There are special checkboxes for pupils and graduates to take part in out of contest.

    If want to take part in contest, registration is obligatory. If you are not, it's free.

    As MikeMirzayanov commented:

    The second division (easy) contest will be a rated event for Div. 2 Codeforces users, so it will be rated for official participants and whose unofficials who is from the Codeforces Div. 2.

    The first division (hard) contest will be a rated event for any participant despite of the participant rating and type of participation.

    Read more »

     
     
     
     
    • Vote: I like it
    • +32
    • Vote: I do not like it

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

    The ABBYY company, a leading provider of document recognition, document capture, is holding a student online ABBYY Cup contest together with the Codeforces and Saratov State University. We’ve been taken into account the feedback from the previous contest into consideration. So, this year’s contest will consist of two divisions.

    If you belong to the second division on Codeforces, that is, if you’ve never participated in programming contest or have little experience of participating, then your best choice is to apply for participating in the second (easier) ABBYY Cup division. This division will have problems that are even easier than those given on ABBYY Cup 1.0. The first (and more difficult) division will be mainly interesting to the first division Codeforces participants, that is, to those who have considerable experience of sports programming.

    We thank Gena Korotkievich for taking part in preparing the problem set.

    Details

    Each division will contain 6 problems, each problem will cost 100 points. The official languages of the contest are C/C++, Pascal, C# and Java. You can submit problems on any languages that are supported by Codeforces. However, the jury does not guarantee that there exist full solutions in all languages from the list. Only fully passing a group of tests is counted. When contestants win the same number of points, the penalty time is counted by the ACM rules. Fully solving some group of tests is counted as submitting an ACM-problem and will determine the penalty time you get.

    The second division contest starts on April 21, Saturday, at 6.00 PM. The contest duration time is 4 hours. The tests are split into two categories (easy and difficult), they are worth 30 and 70 points, respectively. These contests are officially available to those who is included in the Codeforces’ second division. The Codeforces’ first division users can take part in the second division out of competition.

    The first division contest starts on April 28, Saturday, at 4.00 PM. The contest duration time is 5 hours (the problems are worth it :)). The tests are split into three categories (easy, moderate, difficult), they are worth 20, 30 and 50 points, respectively. Anyone regardless of their rating can participate in this contest.

    The registration will start on April, 16 on ABBYY Cup official page!

    Awards

    We invite all participants to the ABBYY Open Day. There we will talk about our technologies and give awards there. The winners of the difficult division will be awarded valuable gadgets and will also receive compensation of their expenses spent on the road to Moscow and back. The date of the event will be announced later. You can read about the Open Day in ABBYY for the ABBYY Cup 1.0 winners on the site of the contest and in Alex_KPR's blog, who participated in the Olympiads and won it.

    See you in ABBYY!

    Read more »

     
     
     
     
    • Vote: I like it
    • +102
    • Vote: I do not like it