I invite to the programming championship
Hello!
Since 2012, we have been holding the All-Russian programming championships together with Codeforces. You can participate with 18 years. Citizenship in general 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 first place was taken by the “terminator” tourist , and the fifth place — this guy rng_58 from Japan:
')
The rules are “olympiadic” tasks that need to be solved, plus “hacking” of other people's solutions due to the selection of their non-standard data sets. Individual standings, 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 final - you will need to write an AI to battle other participants' AI (last year there was hockey, before that - the battle of magicians). The prize of the game round is a laptop.
Qualification March 16, qualifying round March 18, the final for 50 participants - April 15 in our office in Moscow. Last year, the gradation of the number of participants as they were selected for the final was 3500, 2000, 400 and 50 for the final. The average age of the finalist is 24 years.
For the finalists from the Russian Federation, reimbursement of tickets to Moscow is provided (up to 10 thousand rubles).
The difficulty will increase as you get closer to the final, but the rules of the rounds remain the same.
Qualifying runs on the Codeforces platform remotely, as usual, all the tournaments 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 ​​required 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. Having closed the task (after that it is already impossible to work with it), you can watch other people's sources of already sent solutions and “break” them, in fact, by identifying bugs in the autotest, that is, by substitution of complex input data sets. For successful hacking - a bonus, for unsuccessful - a fine.
You are given n memory sections, for each segment its length in bytes is known as a [i]. You need to place in memory as many data structures of possible m as possible, for each structure its size is known as b [j] in bytes. That is, in the optimistic case, it will be possible to place all m structures, and in the pessimistic one - not one. It is known that all b [j] are powers of two. Each structure must be in the same area of ​​memory, but the area can contain several structures. Of course, each byte can belong to no more than one structure.
Your program should work quickly (fit in 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 ​​of a [i] and b [j] there may be the same values ​​(at least all).
Here there are more tasks.
First, we consider a special case when among the values ​​of b [j] there are no ones. This means that all values ​​of b [j] are even (since these are powers of two). In this case, the odd parts of the memory will not be able to be fully consumed (the sum of even numbers 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 it means that 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 defined in all parts of the memory of an odd length (after all, they cannot be used completely without single structures). If single structures remain after this, then we note that if we define one single structure in an even segment, it will become odd. Therefore, there it will certainly be beneficial to determine one more unit structure. Thus, it is possible from a pair of single structures to gather up structures of size 2 and continue working with them, treating them as a whole. If one is left without a pair, then it is necessary to determine it to 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 from how the original structures is the current one and to place individual structures eagerly on this parameter.
- How many people registered at the time of publication of the topic?
You can see here: codeforces.com/croc2016/registrants
- Where are the exact rules and registration?
Here is codeforces.com/blog/entry/43229
To register for the championship please follow the link - codeforces.com/croc2016/register
- The task passed 19 data sets out of 20: will I get at least one point for it?
No, you will not. You have to go through everything.
- I am not a citizen of Russia. Can I participate?
Yes. But it is worth considering that the road to Moscow, we pay only the finalists - the citizens of the Russian Federation.
- I am 45 years old, I am bearded, a student and live in Africa. I can?
Participate and go to the final - yes.
- Have reports?
Photo report and report of the participant .
And video:
- Is there an opportunity to participate at least in qualifying and qualifying rounds, if I am under 18?
Yes, you can fight for the CF rating, but you will not qualify for the final. At least, if you are under 18 full years before April 15, 2016.
- What to write in the registration form, if I can not fill in the "university"?
Write "null" or just fill in the situation. It does not impose restrictions.
- Cool, but I can not. When is the next championship?
Try to take part out of the competition. If it does not work out - the Championship is not the last time, plus there is a mass 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 the All-Russian programming championships together with Codeforces. You can participate with 18 years. Citizenship in general 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 first place was taken by the “terminator” tourist , and the fifth place — this guy rng_58 from Japan:
')
The rules are “olympiadic” tasks that need to be solved, plus “hacking” of other people's solutions due to the selection of their non-standard data sets. Individual standings, 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 final - you will need to write an AI to battle other participants' AI (last year there was hockey, before that - the battle of magicians). The prize of the game round is a laptop.
Timing
Qualification March 16, qualifying round March 18, the final for 50 participants - April 15 in our office in Moscow. Last year, the gradation of the number of participants as they were selected for the final was 3500, 2000, 400 and 50 for the final. The average age of the finalist is 24 years.
For the finalists from the Russian Federation, reimbursement of tickets to Moscow is provided (up to 10 thousand rubles).
Complexity
The difficulty will increase as you get closer to the final, but the rules of the rounds remain the same.
Tournament
Qualifying runs on the Codeforces platform remotely, as usual, all the tournaments 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 ​​required 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. Having closed the task (after that it is already impossible to work with it), you can watch other people's sources of already sent solutions and “break” them, in fact, by identifying bugs in the autotest, that is, by substitution of complex input data sets. For successful hacking - a bonus, for unsuccessful - a fine.
Example task from 2013:
You are given n memory sections, for each segment its length in bytes is known as a [i]. You need to place in memory as many data structures of possible m as possible, for each structure its size is known as b [j] in bytes. That is, in the optimistic case, it will be possible to place all m structures, and in the pessimistic one - not one. It is known that all b [j] are powers of two. Each structure must be in the same area of ​​memory, but the area can contain several structures. Of course, each byte can belong to no more than one structure.
Your program should work quickly (fit in 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 ​​of a [i] and b [j] there may be the same values ​​(at least all).
Here there are more tasks.
Solution options:
First, we consider a special case when among the values ​​of b [j] there are no ones. This means that all values ​​of b [j] are even (since these are powers of two). In this case, the odd parts of the memory will not be able to be fully consumed (the sum of even numbers 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 it means that 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 defined in all parts of the memory of an odd length (after all, they cannot be used completely without single structures). If single structures remain after this, then we note that if we define one single structure in an even segment, it will become odd. Therefore, there it will certainly be beneficial to determine one more unit structure. Thus, it is possible from a pair of single structures to gather up structures of size 2 and continue working with them, treating them as a whole. If one is left without a pair, then it is necessary to determine it to 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 from how the original structures is the current one and to place individual structures eagerly on this parameter.
Question answer
- How many people registered at the time of publication of the topic?
You can see here: codeforces.com/croc2016/registrants
- Where are the exact rules and registration?
Here is codeforces.com/blog/entry/43229
To register for the championship please follow the link - codeforces.com/croc2016/register
- The task passed 19 data sets out of 20: will I get at least one point for it?
No, you will not. You have to go through everything.
- I am not a citizen of Russia. Can I participate?
Yes. But it is worth considering that the road to Moscow, we pay only the finalists - the citizens of the Russian Federation.
- I am 45 years old, I am bearded, a student and live in Africa. I can?
Participate and go to the final - yes.
- Have reports?
Photo report and report of the participant .
And video:
- Is there an opportunity to participate at least in qualifying and qualifying rounds, if I am under 18?
Yes, you can fight for the CF rating, but you will not qualify for the final. At least, if you are under 18 full years before April 15, 2016.
- What to write in the registration form, if I can not fill in the "university"?
Write "null" or just fill in the situation. It does not impose restrictions.
- Cool, but I can not. When is the next championship?
Try to take part out of the competition. If it does not work out - the Championship is not the last time, plus there is a mass 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.
Source: https://habr.com/ru/post/278803/
All Articles