Analysis of qualifications of the programming championship among backend developers
On the first of June the finals of our programming championship took place. The names of the winners are already known. Soon they will receive their awards, and in the meantime we are starting to publish the analysis of the tasks of the championship. First, let us analyze the tasks of the qualification stage among the backend developers.
Qualification lasts a week, and the number of participants in the thousands, so that the preparation of tasks, it turns out, is not an easy task. In total, we needed to do 24 tasks and divide them between the four options so that the options were comparable in complexity.
This time we came up with six tasks, for each of which it was possible to come up with several alternative formulations: one invented task spawned four at once! Thus, the options turned out to be as comparable as possible.
Therefore, I will not publish analyzes of all 24 tasks. Instead, I will review the six tasks of one of the qualifying options: the others are solved in a similar way.
A. Alarm clocks
Work in most IT companies has many advantages: there is no dress code, you can sometimes work remotely, cool and smart colleagues, and, of course, a free schedule! However, a free schedule and the ability to work remotely require great willpower.
Programmer Alexey likes to work at night and does not like to come to work late. To accurately wake up in the morning, Alexey turns every evening alarm clocks on your phone. Each alarm clock is arranged in such a way that it rings every minutes from the time at which it was brought. For example, if the alarm was set at the time then he will call at times , , and so on. At the same time, if any two alarms start ringing at one time, only one of them is displayed.
It is known that before waking up, Alexey listens every morning exactly alarm clocks, then wakes up. Determine the point in time when Alex wakes up.
All alarms ring at integral times, and all alarms have the same snooze period. If two alarms are set at times and , and these points in time give the same balance when divided by , you can leave only one alarm clock - the one that rings first.
So the first action will get rid of unnecessary alarms: group them according to the magnitude of the remainder of the division by and from each group we will leave only one alarm, set for the earliest time.
Now let's learn how to determine how many alarm clocks rang by some time point. . If the alarm is on for a while the number of his calls by the time will be equal
Add up these values for all alarms, we get the total number of alarms that have been rang by the time .
After that, the initial problem is solved by a binary search by : with increase the number of ranked alarms does not decrease (i.e., the function is monotonous); you can select 0 as the initial left border, and the maximum possible answer in the problem.
B. Sports Tournament
While Masha was on vacation, her colleagues organized a chess tournament according to the Olympic system. During the rest, Masha did not pay much attention to this venture, so she could barely remember who was playing with whom (there’s not even a talk about the order of the games). Suddenly, Masha had the idea that it would be nice to bring a souvenir to the winner of the tournament from vacation. Masha does not know who won the final game, but she can easily figure out who played in it, if only she correctly remembered the playing pairs. Help her see if this is the case and identify possible candidates for winners.
This problem can be solved by restoring the tournament games graph. Let's start with the fact that for each participant it is clear to what stage of the tournament he reached: this is determined by the number of games with his participation.
After that, you can distribute the games in rounds. For example, in all the games of the first round, one of the participants flew out in the first round, and the other flew out not earlier than in the second. When processing a game tour with a number It is necessary to check that all participants in this game have played the same number of games at the current time, corresponding to the number otherwise the tournament is invalid.
After the restoration of the tournament scheme, it remains only to print the answer.
C. Interesting game
Petya and Vasya are playing an interesting game. First, Vasya announces how many points you need to score in order for the game to end. Then Petya takes the cards on which non-negative integers are written, and begins to lay them on the table one by one. If the number on the card is a multiple of five, then Vasya gets one point. If the number on the card is a multiple of three, then Petya gets one point. If the number on the card is not a multiple of either three or five, or vice versa, a multiple of both of them, then no one gets points.
As soon as one of the participants scores the number of points that Vasya named at the beginning of the game, the game stops and this player becomes the winner. If none of the participants have scored the required number of points, but all the cards have ended, then the winner is the player who has more points. If all the cards have ended, and the points are equally divided, a draw is declared.
Petya and Vasya are sometimes in a hurry, so they want not to play the game completely, but to immediately find out who would have won with known initial data. They asked you to write a program that will help answer this question.
The most important thing in this task is to correctly understand from the condition of which player and how many points are added after each new move, and also under what conditions the player earns them.
The problem is solved straightforwardly. Since the restrictions are more than mild, it’s enough to go through the data once, interrupting their processing, if one of the players scored the necessary number of points at the next step. If the required minimum number of points is not scored by any of the players, the winner is determined at the end of the cycle.
In some versions of this task, it was necessary to further handle the situation where players could get points at the same time for the same card.
This task is expectedly become the easiest among all the tasks of qualification.
D. Exception Analyzer
We describe the syntax of the programming language :
func f() {...}- function declaration (in parenthesis - the body)maybethrow Excis a command that may or may not throw an exception of the typeExc.try {...} suppress Exc- if an exception of the typeExcoccurs inside this block, then it is suppressed.f()is a function callf.
In language All instructions, except function declarations, can only be in the body of a function. Functions cannot be declared inside other functions. The function can be called before its definition, as well as in its own body. Names of functions and exceptions in the language must match the regular expression , be unique and not match the keywords func , try , suppress , maybethrow .
At the entrance is a program in the language and number . For each function of the program it is necessary to output no more than exceptions that can fly out of it. Output should lexicographically the smallest exceptions.
This task turned out to be the most difficult of all qualification tasks.
To solve it, it was possible to parse the program syntactically by constructing a graph of function calls: in this graph, each function corresponds to a vertex, and to a function call — an edge. After this, it is necessary to directly implement the logic of propagation of exceptions along a graph — for this purpose, a wide bypass of the graph is appropriate.
We choose some exceptions and all the functions that can generate it. These functions are called from other functions; perhaps the calls are inside the try {...} suppress block - in this case, the exception does not apply to the function in which the call occurs. Thus, it is possible with the help of a wide graph traversal to determine all the functions from which this exception can be thrown.
After the detour has been performed for all possible exceptions, all that remains is to form a response.
E. Decoding
A new service has appeared on the Internet. Unfortunately, he has no documentation. Experimentally, the string s was received from the server. However, some characters in this line are encoded - in order to get a real answer, you need to decode this line several times. Since there is no documentation for the service, for further experiments it is necessary to determine how many times it is possible to decode this string in a non-trivial way. The decoding procedure is as follows: you need to find all the substrings of the form ~XY , where X and Y are large or small hexadecimal digits and replace them simultaneously with a character with the ASCII code (each has its own substring). Decoding is called trivial if there are no such substrings.
In a single line print the maximum number of consecutive non-trivial decoding of the source line.
We will consider the characters of the original string in sequence, from left to right. If the addition of the next character leads to the appearance of a sequence that can be decoded, you need to do so. Decoding needs to be repeated as long as possible, i.e. while at the end of the current line there is a sequence of a type defined by the conditions of the problem.
For each character of the resulting decoded string, you must remember how many times to obtain it, you had to decode the original string. It is clear that the newly added character in the string was decoded zero times. If, however, symbols decoded times, the character they make requires decoding operations.
Let the final decoded string contain characters for which it was required to perform decoding, respectively time. Then the answer is
F. Search for a breaking commit
The Yandex search implements the so-called “green trunk” policy: any code that enters the repository, with some reservations, is guaranteed not to break the build and tests.
Tests, however, are extremely difficult, and it is impractical to run them all on each commit. So for especially difficult cases the following procedure is implemented: the tests are run with some regularity, and the set of commits is checked right away. Thus, for some time n unverified commits can get into the trunk, among which at least one contains an error.
In such a situation, the testing system should detect the number m of the first commit that broke the tests. This number has the following property: all commits with numbers less than m successfully pass tests, and commits with numbers greater than or equal to m do not pass tests. In the task it is guaranteed that a commit with the specified properties necessarily exists and is unique.
In order to save resources, the testing system can check only one commit at a time. You need to write a program that will determine the number m.
This task has a prototype in our production: some tests of search components are really too complex, they are too expensive to run on each commit, and a breakdown search procedure is implemented for them, similar to the one described in the task. Of course, developers can use the precommit test and, as a rule, do it, so this procedure is not so popular.
Different variants of the task differed in the number of commits that need to be checked at the same time.
The solution here is quite simple: you need to implement a slightly more complex version of binary search . Say, if you want to check four commits at a time, you need to evenly split the current segment with four numbers. During implementation, some care is required to avoid looping when the length of the segment is less than the number of simultaneously checked commits. It is also worth noting that, according to the conditions of the problem, you can check the same commit several times - sometimes you have to do this, for example, if there are two commits, and you need to check three commits at a time.
Assorted qualification round tasks are available as a Codeforces training session . We also did a training session for the finals .
')
Source: https://habr.com/ru/post/457262/
All Articles