By removed1, 15 years ago, translation, In English

Problem A.

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.

Problem B.

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.

Problem C.

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


Full text and comments »

  • Vote: I like it
  • +12
  • Vote: I do not like it

By MikeMirzayanov, 15 years ago, translation, In English
In this topic I would like to raise issues around Codeforces Beta Round # 1. What did you like? What is not liked? What seemed uncomfortable? What can be changed to make participation more comfortable?  I wonder your opinion on contest web-interface. 

Please do not write about access the site with the address http://mirror.codeforces.com/ (I recommended to use http://mirror.codeforces.com:8081/). I guess the problem is around of Apache Virtual Hosts + AJP Connector. Something is configured incorrectly or doesn't work properly because , then it works so good. In short, I will correct. 

I'm waiting for your comments. And, of course, welcome to Codeforces Beta Round # 2. 

Also I would like to see someone who wants to write contest tutorial. This must be done in Russian and English languages. Of course you must solve the problem on either contest, or in the practice. If you have a desire to do it - write in comments. Your post will be published on the main page and later available on special link available from the contest page.

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

By VladimirYakunin, 15 years ago, translation, In English
 
Those who has ever been to chinese market (especially if it was tourists oriented one) know that buying particular thing in China is something more than just pay-your-money-and-go-away.
Chinese sellers have a more artistic approach to their job. Who says any good has a fair price? In China fair price is a function of seller's mood, amount of leisure time the buyer has, current moon phase and Buddha's aura condition.
Here are some tips which were helpful for me and my friends in chinese markets:

Full text and comments »

  • Vote: I like it
  • +12
  • Vote: I do not like it

By MikeMirzayanov, 15 years ago, translation, In English

This post is no longer relevant; it has become significantly outdated. You should read the post at https://mirror.codeforces.com/blog/entry/121114.

Later you'll be introduced to the rules of the Codeforces contests, which differ from those of ACM-ICPC, TopCoder, GCJ, and I hope they'll bring some difference to the world of programming competitions. Most of the official competitions will be carried out according to these rules, though there will be more traditional contests. For example, Codeforces Beta Round #1 will be carried out according to the familiar ACM-ICPC rules. For some time testing will be based on Windows, but things might change in future, fortunately, the system supports testing on different platforms, even within one contest.

At the present time the system is configured to support the following programming languages (the compilation and/or the launching line is shown for each language):

  1. GNU C++ 4
    g++.exe -static -DONLINE_JUDGE -lm -s -x c++ -Wl,--stack=268435456 -O2 -o {filename}.exe {file}

  2. GNU C++11 4
    g++.exe -static -DONLINE_JUDGE -lm -s -x c++ -Wl,--stack=268435456 -O2 -std=c++11 -D__USE_MINGW_ANSI_STDIO=0 -o {filename}.exe {file}

  3. GNU C 4
    gcc.exe -static -fno-optimize-sibling-calls -fno-strict-aliasing -DONLINE_JUDGE -fno-asm -lm -s -Wl,--stack=268435456 -O2 -o {filename}.exe {file}

  4. MS VS C++
    cl /W4 /F268435456 /EHsc /O2 /DONLINE_JUDGE {file}

  5. Free Pascal 2
    -n -O2 -Xs -Sgic -viwn -dONLINE_JUDGE -Cs67107839 -Mdelphi -XS {file} -o{filename}.exe

  6. Delphi 7
    dcc32 -Q -$M1048576,67107839 -DONLINE_JUDGE -cc {file}

  7. C# Mono 2
    dmcs -define:ONLINE_JUDGE -o+ -out:{filename}.exe {file}

  8. C# .NET
    csc.exe /o+ /d:ONLINE_JUDGE /r:System.Numerics.dll /out:{filename}.exe {file}

  9. Java 6, 7
    javac -cp ".;*" {file}
    и
    java.exe -Xmx512M -Xss64M -DONLINE_JUDGE=true -Duser.language=en -Duser.region=US -Duser.variant=US -jar %s

  10. Ruby
    ruby.exe %s

  11. Python 2, Python 3
    python.exe %s

  12. PHP 5
    php.exe -n -d ONLINE_JUDGE=true -d display_errors=Off -d error_reporting=0 %s

  13. Haskell GHC 7
    ghc --make -O %s

  14. D
    dmd -L/STACK:268435456 -version=ONLINE_JUDGE -O -release -inline -noboundscheck {file}

  15. OCaml
    ocamlopt nums.cmxa str.cmxa -pp camlp4o -unsafe -o {filename}.exe-ocaml {file}

  16. Scala
    As Java

  17. JavaScript V8
    d8 {file}

It is not guaranteed that all the problems will have solutions in all the given languages (it's especially about the scripting ones). Probably, I'll later introduce equalizing coefficients for the working time for some languages. A "plus" next to the version name means that the testing system can use older versions. If you have suggestions about the possible ways to change the compilation or the launching line, write about them in your commentaries.

It should be mentioned that apart from standard verdicts, you can get "Denial of judgement", which usually means that your solution can't be launched, or it has unexpectedly failed. For example, is the Delphi array is too big, the compiler compiles the code, but the result will be the incorrect win32 exe-file. Solutions with the verdicts like "Compilation failed", "Denial of judgement", "Judgement failed" will be ignored while summing the results.

Moreover, pay attention, please, that the problems will be given in English as well as in Russian.

That's it, see you at Codeforces Beta Round#1.

UPD: GCC compiler has been added.

UPD 2: Added Haskell and F#.

UPD 3.2: Actual compiler versions are

  • Mono C# compiler version 3.2.3
  • DMD32 D Compiler v2.064.2
  • Delphi 7 [Borland Delphi Version 15.0]
  • Free Pascal Compiler version 2.6.2
  • MinGW g++.exe (GCC) 4.9.2
  • Haskell Glorious Glasgow, version 7.6.1
  • Java 6 javac 1.6.0_45
  • Java 7 javac 1.7.0_72
  • Java 8 javac 1.8.0_25
  • Ocaml ocamlopt 4.00.1
  • Perl v5.12.2
  • PHP 5.3.8
  • Python 2.7.8
  • Python 3.4.1
  • Ruby 2.0.0p353
  • Scala compiler version 2.11.1
  • MS VS C++ 2010
  • JavaScript V8 3.23.0

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By MikeMirzayanov, 15 years ago, translation, In English

I will briefly enumerate the changes at Codeforces:

  • Codeforces beta Round #1 is announced. It will go according to the ACM-ICPC rules, but will last for 2 hours. You shouldn't expect much from the problems - in the first place it is organized to check the system function and your feedback. The problems will be in two language: Russian and English. If I finish all the preparatory work earlier, I'll bring the Round some two days forward. It's planned to have the rating system at Codeforces similar to that at TopCoder. If the beta-competition goes without system failures, the participants will get ratings. To take part you are to register first.
  • The visual organization of “Recent actions” has been changed - "new comment" and "compose/edit text" can be seen in the sidebar. Blog entries are sorted by the date of events, it means the last 15 entries are displayed.
  • A new “Recent actions” detailed page, from which you can clearly see who has been doing what in recent time, is introduced.
  • The algorithm of your "contribution" evaluation has been changed. For more details see below. I think I might change something again later.
  • I've fixed some bugs.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By MikeMirzayanov, 15 years ago, translation, In English
After a two-day stop in Beijing we're leaving for Moscow. The flight is tomorrow, a bit earlier then 2 p.m. Maybe someone else is flying with us? We land at about 6 p.m., and then we'll have to go to the Paveletsky station, it would be great to catch train 17 that leaves at 19:56. Taking into consideration the number of suitcases we have, it seems that the bus/minibus+underground variant isn't for us. Taxi is the only suitable thing, by the way, does someone know how much it costs to take taxi from the Sheremetyevo 2 Airport to the Paveletsky station?

And if everything goes according to the plan, and we catch the train, we'll arrive at Saratov on February 10 at 12:04. As Antonina Gavrilovna says "tired, but hungry". Wait for us.

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

By MikeMirzayanov, 15 years ago, translation, In English

The results are announced - thanks to Ivan Romanov for being so quick. Thanks to everyone who supported us and followed the contest events. My apologies the system break-down, but if everything was stable in Codeforces, I wouldn't have called it beta. Unfortunately, I had no Internet during the day.


Congratulations to the medalists. The competition was tough.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By ivanromanov, 15 years ago, translation, In English
According to Snarknews (in Russian only), Shanghai JTU has become the World Champion for the third time (2002, 2005, 2010), this means it has the same number of victories as the Stanford University and the SPbSU ITMO.

Then goes the Moscow State University (Gusakov, Kornakov, Razenshtein) - the European Champions! Congratulations to the team and to their coach Anton Pankratiev!

The next one is the biggest surprise of this contest (IMHO) - Taiwan National University. Personally for me it was a pleasant surprise, because in November I visited Taiwan - a nice island! I recommend it to everyone. It was my first trip to Asia, a good start .

The following two teams - Kiev State University (Grinenko, Neiter, Simonenko) and Petrozavodsk State University (Denisov, Nikolaevskyi). In person I know only the guys from Petrozavodsk, I'm glad for Alexei, Denis, Ilya, and Denis Petrovich, Vladimir Alekseevich, Victor Nicolaevich - congratulations to all of them!

An interesting fact: the three leaders of the last Petrozavodsk training session took the positions among the five best teams, and in the same order!

The sixth place - Tsinghua. The seventh - alma mater, Saratov SU (Bondarenko, Matov, Yakunin)! Congratulations to Natasha, Dima, Vova, Misha, Antonina Gavrilovna on their silver medals!

The eighth position - Warsaw, a nice city. The ninth - St. Petersburg SU (Antipov, Levin, Smirnov), the forth medal to our North-Eastern European region. 10th and 11th were Zhongshan and Fudan. The 12th was the University that hosted the previous World Championship in Stockholm - KTH, Sweden.

Congratulations to the medalists once again!

UPD. It occurred that SPbSU has the same penalty time as the eighth position. Moreover, there is a chance that Russia will have one more medalist - Ural SU (Burmistrov, Dublennih, Kurpilianskyi) occupies the 13th position and is the last team which solved 6+ problems.

UPD2. 4 gold medals, 5 silver medals (including SPbSU), 4 bronze medals (including UralSU). Totally, NEERC is the Vice-World champion, the European champion, got a gold medal, three silver medals and a bronze one.

Full text and comments »

  • Vote: I like it
  • +24
  • Vote: I do not like it

By MikeMirzayanov, 15 years ago, translation, In English
I think I won't find any strength to describe the finishing day. I will only tell you that it was quite tiring - before the trial contest the guys had to wait for about an hour. Then there was a contest almost as long as the real one.

And now about the most important. The official site of the contest is http://icpc.baylor.edu/, and as for the traditional textual broadcast, you'll find it at Snarknews (In Russian)

You start rooting for us on February 5 at 5 o'clock (Moscow time)

Let's express our thoughts and emotions about the contest in the commentaries under this post. I'm not sure, if I'm going to have the Internet during the contest, but if I have such a chance, I'll write something.

UPD: I've nearly forgotten the most important. Today Bill Poucher announced sad news - the finals in Malaysia are postponed, and where they are next year is still kept secret. Rumors say in Cairo (Egypt).

UPD 2: At the informal tournament ICPC Challenge our team advanced to the finals and took the 4th prize. The Final competition is going to take place tomorrow at the closing ceremony.

UPD 3: I think you'll be able to see the results here. Thank you vici, plus for you!

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By MikeMirzayanov, 15 years ago, translation, In English
Line to open ceremony

The third day was marked by rises and falls of Harbin in our eyes. Everything started with the opening ceremony - it was badly organized, protracted and boring. Right before the opening ceremony the audience went to the assembly hall of the Harbin Engineering University, but the participants were less privileged and had to suffer. We were all gathered in a long basement room, we had to form a line according to predetermined numbers, and wait. As you know, 103 teams take part in the finals, so, about 450 people (coaches and volunteers included) packed into that basement. It was stuffy and crowded there. The Russian teams demonstrated their inherent quick-wittedness, they decided not to stand in the crowd, and moved closer to the entrance, it was cooler and there was more room there.

Finally, to solemn music (be careful, phonogram!) the teams one by one climbed the stage, took pictures and went down to join the audience. As after that according to the program some outdoor activities were planned, many participants had prepared sensibly beforehand, they had put on the presented warm trousers, sweaters, etc. With such a "formal" look they got to the opening ceremony and the shoot. My standing ovation.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it