VKontakte launches the third VK Cup championship
Hello! The social network VKontakte resumes its blog on Habré.
The first thing we want to tell is the VK Cup 2016 championship in sports programming and the analysis of several interesting problems from last year.
A few words about the Championship. VKontakte holds the third VK Cup - programming championship among Russian-speaking young professionals, students, schoolchildren and just lovers of algorithms and data structures.
')
To participate in it are invited teams of two people (you can participate individually), whose age is from 14 to 23 years. Qualifying rounds will be held from March to May, and the best 20 teams will be invited to the finals. The final will be held in St. Petersburg in July, the top eight teams will be awarded with prizes:
1st place - 1048576 rubles
2 places - 524288 rubles
3 places - 262144 rubles
4-8 places - 131072 rubles
The competition will be held at the Codeforces site, registration is already open - hurry to register a team ! Start your participation with the qualification stages , which will take place on March 13-14 and March 20-21. You can participate in both, and in any of them. All details are available on the link on the Championship page .
On the one hand, the VK Cup Championship follows the traditions of the programming championships, offering participants tasks on algorithms and data structures. On the other hand, we are trying to expand the format. So, during the championship last year, two unusual rounds were held (Wild Card rounds 1 and 2).
In the first of these, participants were offered simple tasks, but the language in which they can be solved, they learned only at the start of the round. The language of the round was a little-known language Picat. For two hours of competition, participants had to learn the basics of this language and solve several problems on it. For example, one of the problems was about calculating the Levenshtein distance.
Here is a solution sent by one of the participants:
The second Wild Card Round was held during the week. During this time, participants had to compile and implement the most accurate plagiarism search algorithm for solving programming problems. Unfortunately, in online programming competitions, some participants copy solutions from each other, making minor (and sometimes not very) edits. Participants needed to write a program that reads a sequence of files and highlights groups of equivalent solutions. The winner of the round is very advanced in the search for plagiarism, and his decision is now used on Codeforces to search for cheaters.
And here is an example of a classic format problem from the first qualifying round.
The full text of the conditions is available here . You can also try to solve them yourself and send the solution for verification. For the most impatient here is the description of the solution.
We are waiting for you on VK Cup 2016 ! It's time to register a team and connect to the qualifying round . If you do not have time to take part in the first, you can participate in the second, which will be held March 20-21. Good luck!
The first thing we want to tell is the VK Cup 2016 championship in sports programming and the analysis of several interesting problems from last year.
A few words about the Championship. VKontakte holds the third VK Cup - programming championship among Russian-speaking young professionals, students, schoolchildren and just lovers of algorithms and data structures.
')
To participate in it are invited teams of two people (you can participate individually), whose age is from 14 to 23 years. Qualifying rounds will be held from March to May, and the best 20 teams will be invited to the finals. The final will be held in St. Petersburg in July, the top eight teams will be awarded with prizes:
1st place - 1048576 rubles
2 places - 524288 rubles
3 places - 262144 rubles
4-8 places - 131072 rubles
The competition will be held at the Codeforces site, registration is already open - hurry to register a team ! Start your participation with the qualification stages , which will take place on March 13-14 and March 20-21. You can participate in both, and in any of them. All details are available on the link on the Championship page .
On the one hand, the VK Cup Championship follows the traditions of the programming championships, offering participants tasks on algorithms and data structures. On the other hand, we are trying to expand the format. So, during the championship last year, two unusual rounds were held (Wild Card rounds 1 and 2).
In the first of these, participants were offered simple tasks, but the language in which they can be solved, they learned only at the start of the round. The language of the round was a little-known language Picat. For two hours of competition, participants had to learn the basics of this language and solve several problems on it. For example, one of the problems was about calculating the Levenshtein distance.
The task
The Levenshtein distance between lines consisting of characters of the English alphabet is calculated as the minimum total cost of a sequence of actions that allows you to convert one line to another. Allowed actions:
* replacement: the cost of replacing one character with another is equal to the difference between the sequence numbers of these characters in the alphabet.
* insert / delete: the cost of inserting a character into a string or deleting a character from a string is equal to the ordinal number of this character in the alphabet.
You are given two lines. Find the Levenshtein distance between them.
* replacement: the cost of replacing one character with another is equal to the difference between the sequence numbers of these characters in the alphabet.
* insert / delete: the cost of inserting a character into a string or deleting a character from a string is equal to the ordinal number of this character in the alphabet.
You are given two lines. Find the Levenshtein distance between them.
Here is a solution sent by one of the participants:
Picat solution
~~~~~ table(+, +, min) edit(I, J, Cost) ?=> str(S), goal(G), N = length(S), M = length(G), ( I <= N, J <= M, edit(I + 1, J + 1, NextCost), Cost = abs(ord(S[I]) - ord(G[J])) + NextCost ; I <= N, edit(I + 1, J, NextCost), Cost = ord(S[I]) - 0'a + 1 + NextCost ; J <= M, edit(I, J + 1, NextCost), Cost = ord(G[J]) - 0'a + 1 + NextCost ; I > N, J > M, Cost = 0 ). main => S = read_line(), G = read_line(), cl_facts([$str(S), $goal(G)]), edit(1, 1, Cost), println(Cost). ~~~~~ The second Wild Card Round was held during the week. During this time, participants had to compile and implement the most accurate plagiarism search algorithm for solving programming problems. Unfortunately, in online programming competitions, some participants copy solutions from each other, making minor (and sometimes not very) edits. Participants needed to write a program that reads a sequence of files and highlights groups of equivalent solutions. The winner of the round is very advanced in the search for plagiarism, and his decision is now used on Codeforces to search for cheaters.
And here is an example of a classic format problem from the first qualifying round.
Example
The social network for dogs VBudke has k special servers for clamping downloadable clips about cats. Each video after downloading should be processed on one (any) of the servers and only after that it is saved in the social network.
Each server is known to pinch a minute fragment in one second. Thus, on any of the servers, the video file of m minutes is pinched in m seconds.
We know the load time in the social network of each of the n videos (in seconds since the general start of the servers). All videos arrive at different points in time and are processed in the order received. If the video has arrived at the moment s, then it can be processed immediately at this moment. Some of the videos can be expected to be processed due to the busyness of all servers. In this case, as soon as any server becomes free, it will immediately begin processing the next clip. Pending rollers are added to the queue. If several servers are free by the time processing starts, then any of them starts processing it.
For each of the rollers determine the end of its processing.
Input data
The first line of input data contains integers n and k (1 ≤ n, k ≤ 5 · 10 ^ 5) - the number of clips and servers, respectively.
Next n lines contain descriptions of the rollers by pairs of integers s_i, m_i (1 ≤ s_i, m_i ≤ 10 ^ 9), where s_i is the time in seconds when the i-th movie arrived, and m_i is its duration in minutes. It is guaranteed that all s_i are different and the rollers are given in chronological order of loading, that is, in the order of increasing s_i.
Output
Output n numbers e_1, e_2, ..., e_n, where e_i is the time in seconds from the start of the servers when the i-th movie is processed.
Each server is known to pinch a minute fragment in one second. Thus, on any of the servers, the video file of m minutes is pinched in m seconds.
We know the load time in the social network of each of the n videos (in seconds since the general start of the servers). All videos arrive at different points in time and are processed in the order received. If the video has arrived at the moment s, then it can be processed immediately at this moment. Some of the videos can be expected to be processed due to the busyness of all servers. In this case, as soon as any server becomes free, it will immediately begin processing the next clip. Pending rollers are added to the queue. If several servers are free by the time processing starts, then any of them starts processing it.
For each of the rollers determine the end of its processing.
Input data
The first line of input data contains integers n and k (1 ≤ n, k ≤ 5 · 10 ^ 5) - the number of clips and servers, respectively.
Next n lines contain descriptions of the rollers by pairs of integers s_i, m_i (1 ≤ s_i, m_i ≤ 10 ^ 9), where s_i is the time in seconds when the i-th movie arrived, and m_i is its duration in minutes. It is guaranteed that all s_i are different and the rollers are given in chronological order of loading, that is, in the order of increasing s_i.
Output
Output n numbers e_1, e_2, ..., e_n, where e_i is the time in seconds from the start of the servers when the i-th movie is processed.
The full text of the conditions is available here . You can also try to solve them yourself and send the solution for verification. For the most impatient here is the description of the solution.
Solution Description
We’ll get a queue with priorities; we’ll store there for the near future the release of each of the k servers. Thus, there will be exactly k elements in the queue at any given time. If the standard language library does not have a built-in priority queue, then you can simply use an ordered set or heap. It is important that the operations of removing the minimum and adding the element work no longer than the logarithm. Then, when processing the next video s_i, m_i, it is easy to understand that it will be processed at the moment e_i = max (s_i, A) + m_i, where A is the minimum release time for all servers, that is, the number in the head of the priority queue (or at the top heaps or sets). Thus, you must output e_i, remove the element from the queue head, and then add e_i there.
Here is the main part of this solution in C ++:
Here is the main part of this solution in C ++:
priority_queue<long long, std::vector<long long>, std::greater<long long>> q; int n, k; scanf("%d %d", &n, &k); for (int i = 0; i < k; i++) q.push(0); for (int i = 0; i < n; i++) { long long s, m; scanf("%lld %lld", &s, &m); s = max(s, q.top()) + m; printf("%lld\n", s); q.pop(); q.push(s); } We are waiting for you on VK Cup 2016 ! It's time to register a team and connect to the qualifying round . If you do not have time to take part in the first, you can participate in the second, which will be held March 20-21. Good luck!
Source: https://habr.com/ru/post/279145/
All Articles