Challenge24 finals are finally over, and as usual, I hurry to share my impressions about them. The impressions are sponsored by team Progopedia (Andrii Maksay a.k.a. maksay, Sergii Dymchenko a.k.a. kit1980 and me). Such things are the best to write immediately after the contest, while the emotions still invade you. Of course, one can start writing them while still in the competition (and last year I did so — I was pretty useless at night anyways), but this year we felt alert and fought for the points till the last minutes of the contest, so the blog post was postponed.

The main part of Challenge 24 took a bit less than 48 hours: registration and optional sightseeing on Friday, the round itself from Saturday morning to Sunday morning, and winners announcement and closing ceremony (for the toughest contestants who don’t really need all that sleep) on Sunday noon.

I’m a huge fan of Surprise/Unknown Language Round competition format. Theoretically I enjoy participating in them, but in practice I mostly run them. What’s so special about them that makes me like them so much?

1. They are unusual. At some point of time (which arrived pretty soon for me) traditional competitions pall and become a blur. If I give it a thought, I can clearly remember only a couple of the 80 SRMS and CF rounds I’ve done. The SRM which featured MooresLaw problem (great challenge phase and my only ever room win), TCO elimination round which I passed thanks to a last-minute submission on 500pt, a GCJ round from back when it was held on TopCoder platform, when I got stuck at input parsing and never got to the actual solution… and that’s all. Marathon memory is a bit better, probably because I’ve participated in fewer of them, and each match took more time and effort. But unusual competitions leave the most lasting and vivid impression.

2. They fit my skills. I’m not the one to get intimidated, let alone scared by a language which misses loops, strings or anything else from the commonly used programmer’s toolkit. Well, there are a couple of languages which I’m uneasy about, but they are very unlikely to appear in an ULR.

Congratulations to KADR who was the first of two people to solve all 8 problems!

171A - Mysterious numbers - 1

The easiest way to make the problem statement unusual is to omit it. This is an extremely convenient approach — you don’t have to maintain the statement in two languages or to worry that it might turn out to be ambiguous or too long or too scary. 690 people solved this problem, so evidently we can omit statements even in regular rounds :-)

As for the problem itself, it required to sum the first number and the reverse of the second number.

171B - A star

They say it’s better to see once than to hear ten times or to read a hundred times. In this problem we decided to check this and to replace the traditional textual statement with a single image. Same as in the previous problem, it did well — at least 645 participants recognized star numbers (sequence http://oeis.org/A003154 in OEIS), the numbers of balls needed to form a six-pointed start of certain size. After this one had only to code the formula —

Editorial

You might have already noticed the next contest in the events calendar, the one named April Fools Day Contest. The name hints that the contest is unusual, nowhere near serious and maybe even snide. One could even guess the author of the contest — the meanest of all out there, that would be me :-)

I love unusual contests — Surprise/Unknown Language which require solutions in unusual languages, Time Limit Exceeded which require solutions in C but written in an unusual manner… Most of such contests exploit the domain of unusual solutions. I’ve decided to take a peek at the dual domain — unusual problem statements.

In this round you’ll be given several weird problems and 2 hours to solve them. The contest will be unrated (you bet!), and it will follow ACM ICPC rules (no hacks, the standings are decided by the number of solved problems and penalty time earned on them). You can submit solutions in any language allowed by Codeforces — of course, unless the problem says otherwise :-)

Be warned, to enjoy competing in this round you’ll need a sense of humor compatible with mine! It’s April Fools Day, after all. Enjoy!

P.S. This contest exists solely due to maksay who volunteered to do all technical preparations. Thanks!

So here goes the editorial. Note that Factor allows pretty random codes, feel free to put all words in one line, but all words must be separated by at least one space, don’t try to skip a space between a bracket and a word or something like that.

162A - Pentagonal numbers

This problem was almost the same as 130A - Hexagonal numbers from Befunge round. Data input and output is done exactly as in the sample code, and besides them the program needs only basic stack operations.

USING: io kernel math math.parser ;

readln string>number
dup 3 * 1 - * 2 /
number>string print

Factor has a very system of built-in libraries which liberate the programmer from solving a lot of basic routine tasks. So after the first (trivial) probllem I gave several one-liners

The contest is over. My sincere respect to the winner in overall run nab who solved all 10 problems in 1h 25m, and congratulations to the winner in the official contest winger who repeated this heroic deed in 1h 52m.

Here is the editorial.

The language of this round is Factor — a stack-based functional language with a sophisticated system of built-in libraries (dictionaries).

Anybody feels like sharing the thoughts about Challenge24 online round? Like who was in which team and who solved what? I miss the detailed information — participants’ countries and total points earned is too little :-)

Here is the list of teams known so far:

Here goes a review of the problems. I tried to set them so that each of them shows a certain aspect of the language — a commonly used verb or a specific feature. Once it was recognized and found, the solution should become evident.

153A - A + B

Let me note right away that the sample code provided in the blog post does work both in Custom test and in ideone (as well as locally), as long as the numbers are written one per line and (attention!) each of them, including the last one, is followed by the end-of-line character. The last ‘n’ is not shown in the tests, but it is there, and COBOL minds it. All test cases at Codeforces are generated with this in mind, so there should be no problems like this when the code is submitted.

The most evident COBOL feature is storing numbers in decimal notation, with width set by the programmer. In this case we focused on the fact that by default the number is printed in a fixed-width way, padded with leading zeros if needed. These zeros where what you needed to get rid of.

The round is over, I hope you have enjoyed it. Here is the editorial.

The language of this round is COBOL (dialect COBOL85), one of the oldest programming languages (date of “birth”: 1959, so it’s twice older than I am). Despite being so old, it’s still in active use, though not in programming competitions, so I think it should be enough of a surprise for you :-)

The problem “A+B” (numbers A and B given in separate lines) can be solved in a following way:

       IDENTIFICATION DIVISION.
       PROGRAM-ID. SOLUTION.

       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01 A        PIC 9(10)   VALUE ZEROES.
       01 B        PIC 9(10)   VALUE ZEROES.
       01 STR      PIC X(10).

       PROCEDURE DIVISION.
         ACCEPT STR
         MOVE STR TO A
         ACCEPT STR
         MOVE STR TO B
         ADD A TO B
         DISPLAY B
         STOP RUN.

A couple of days ago I was asked to answer the question “What is it like to be a problem writer for programming competitions?” at Quora web-site. My first idea of the answer had only one word, but then I’ve thought of a more detailed one, and then of a story I must include, hmm, and I should definitely mention this… Around the second page I realized that this is becoming more than an answer, and at the third one I decided to share this article with a qualified audience — that would be you.

So, what is it like to be a problem writer for programming competitions?

In one word (the one I’ve thought of at first), it’s “awesome”. In a bit more detail, “hard, sometimes unrewarding, but anyways fascinating job”. In even more detail…

А что, кто-нибудь планирует завтра участвовать в TLE? Минус, конечно, что в этом году участие индивидуальное, а не командное, лично мне в хорошей компании было веселее, но контест и сам по себе забавный — на те познания в языке C, в наличии которых в приличном обществе признаваться как-то даже неловко :-)

So, here goes the editorial. I’ll tell you right away that nobody guessed MikeMirzayanov’s problem (nice disguise, er?) — it was problem C about the picky princess. Actually, this was the first problem of the round, the rest of problems I invented to keep up the lovely topic.

148A - Insomnia cure

The number of dragons D can be quite small, so the problem can be solved in a straightforward way, by iterating over dragons 1 through D and checking each dragon individually. Time complexity of such solution is O(D).

Hello,

Codeforces Round #105 will take place on February 2nd, 20:00 Moscow time.

This is a themed round, based on the fairy tales I write in Russian.

In this round we decided to conduct an experiment on smoothing the effects of problem setters misestimating the complexities of the problems: all problems have point values of 1000. We tried to order the problems by increasing difficulty, but this is a subjective opinion, so surprises are possible.

Thanks to MikeMirzayanov for the problem contributed to the round (who can guess which one of the five is not mine?) and to RAD for his help in preparing the problems.

Good luck at the round!

The Unknown Language Round format is becoming popular outside of Codeforces: Chaos. There are only 6 problems, which is less than an ULR typically has, and the problems themselves are easier, but that's a good start.

P.S. I know it's too late for a contest announcement but I had no time earlier - I even got late for the contest itself.

P.P.S. My report of the contest participation: Chaos Chef.

На днях открылась регистрация на замечательный контест венгерского происхождения Challenge24. Лично я его очень люблю - пожалуй, в списке моих любимых контестов он уступает только TopCoder Open. Это вполне естественно - все любят контесты, на которых их приглашают на онсайт в какие-нибудь интересные города :-) Поэтому я решила немного его прорекламировать (и даже сделать это заранее, чтобы не получилось как с CodeSprint).

Участие в контесте командное, причем в команде должно быть ровно три человека. Ограничений студент-не студент нет, равно как и на страну проживания, только что английский знать надо. Единственное требование - все участники должны предъявить подобающее резюме. Кстати, для поездки на онсайт можно заменить одного участника команды по сравнению с составом на момент онлайн-раунда. Очень гуманно, если учесть вопросы виз-денег-"да не поеду я, отстаньте со своими глупостями" :-)

Проводится контест в два этапа: Electronic Contest (онлайн отборочный раунд длиной 5 часов) и собственно финалы-онсайт (24 часа, но об этом я стараюсь не вспоминать) в Будапеште, на которые приглашают лучшие 27 команд по результатам онлайн раунда плюс 3 команды, занявшие первые места в прошлом году. Сразу уточню важный момент: в отличие от общеизвестных турниров, организаторы не оплачивают дорогу и проживание. Впрочем, бумажное приглашение для визы присылают исправно, если попросить как следует.

Codesprint закончился, можно обсудить задачи. Лично я полностью решила четыре штуки:

• Picking Cards - произведение ((количество карт номиналом < i) - i + 1) по i от 1 до N.
• Coin Tosses - рекурсия по количеству орлов, которые осталось выбросить с текущего момента; за один шаг рекурсии рассматриваю один бросок монеты, и получаю либо орла (переход к "осталось выбросить на одного орла меньше"), либо решку (переход к известному матожиданию числа бросков, нужных для того, чтобы выбросить N орлов подряд - 2^N+1-2). Немного начудила - считала не в целых, а в Decimal (Python), так что преобразование в строку получилось страшноватое, но прошло.

Я тут отвлеклась ненадолго от всяческих спортивно-программных вещей и сделала новогодний квест. Правила и сообщения об исправленных багах (буде таковые объявятся) тут. А комментировать можно и здесь :-)

С наступающим!

Update. Разбор заданий квеста.

A. HQ9+

The problem described HQ9+ programming language and asked whether the given program will print anything. Given the extraordinary simplicity of the language, it was enough to check whether the program contains at least one of the characters H, Q and 9.

Codeforces Beta Round #96 will take place on Saturday, December 3rd, and it will be my first classical Codeforces round. To smoothen the transition between Unknown Language and known ones, I've made the problems of the round follow a certain topic, which is of course programming languages :-)

Thanks to MikeMirzayanov, maksay и RAD for their help in preparing this round.

Good luck!

P.S. Points cost for problems: division 1 — 500-1500-1500-2000-2500, division 2 — 500-1000-1500-2500-2500.

So here goes an editorial for the round. For me Befunge is one of the languages in which it's much easier to write code than to read it (and debugging code written by someone else is a complete torture; that's why we don't have hacking in ULRs). That's why I'll post just the general idea of the solution and my own codes — the latter just to show that I can code in Befunge too.

A. Hexagonal numbers

&:2*1-*.@

A "consolation" problem, which requires only to understand the principles of working with stack. Read n, duplicate it, multiply the topmost copy by 2 and decrement the result. Now the stack contains two numbers n and 2n - 1; multiply them and print the result.

The round is over; I hope you enjoyed it. Here is the editorial.

The language of this round is Befunge, a lovely two-dimensional esoteric language. It's quite neat and convenient, especially for an esoteric language. Thus, for example, "A+B" problem, where A and B are given in separate lines, can be solved like this:

&&+.@

To learn the language you can read the original documentation (the rumor is that it is broken in some browsers), examples of programs at Rosetta Code and Progopedia article with annotated examples.

Our testing system uses befungee interpreter, which implements Befunge-93 dialect. To run the interpreter, one needs to have Python installed (version 2.6 or so, but not 3.*). Download files befungee.py, boards.py and funge.py to the directory with your programs and run the interpreter with python befungee.py <Befunge program name> command. Note the built-in debugger (run with --debug --delay=100 option) which allows to watch the movement of instruction pointer through the program and the effect it has on the stack.

As an alternative local IDE you can use WASABI which requires Java. Download interpreter arhive, unzip it and run with java -jar "Wasabi v1_4.jar" <Befunge program name> command.

In input data end of line is marked with #10 character (you'll need this for problems which require reading the string till the end of line). Your program's return is checked to be accurate within the whitespace and line feeds; it's not necessary to end the printed lines with line feeds, and if a problem requires printing several numbers, they can be separated with any number of spaces. Extra spaces at the end of line are also allowed.

Every time I win a trip to any kind of tournament onsites (so far this happened three times, so I can generalize), I find myself facing a serious problem, named "souvenirs". I've settled this question once and for all as long as it concerns myself: the best souvenir is a pile of photos accompanied by a thrilling story. The second-best is a couple of Swiss chocolates, though I can handle both at the same time :-) But one can't live in a society and be free of it; and it's the souvenirs for people around me that become a real problem.

Take, for example, my last year's trip to Las Vegas. I went there with a t-shirt demand from my future husband's sister. Besides, my future husband himself stayed at home (his visa application was unexpectedly refused, and there's not much point in winning a trip without the visa), and I felt I had to bring him something to cheer him up. So my shopping plans were quite intense.

TCO11 - is the second (and hopefully not the last) finals I've visited as a blogger. I hope that not everybody here followed the official blog, and thus my story of this trip will be read as an original art work :-)

Day -1. Arrival

Читали этот мой пост в TCO-блоге? Душа автора жаждет отзывов, ну, и знать, не зря ли TopCoder этот блог затеял вообще, читает ли его хоть кто-то.

Мм, по просьбе как минимум одного читателя примерный перевод.