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!

https://get.google.com/albumarchive/pwa/114842746780416406882/JInSLJ?authkey=Gv1sRgCLPuzoHEm4X_YQ

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(n²) or O(n³). 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(n²) 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.

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:

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:

Hi, everyone!

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

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!

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:

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!

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:

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!

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 :)

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 = |sum₁ - s| + ... + |sum_t - s|, where |x| — the absolute value of x, t = 2 * n + 2, sum₁, .., sum_n — the sum of elements in one row, sum_n + 1, sum_2n — the sum of element in one column, sum_t - 1 — the sum of elements on the main diagonal, sum_t --- 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 a₁. One needs to make a₁ steps with i = 1 and some t on each step. Which t is the most efficient? The maximum t, where 1 + 2^t ≤ n. In that case later zeroing out longer prefixes of the sequence will take less steps. Having zeroed a₁, 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 a_i separately. In other words, if we fix some k, contribution of each a_i to an answer can be counted separately.

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

A corresponding sequence of powers of 2 should be found for each element a_i. 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 b_i — 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.

**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 : )

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

Thanks to all participants! Have a good weekend :)

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!

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.

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!