Nickolas's blog

By Nickolas, history, 5 years ago, translation, ,

TCO15 Marathon Round 3 "PegJumping" has started. It will run for 2 weeks, and this is the last chance to advance to the finals. Once again I'm not the writer but the tester; enjoy :-)

• +18

By Nickolas, 5 years ago, translation, ,

TCO15 Marathon Round 2 "PathDefense" has started. It will run for 2 weeks, and the top 4 will advance to the finals. This time I'm not the writer, just the tester; enjoy :-)

• +26

By Nickolas, 5 years ago, ,

Two papers by kit1980 and me:

• Declaratively solving tricky Google Code Jam problems with Prolog-based ECLiPSe CLP system, The 30th ACM/SIGAPP Symposium On Applied Computing (preprint: http://arxiv.org/abs/1412.2304)
• Declaratively solving Google Code Jam problems with Picat, Practical Aspects of Declarative Languages 2015 (preprint: http://arxiv.org/abs/1504.00977)

And for a lighter reading, Cognitive Biases in Competitive Programming :-)

• +44

By Nickolas, 5 years ago, translation, ,

TCO15 Marathon Round 1 "SmallPolygons" has started. It will run for 2 weeks, and the top 4 will advance to the finals. I am the writer; enjoy :-)

• +66

By Nickolas, 5 years ago, translation, ,

In this contest we aimed to show that declarative approach to problemsolving can be more convenient than the traditional imperative. However, the first several problems were supposed to aquaint the competitor with the basic language syntax and its libraries. All reference solutions are written by kit1980.

To solve a quadratic equation, one has to use a library function sqrt and an if-then-else construct. Besides, this problem was supposed to show that Picat has foating-point numbers. :-)

main =>
D = B * B - 4 * A * C,
X1 = (-B - sqrt(D)) / (2 * A),
X2 = (-B + sqrt(D)) / (2 * A),
if D == 0 then
println(X1)
else
printf("%w %w%n", min(X1, X2), max(X1, X2))
end.


530B - String inside out

A string manipulation problem: library function slice allows to get a substring of the given string, reverse, well, reverses it, and ++ is concatenation operator.

• +45

By Nickolas, 5 years ago, translation, ,

This round features Picat, a language somewhat similar to Prolog. We tried to make most of our problems convenient to solve using declarative approach.

The traditional A+B program (A and B are space-separated) looks as follows:

main =>
C = A + B,
println(C).


The main source of information about language is http://picat-lang.org/ The contest uses version 0.9.

• +140

By Nickolas, 5 years ago, ,

Marathon Match 86 "MovingNQueens" is starting now and runs for one week till next Monday. No gigabytes of data to analyze, no machine learning algorithms to implement (probably), and it even has prizes for the top-4 finishers!

(I am the writer. This announcement begs for a Moriarty-style "Did you miss me?" photo, but I didn't have time to take a photo evil enough :-))

• +171

By Nickolas, 5 years ago, translation, ,

470A - Crystal Ball Sequence

As usual, the first problem tests competitors' ability to do basic math, and in this case it is even easier than the sample — without any loops.

^'0-
\$ 1+*3*1+.

470B - Hexakosioihexekontahexaphobia

This problem uses more advanced language concepts — loop, conditional execution and even named variables! Variables are convenient to use as loop counters and result accumulators, so as to avoid stack manipulations for the same purpose.

• +55

By Nickolas, 5 years ago, translation, ,

The contest is over. 13 people solved all problems — you guys are amazing!

The editorial will be available here.

Today's language is FALSE, stack-based esoteric programming language invented over 20 years ago.

The traditional A+B problem (integers A and B are separated with a space) can be solved like this.

To test your solutions, you can:

• download source code in C of the original interpreter here. Testing system uses this interpreter with -q option.
• use "Custom Invocation".
• use online interpreters (they differ from the reference interpreter a bit but make debugging much easier): 1, 2.

Notes:

1. Language description contains instructions ø and ß. The reference interpreter uses O and B instead (both online interpreters support ø and ß).
2. End of file is encoded as #-1, end of line — as #13#10.
3. The stack MUST be empty when program completes, otherwise the interpreter will post an error to stdout, and output will be judged as incorrect.

Surprise Language Round #7 will take place on September 13th, the Programmers' Day.

The rules of the contest are as follows:

• The contest is unrated for everybody.
• The round uses ACM ICPC rules: the standing is defined by the number of solved problems, ties are resolved based on penalty time. Initially the penalty is 0, and for each solved problem it is increased by submission time (since the start of the contest) + 20 minutes for each failed submission. The solution is considered to be correct if it passes all tests from a predefined test set; you know whether the solution is right immediately after sending it. There are no hacks.
• The round has 8 problems, sorted by estimated complexity, and you have 2 hours to solve it.
• Solutions are accepted only in one language, which will be announced at the beginning of the contest. The language was created a while ago, we didn't invent it for this occasion.
• Please reread this post at the beginning of the contest: we will announce the language and add instructions to install the compiler (the contest interface will provide an option to run your solutions online as well) and links to useful manuals. Other than that, learning the language is up to the competitor. You can use any resources to solve the problems (as long as you remember that this is an individual competition); you don't have to limit yourself to the manuals provided in the post.

I hope that the language I chose will be unknown to most of the competitors.

Announcement of Surprise Language Round #7

• +153

By Nickolas, 6 years ago, translation, ,

Preparing a contest is not as popular a topic as the perennial question of "how to become red in three months", but still it stirs some interest in Codeforces community now and then. Earlier I've written about preparing Surprise Language Round and about emotional aspect of problemsetting; now it's time to share some facts about running regular contests.

Problems

How much time does it take to prepare, select, recall or find problem ideas?

How much experience solving competitive programming problems is necessary to be confident about inventing problems of your own?

Idea generation is a long-term, nearly continuous process. A couple of years ago when I was still an active problemsetter I used to create ideas from literally everything (a squirrel running... hey, this could be a great problem! — seriously, the problem is still there in my drafts, and a pretty complicated one) and to write them down. Then when I had time and inspiration to run a contest, I went through the drafts looking for ideas which would be 1) solvable and 2) nice and unusual enough, and combined them in a problem set.

• +263

By Nickolas, 6 years ago, translation, ,

After enjoying another batch of ten spam posts in "Recent actions" I decided to write a small userscript which would analyze the contents of Recent actions section and deletes from it (and from the main page body) posts written by spammers.

Criteria for deletion (all 3 must be fulfilled):

• Post author is unrated.
• Post author doesn't belong to a white-list (MikeMirzayanov + several other well-known users).
• Recent actions contains at least two posts by this author. Typically a spammer publishes 5 posts within a couple of minutes and then disappears forever. So two-post limitation allows to keep singular posts by honest unrated people, as long as they are writing reasonably often :-)

Well, here is the actual script: http://userscripts.org/scripts/show/486645. If Install button doesn't work (looks like userscripts.org has some problem now), you can copy source code from http://userscripts.org/scripts/review/486645 into a file called cf-hide-spam.user.js and run it separately.

Let me know whether you have any problems with it, and what you think of it in general :-)

• +79

By Nickolas, 6 years ago, translation, ,

Unfortunately, the most anybody could solve was 7 problems out of 9 total. 1289 participants solved at least one problem — this is less than the last year's numbers, but not bad either. Anyways, the key point is the total quantity of fun the people had!

409A - The Great Game

The Most Intellectually Challenging Game In The World turned out to be the famous rock-paper-scissors. One could deduce this from the examples — ok, the rock () didn't look itself, but paper [] and especially scissors 8< looked really lifelike!

Team competition is organized like this: players are split into pairs, with one player of each team in each pair, and pairs play against each other (the first line of input has "moves" of first team's players, the second line — of second team's players). The team which scores more individual victories wins.

By the way, the game is not so trivial as it looks -

• +137

By Nickolas, 6 years ago, translation, ,

The contest is over; I hope you've enjoyed it :-) Editorial is here. See you next year!

The third April Fools Day Contest will take place on Tuesday April 1st. This is a joke competition in which solving the problem is often easier than figuring out what the actual task is. Thanks to kit1980, Skiminok, Gerald and MikeMirzayanov for their help in preparing problems.

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

Be warned, to enjoy competing in this round you'll need a sense of humor compatible with mine! Good luck, and have fun!

• +370

By Nickolas, 6 years ago, translation, ,

This time the language is Ada, chosen not for being particularly crazy (it's too Pascal-like to my taste) but for its name. Indeed, a language named for Ada Lovelace seems to be a perfect fit for programmers' professional holiday. I tried to balance the lack of language weirdness by problems somewhat less trivial than usual.

Here is the traditional solution for "A+B" problem (integers A and B can be given in one line):

with Ada.Integer_Text_IO;

procedure AplusB is
A, B: Integer;

begin
Get(Item => A);
Get(Item => B);
Put(Item => A + B, Width => 1);
end AplusB;


The testing system uses gnat 4.7.2. To test your programs before submitting, you can:

• use “Custom test” tab in the contest interface.
• use ideone, language Ada (gnat-4.6). Remember that by default programs submitted by anonymous are shown in “recent codes”; to avoid this I recommend registering and using "private" privacy option or at least use "secret" option.
• install the compiler locally.

If you use Linux, this compiler is present in the repositories (version 4.4.3 for my Kubuntu). After installing the compiler use gnat make file.adb to compile the code and create the executable. If you have mingw installed, you can run mingw-get install ada and then compile gnatmake file.adb.

September 13th will be Friday the 13th, Programmers' Day — this year not only a professional holiday but also a Surprise Language Round!

The rules of the contest are as follows:

• The contest is unrated for everybody.
• The round uses ACM ICPC rules: the standing is defined by the number of solved problems, ties are resolved based on penalty time. Initially the penalty is 0, and for each solved problem it is increased by submission time (since the start of the contest) + 20 minutes for each failed submission. The solution is considered to be correct if it passes all tests from a predefined test set; you know whether the solution is right immediately after sending it. There are no hacks
• The round has 7 problems, sorted by estimated complexity, and you have 2 hours to solve it.
• Solutions are accepted only in one language, which will be announced at the beginning of the contest. The language was created a while ago, we didn't invent it for this occasion.
• Please reread this post at the beginning of the contest: we will announce the language and add instructions to install the compiler (the contest interface will provide an option to run your solutions online as well) and links to useful manuals. Other than that, learning the language is up to the competitor. You can use any resources to solve the problems (as long as you remember that this is an individual competition); you don't have to limit yourself to the manuals provided in the post.

We hope that the language we chose will be unknown to most of the competitors.

• +230

By Nickolas, 7 years ago, translation, ,

The contest is over; I hope you've enjoyed it. 1465 participants submitted at least one problem correctly. Unfortunately, nobody managed to solve all 6 problems; congratulations to ShadowSong who won the contest by solving 5 first problems with the lowest penalty time!

290A - Mysterious strings

Last year we've verified that a lack of problem statement doesn't prevent participants from solving and submitting the problem successfully and at the same time saves the problem setter some writing effort. This year we've ascertained this again. Well, I could've invented a long and knotty legend about you, a young but very promising software developer, were summoned to White House and given a task of utmost importance: to deliver an interactive list of USA presidents from founding fathers to our days. It could have featured a dramatic time-consuming search for necessary info, pursuits, firefights, a wounded teammate whose dying words were "Eight is Van Buren, don't forget... print Van, just Buren... doesn't pass". But what for?

• +124

By Nickolas, 7 years ago, translation, ,

The contest editorial is available here.

Some jokes are fun only for the first time, repeating them makes them lose their charm. I certainly hope that April Fools Day Contest is not the case, but there's only one way to verify this :-) I'm happy to invite you to take part in the verification process which will take place on Monday April 1st. Let me disprove the suspicions some people have: the joke is the contest contents, not the fact of its existence or the lack of it — that would have been too simple :-)

In this round you'll face 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. To get an idea of what awaits you, you can have a look at the last year's contest.

Be warned, to enjoy participation in this round you'll need a sense of humor compatible with mine! It's April Fools Day, after all. Good luck!

Upd. Registration is open till the end of the contest.

• +406

By Nickolas, 8 years ago, translation, ,

A couple of days ago I wondered how many authors (except for me) write problems about programming languages. I was hoping to be not alone in my passion to this topic; but the reality exceeded all expectations. Of course, problems which feature programming languages are much scarcer than ones about computers, processors, microchips, parallel computing, databases and other IT things, but still much more frequent than ones about, say, dragons :-)

1. TopCoder

The early years of TopCoder presented the participants with several programming-languages-featuring problems.

• +28

By Nickolas, 8 years ago, translation, ,

Roco is a very simple language. On one hand, it's esoteric, so everything you need to know about it fits in two pages. On the other hand, it's powerful enough to enable writing rather complicated programs in it without racking one's brains over each elementary operation (like in Brainfuck). Being able to refer variables using names (numerical, but names nevertheless) is already a gift to the programmer :-)

188A - Hexagonal Numbers

As usual, the first problem tests the competitor's understanding of basic arithmetic operations. The solution is very similar to the example.

iin [0]
mul [1] [0] 2
dec [1]
mul [1] [1] [0]
iout [1]
ac


Starting with the second one, the problems need learning the main feature of the language — the coroutines.

• +38

By Nickolas, 8 years ago, translation, ,

The contest is over; the editorial is here. I've mis-estimated the complexity of the problems — but how could I possibly guess who will arrive and finish everything in 40 minutes :-) Congratulations to the winners — the slowest and the most relaxed of them took under an hour to solve all the problems.

Today's round features Roco — a little-known esoteric language with a special approach to loops and subroutines. The programs written in it look a bit bulky, especially when compared to Befunge, but this is compensated by their relative simplicity and readability. Here is a program which calculates the sum of two given numbers:

iin [0]
iin [1]
iout [2]
ac


There is little information about this language on the web — the only two sources known to me are the author's site and Progopedia article with commented sample programs.

There is also exactly one interpreter for Roco, written by its author. To run it, one has to have C++ installed (the author uses g++, and so do we), compile the interpreter source code into an executable file and run programs using command "roco program.roco". You can download the interpreter here.

Announcement of Surprise Language Round #6

• +79

By Nickolas, 8 years ago, translation, ,

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.

• +73

By Nickolas, 8 years ago, translation, ,

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.

• +58

By Nickolas, 8 years ago, translation, ,

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 - 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 —

• +48

By Nickolas, 8 years ago, translation, ,

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!

Announcement of April Fools Day Contest

• +140

By Nickolas, 8 years ago, translation, ,

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 ;

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

• +42

By Nickolas, 8 years ago, translation, ,

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).