November 21, 2010 at 21:31Challenging Competition for Programmers
Hello habrachitatel.
Recently, I like to hold competitions for mathematicians, but these competitions are somewhat different from programming olympiads, at least in that I offer problems that do not have an effective solution algorithm. In addition, tasks are proposed that either no one has ever solved before, or solved very little, but have not achieved significant success. The last feature of these problems is that they are somehow related to enumeration combinatorics, that area of mathematics that was buried in Russia along with other useful areas of science "you know when." But this is less important.
An example of such a competition is a competition on the problem of placing 6 queens on a n × n chessboard. It was first solved exactly in the framework of my competition (an explicit formula for the number of all configurations was obtained) and caused a resonance among those researchers who are involved in enumerator combinatorics. The formula itself allowed researchers of this problem to build new and stronger hypotheses. I expressed my position in relation to such tasks in Habré in this article .
Another competition related to the physics of polymers in the future will allow researchers in this field to show that defective gratings can also be easily calculated, as well as defect-free gratings that are practically unrealistic in the real world. This was shown by calculating the “pre-Hamiltonian” cycles. The corresponding competition was supported by an article on the dynamic programming method . The algorithm described in this article (with appropriate implementation) is by far the fastest in the world (modestly, but it is). With more serious computing power, one could talk about obtaining significant results in enumerator combinatorics ... but dreaming is not harmful. In short, this competition was also useful for science.
Now I am conducting one contest “just like that”, even without a prize pool, and I propose to solve not the most difficult problems from my repertoire. What for? Just so that lovers to compete (of course, in the presence of free time) could compete with other such lovers. The proposed tasks are difficult (in any case, the existence of an effective algorithm for solving them has not been proved), so you will have to fight not in the classical sense (as at the programming Olympiad - for speed and quality), but in the sense of "who has the best approach." And someone can have more power at hand, also welcome. In any case, I personally am interested in not who wins, but the result itself obtained by joint forces in the course of the competition. Practice has shown that the last two of my competitions have proven to be practically useful for science.
The contest itself will be held on my blog, which, in addition to other contests, has published posts with a completely different meaning from programming. You just can not pay attention to them, and immediately select the " Contests " section in the menu . The fact is that I cannot create a separate resource for contests for personal reasons and for reasons of insufficient experience in conducting them, so for the time being they will train to conduct them on a blog.
A detailed description of the tasks is given on the pages of the competition, here I will briefly outline the conditions.
The natural number n is given. Find a minimal integer k such that the number 3 k contains at least n consecutive zeros in the decimal notation. For example, for n = 1, the answer would be k = 10, since 3 10 = 59 0 49 and this is the first of the powers of the triple that contains one zero. For n = 2, the answer is k = 35, since 3 35 = 5 00 31545098999707 and this is the first of the powers of the triple containing two zeros.
There is a well-known problem of covering dominoes (link to English), or the problem of dimers. The meaning of the problem is to calculate the number of ways to tile a m × n chessboard with 1 × 2 dominoes, so that the domino knuckles do not overlap, do not crawl over the edges of the board and completely cover the board. For example, if n = m = 2, then there are only two ways (both dominoes vertically or both horizontally).
Now let's “roll” our board into a cylinder, connecting the left and right borders. In this case, any coating can be represented as follows: if the domino pops out over the left edge, then its second half appears on the right, and vice versa. It is required to calculate the number of tilings of such a square chess cylinder measuring 2n × 2n. For n = 1, the answer will be 5, and for n = 2, the answer is 121 ... If it is not very clear, the pictures are on the page of the competition.
Given a square lattice of size n × n. In it, you can find simple cycles with a length of 4, 6, 8, etc., to the largest possible length. [A simple cycle is a cycle that does not have self-intersections]. For example, on a 2 × 2 lattice there is one cycle of length 4. On a 3 × 3 lattice there are 4 cycles of 4 length, 4 cycles of 6 length and 5 cycles of 8 length, that is, the sequence will be the answer [4,4,5]. On a 4 × 4 lattice, the answer is the sequence [9,12,26,52,76,32,6] (lengths from 4 to 16). It is required to name the answers for n = 5,6, ...
So, welcome to all participants. Those who do not understand the meaning of my contests and ill-wishers, please do not show yourself. Good luck
PS. Yes, it would be appropriate to post “I am PR” on the blog, but I don’t have enough karma for this. This post is also related to Sports Programming.
Recently, I like to hold competitions for mathematicians, but these competitions are somewhat different from programming olympiads, at least in that I offer problems that do not have an effective solution algorithm. In addition, tasks are proposed that either no one has ever solved before, or solved very little, but have not achieved significant success. The last feature of these problems is that they are somehow related to enumeration combinatorics, that area of mathematics that was buried in Russia along with other useful areas of science "you know when." But this is less important.
An example of such a competition is a competition on the problem of placing 6 queens on a n × n chessboard. It was first solved exactly in the framework of my competition (an explicit formula for the number of all configurations was obtained) and caused a resonance among those researchers who are involved in enumerator combinatorics. The formula itself allowed researchers of this problem to build new and stronger hypotheses. I expressed my position in relation to such tasks in Habré in this article .
Another competition related to the physics of polymers in the future will allow researchers in this field to show that defective gratings can also be easily calculated, as well as defect-free gratings that are practically unrealistic in the real world. This was shown by calculating the “pre-Hamiltonian” cycles. The corresponding competition was supported by an article on the dynamic programming method . The algorithm described in this article (with appropriate implementation) is by far the fastest in the world (modestly, but it is). With more serious computing power, one could talk about obtaining significant results in enumerator combinatorics ... but dreaming is not harmful. In short, this competition was also useful for science.
Now I am conducting one contest “just like that”, even without a prize pool, and I propose to solve not the most difficult problems from my repertoire. What for? Just so that lovers to compete (of course, in the presence of free time) could compete with other such lovers. The proposed tasks are difficult (in any case, the existence of an effective algorithm for solving them has not been proved), so you will have to fight not in the classical sense (as at the programming Olympiad - for speed and quality), but in the sense of "who has the best approach." And someone can have more power at hand, also welcome. In any case, I personally am interested in not who wins, but the result itself obtained by joint forces in the course of the competition. Practice has shown that the last two of my competitions have proven to be practically useful for science.
Tasks
The contest itself will be held on my blog, which, in addition to other contests, has published posts with a completely different meaning from programming. You just can not pay attention to them, and immediately select the " Contests " section in the menu . The fact is that I cannot create a separate resource for contests for personal reasons and for reasons of insufficient experience in conducting them, so for the time being they will train to conduct them on a blog.
A detailed description of the tasks is given on the pages of the competition, here I will briefly outline the conditions.
Problem 1. Three to the degree of n
The natural number n is given. Find a minimal integer k such that the number 3 k contains at least n consecutive zeros in the decimal notation. For example, for n = 1, the answer would be k = 10, since 3 10 = 59 0 49 and this is the first of the powers of the triple that contains one zero. For n = 2, the answer is k = 35, since 3 35 = 5 00 31545098999707 and this is the first of the powers of the triple containing two zeros.
Problem 2. Dimers on the cylinder
There is a well-known problem of covering dominoes (link to English), or the problem of dimers. The meaning of the problem is to calculate the number of ways to tile a m × n chessboard with 1 × 2 dominoes, so that the domino knuckles do not overlap, do not crawl over the edges of the board and completely cover the board. For example, if n = m = 2, then there are only two ways (both dominoes vertically or both horizontally).
Now let's “roll” our board into a cylinder, connecting the left and right borders. In this case, any coating can be represented as follows: if the domino pops out over the left edge, then its second half appears on the right, and vice versa. It is required to calculate the number of tilings of such a square chess cylinder measuring 2n × 2n. For n = 1, the answer will be 5, and for n = 2, the answer is 121 ... If it is not very clear, the pictures are on the page of the competition.
Problem 3. Statistics of cycles on a square lattice
Given a square lattice of size n × n. In it, you can find simple cycles with a length of 4, 6, 8, etc., to the largest possible length. [A simple cycle is a cycle that does not have self-intersections]. For example, on a 2 × 2 lattice there is one cycle of length 4. On a 3 × 3 lattice there are 4 cycles of 4 length, 4 cycles of 6 length and 5 cycles of 8 length, that is, the sequence will be the answer [4,4,5]. On a 4 × 4 lattice, the answer is the sequence [9,12,26,52,76,32,6] (lengths from 4 to 16). It is required to name the answers for n = 5,6, ...
So, welcome to all participants. Those who do not understand the meaning of my contests and ill-wishers, please do not show yourself. Good luck
PS. Yes, it would be appropriate to post “I am PR” on the blog, but I don’t have enough karma for this. This post is also related to Sports Programming.