March 9, 2016 at 09:56I invite you to the programming championship
Hello!
Since 2012, we have been holding all-Russian championships in programming together with Codeforces. You can participate from 18 years old. Citizenship as a whole is not important, we always had guests from Kazakhstan, Ukraine, Belarus and other countries, but the language of the tournament is Russian. For example, in 2013 there were 3,500 people, and the “terminator” tourist took first place , and the fifth is this guy rng_58 from Japan:
The rules are the “olympiad” tasks that need to be solved, plus the “hacks” of other people's decisions by selecting their own non-standard data sets. Individual classification, in prizes of 100 thousand rubles for the first place, 70 thousand and 50 thousand for the second and third. As usual, there will be a separate game round in the finals - you will need to write AI to battle the AI of other participants (last year there was hockey, before that - the battle of magicians). The prize of the game round is a laptop.
Qualification on March 16, qualifying round on March 18, final for 50 participants - April 15 at our office in Moscow. Last year, the gradation of the number of participants as they were selected for the finals was as follows: 3500, 2000, 400 and 50 for the finals. The average age of the finalist is 24 years.
Compensation for tickets to Moscow (up to 10 thousand rubles) is provided for finalists from the Russian Federation.
Difficulty will increase as you approach the final, but the rules of the rounds remain the same.
Qualifiers are held remotely on the Codeforces platform, as usual all tournaments are there. The final involves physical participation: all players will gather in one hall. There are Wi-Fi, sockets and local machines with a set of development environments that cover all the languages stipulated by the rules. Practice shows that we deploy only a couple of such machines - usually participants arrive with their laptops.
From there you go to the site under your account (as usual), get tasks, solve them. Closing a task (after that it is no longer possible to work with it), you can look at the source codes of already sent solutions and “break” them, in fact, by identifying bugs in the autotest, that is, by substituting complex sets of input data. For successful hacking - a bonus, for unsuccessful - a fine.
You are given n sections of memory, for each section its length in bytes a [i] is known. You need to place as many data structures out of possible m in memory as possible, for each structure its size b [j] in bytes is known. That is, in the optimistic case, it will be possible to place all m structures, and in the pessimistic case - not one. It is known that all b [j] are powers of two. Each structure should be in one piece of memory, but a piece can hold several structures. Of course, each byte can belong to no more than one structure.
Your program should work quickly (within a couple of seconds) for any n and m not exceeding 10 ^ 6. All a [i] and b [j] are integers from 1 to 10 ^ 9. Among the values a [i] and b [j], there may be the same values (at least all).
Here here there are more problems.
First, we consider a special case when among the values of b [j] there are no units. So all the values of b [j] are even (since these are powers of two). In this case, the odd sections of memory cannot be used up completely (the sum of the even ones is even). Therefore, we will not lose anything if we subtract one from each odd a [i]. Thus, we obtain a situation in which all b [j] and a [i] are even. But then all these values can be simultaneously divided by 2 and this will not change the answer! With such a division, single structures may appear, and we will now consider this case (and if they did not appear, then we can divide everything into two again).
If some b [j] are equal to 1, then there is no reason not to try to place them somewhere. Of course, first of all, they must be determined in all sections of memory of odd length (after all, they cannot be used in any way without unit structures). If even after this unit structures remain, then we note that if we define one unit structure in an even section, then it will become odd. Therefore, it will certainly be beneficial to determine another unit structure. Thus, it is possible to collect structures of size 2 from pairs of unit structures and continue to work with them, considering them as a whole. If you are left alone without a pair, then you need to define it in the minimum positive a [i].
So we have achieved that now we do not have structures of size 1, which means we have come to the first case. The only thing you need to remember is how many initial structures the current one consists of and place single structures greedily for this parameter.
- How many people registered at the time of publication of the topic?
You can see it here: codeforces.com/croc2016/registrants
- Where are the exact rules and registration?
Here - codeforces.com/blog/entry/43229
You can register for the championship at the link - codeforces.com/croc2016/register
- The task completed 19 data sets out of 20: will I get at least one point for it?
No, don't get it. We have to go through everything.
- I am not a citizen of Russia. Can I participate?
Yes. But it should be borne in mind that we pay the road to Moscow only to finalists - citizens of the Russian Federation.
- I am 45 years old, I am a bearded student and live in Africa. I can?
Participate and go to the finals - yes.
- Any reports?
Photo report and participant report .
And the video:
- Is there an opportunity to participate at least in the qualifying and qualifying rounds, if I am not 18?
Yes, you can fight for the CF rating, but you won’t reach the final. At least, if you are under 18 full years until April 15, 2016.
- What should I write in the registration form if I cannot fill out the “University” field?
Write “null” or just fill in according to the situation. It does not impose restrictions.
- Cool, but I can’t. When is the next championship?
Try to take part out of competition. If it doesn’t work out - the Championship is not the last time, plus there are still a lot of contests and contests. For example, a couple of years ago we had a competition of flying robots with a prize of 1 million rubles. You can also follow our corporate blog here on Habré - major events will be announced.
Since 2012, we have been holding all-Russian championships in programming together with Codeforces. You can participate from 18 years old. Citizenship as a whole is not important, we always had guests from Kazakhstan, Ukraine, Belarus and other countries, but the language of the tournament is Russian. For example, in 2013 there were 3,500 people, and the “terminator” tourist took first place , and the fifth is this guy rng_58 from Japan:
The rules are the “olympiad” tasks that need to be solved, plus the “hacks” of other people's decisions by selecting their own non-standard data sets. Individual classification, in prizes of 100 thousand rubles for the first place, 70 thousand and 50 thousand for the second and third. As usual, there will be a separate game round in the finals - you will need to write AI to battle the AI of other participants (last year there was hockey, before that - the battle of magicians). The prize of the game round is a laptop.
The timing
Qualification on March 16, qualifying round on March 18, final for 50 participants - April 15 at our office in Moscow. Last year, the gradation of the number of participants as they were selected for the finals was as follows: 3500, 2000, 400 and 50 for the finals. The average age of the finalist is 24 years.
Compensation for tickets to Moscow (up to 10 thousand rubles) is provided for finalists from the Russian Federation.
Complexity
Difficulty will increase as you approach the final, but the rules of the rounds remain the same.
Tournament progress
Qualifiers are held remotely on the Codeforces platform, as usual all tournaments are there. The final involves physical participation: all players will gather in one hall. There are Wi-Fi, sockets and local machines with a set of development environments that cover all the languages stipulated by the rules. Practice shows that we deploy only a couple of such machines - usually participants arrive with their laptops.
From there you go to the site under your account (as usual), get tasks, solve them. Closing a task (after that it is no longer possible to work with it), you can look at the source codes of already sent solutions and “break” them, in fact, by identifying bugs in the autotest, that is, by substituting complex sets of input data. For successful hacking - a bonus, for unsuccessful - a fine.
An example of a task from 2013:
You are given n sections of memory, for each section its length in bytes a [i] is known. You need to place as many data structures out of possible m in memory as possible, for each structure its size b [j] in bytes is known. That is, in the optimistic case, it will be possible to place all m structures, and in the pessimistic case - not one. It is known that all b [j] are powers of two. Each structure should be in one piece of memory, but a piece can hold several structures. Of course, each byte can belong to no more than one structure.
Your program should work quickly (within a couple of seconds) for any n and m not exceeding 10 ^ 6. All a [i] and b [j] are integers from 1 to 10 ^ 9. Among the values a [i] and b [j], there may be the same values (at least all).
Here here there are more problems.
Solution Options:
First, we consider a special case when among the values of b [j] there are no units. So all the values of b [j] are even (since these are powers of two). In this case, the odd sections of memory cannot be used up completely (the sum of the even ones is even). Therefore, we will not lose anything if we subtract one from each odd a [i]. Thus, we obtain a situation in which all b [j] and a [i] are even. But then all these values can be simultaneously divided by 2 and this will not change the answer! With such a division, single structures may appear, and we will now consider this case (and if they did not appear, then we can divide everything into two again).
If some b [j] are equal to 1, then there is no reason not to try to place them somewhere. Of course, first of all, they must be determined in all sections of memory of odd length (after all, they cannot be used in any way without unit structures). If even after this unit structures remain, then we note that if we define one unit structure in an even section, then it will become odd. Therefore, it will certainly be beneficial to determine another unit structure. Thus, it is possible to collect structures of size 2 from pairs of unit structures and continue to work with them, considering them as a whole. If you are left alone without a pair, then you need to define it in the minimum positive a [i].
So we have achieved that now we do not have structures of size 1, which means we have come to the first case. The only thing you need to remember is how many initial structures the current one consists of and place single structures greedily for this parameter.
Question answer
- How many people registered at the time of publication of the topic?
You can see it here: codeforces.com/croc2016/registrants
- Where are the exact rules and registration?
Here - codeforces.com/blog/entry/43229
You can register for the championship at the link - codeforces.com/croc2016/register
- The task completed 19 data sets out of 20: will I get at least one point for it?
No, don't get it. We have to go through everything.
- I am not a citizen of Russia. Can I participate?
Yes. But it should be borne in mind that we pay the road to Moscow only to finalists - citizens of the Russian Federation.
- I am 45 years old, I am a bearded student and live in Africa. I can?
Participate and go to the finals - yes.
- Any reports?
Photo report and participant report .
And the video:
- Is there an opportunity to participate at least in the qualifying and qualifying rounds, if I am not 18?
Yes, you can fight for the CF rating, but you won’t reach the final. At least, if you are under 18 full years until April 15, 2016.
- What should I write in the registration form if I cannot fill out the “University” field?
Write “null” or just fill in according to the situation. It does not impose restrictions.
- Cool, but I can’t. When is the next championship?
Try to take part out of competition. If it doesn’t work out - the Championship is not the last time, plus there are still a lot of contests and contests. For example, a couple of years ago we had a competition of flying robots with a prize of 1 million rubles. You can also follow our corporate blog here on Habré - major events will be announced.
