It seems everyone is in the know that Codeforces Beta Round#3 didn’t take place in the appointed time. Seemingly, it happened because of the increased popularity of the site, on the one hand, and some of our bugs, on the other. For sure, it’s a pity that things went in such a way. On the other part, if everything had failed during the contest, it would have been worse. The contest is rescheduled for Sunday, 15:00 (Moscow time). Please be sure to check here for the start time in your time zone: http://www.timeanddate.com/worldclock/fixedtime.html?&day=07&month=03&year=2010&hour=07&min=00&sec=0&p1=179
I’d like to remind you that the project is in Beta yet, and we’ll work on the problem and try to fix it.
Thanks for your understanding,
According to The November Revolution of Colors and Titles, the text below is not an actual and just a historical document.
Not so long ago a new rating system was introduced at Codeforces. To complete the picture I’ll tell you about our Table of Ranks.
From this moment on all the participants will be given ranks that reflect their skills and abilities at such a hard field as computer science and problem solving. Judging by the results of previous rounds you will gain (or lose, I hope it’s not your case) points. If you score big success, you are promoted to a higher rank. You can see the dependence between rating and ranks in the table below. Moreover each rank has its color, which is reflected in the table.
As some users have already noticed - contest rating has been added to Codeforces. For now it is in beta too, but it looks very adequate. Here's how it is calculated.
Each person is characterized by their rating, the number R. If person A's rating is RA, and person B's is equal to RB, then the formula
Before updating your rating after the end of the round, for each participant his seed is calculated, that is the place that the participant is expected to take in this competition. Thus, two things are known for each participant - his seed (the expected place) and rank (the actual place). Depending on the difference between these two values, your rating increases or decreases. If the difference is higher, your rating changes more.
There are a few technical points:
As at TopCoder all users are divided into two divisions: the first (rating over
1500 1650) and the second (rating_ not more than 1500 1650). Not rated users fall into the second division automatically.
Wish you high rating,
Thank you all for participating in Codeforces Beta Round # 2. I hope you enjoyed it. You may discuss the problems and system in comments. Please express your opinion, especially if you notice any inappropriate behavior. And as always, I will read with interest the suggestions for improvement.
See you at Codeforces Beta Round # 3.
P.S. And by the way, the round tutorial is waiting for a volunteer. It is desirable that it will be one of the leaders of today's competition. The tutorial should be in Russian and in English. It will be published on the homepage and later will be available via special link from the contest page.
The constraint that edges of each flagstone much be parralel to edges of the square allows to analyze X and Y axes separately, that is, how many segments of length 'a' are needed to cover segment of length 'm' and 'n' -- and take product of these two quantities. Answer = ceil(m/a) * ceil(n/a), where ceil(x) is the least integer which is above or equal to x. Using integers only, it is usually written as ((m+a-1)/a)*((n+a-1)/a). Note that answer may be as large as 10^18, which does not fit in 32-bit integer.
Most difficulties, if any, contestants had with data types and operator priority, which are highly dependant on language used, so they are not covered here.
Let each letter representation of column number be associated with integer in radix-26, where 'A' = 0, 'B' = 1 ... 'Z'=25. Then, when converting letter representation to decimal representation, we take associated integer and add one plus quantity of valid all letter representations which are shorter than letter representation being converted. When converting from decimal representation to letter representation, we have to decide how many letters do we need. Easiest way to do this is to subtract one from number, then quantity of letter representation having length 1, then 2, then 3, and so on, until next subtraction would have produced negative result. At that point, the reduced number is the one which must be written using defined association with fixed number of digits, with leading zeroes (i.e. 'A's) as needed.
Note that there is other ways to do the same which produce more compact code, but they are more error-prone as well.
The points can be vertices of regular N-polygon, if, and only if, for each pair, difference of their polar angles (as viewed from center of polygon) is a multiple of 2*pi/N. All points should lie on the circle with same center as the polygon. We can locate the center of polygon/circle [but we may avoid this, as a chord (like, say, (x1,y1)-(x2,y2)) is seen at twice greater angle from center, than it is seen from other point of a cricle (x3,y3)]. There are many ways to locate center of circle, the way I used is to build midpoint perpendiculares to segments (x1,y1)-(x2,y2) and (x2,y2)-(x3,y3) in form y = a*x + b and find their intersection. Formula y = a*x + b has drawback that it cannot be used if line is parallel to y, possible workaround is to rotate all points by random angle (using formulae x' = x*cos(a) - y*sin(a), y' = y*cos(a) + x*sin(a) ) until no segments are horizontal (and hence no perperdiculares are vertical).
After the coordinates of the center are known, we use fancy function atan2, which returns angle in right quadrant: a[i] = atan2(y[i]-ycenter, x[i]-xcenter)
Area of regular polygon increases with increasing N, so it is possible just to iterate through all possible values on N in ascending order, and exit from cycle as first satisfying N is found.
Using sin(x) is makes it easy: sin(x) = 0 when x is mutiple of pi. So, for points to belong to regular, N-polygon,
sin( N * (a[i]-a[j]) /2 )=0
because of finite precision arithmetic,
fabs( sin( N * (a[i]-a[j]) /2 ) ) < eps