Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Nickolas's blog

By Nickolas, 8 years ago, translation, In English

TCO16 Marathon Round 3 TerrainCrossing started today. It will run for 2 weeks, the top 2 participants will advance to the finals, the top 15 will get t-shirts, and the participants of the first two rounds will finally find out who gets two additional spots in the finals (current unofficial leaderboard). I am the writer; enjoy :-)

Full text and comments »

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

By Nickolas, 8 years ago, In English

If you like Marathons but don't have two weeks to dedicate to participation in a typical match, consider taking a look at the match that will run for 28 hours right before the TCO16 NYC regional event. The coding phase will start on Thursday, June 16 at 8:00 a.m. EDT (in your time zone) and end on Friday, June 17 at Noon EDT (in your time zone). It will be a rated event featuring a somewhat easier than usual problem (I am the writer ;-)) and following the usual Marathon rules (apart from the shorter duration).

And if you happen to live in New York area, consider not only participating in the Marathon but stopping by at the TCO16 NYC regional event at the Google office afterwards: top participants of this match who will be present at the event will get prizes! Nothing as spectacular as a trip to TCO16 finals, I'm afraid, but I hear it's something quite special :-)

Everyone can participate in the match, but to get the prize you have to be present at the NYC regional event.

UPD: NYC Lightning Round ColorCapture is now live.

Full text and comments »

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

By Nickolas, 8 years ago, translation, In English

TCO16 Marathon Round 2 StarTraveller started today. It will run for 2 weeks, the top 2 participants will advance to the finals, the top 15 will get t-shirts, and the participants of the first round continue to compete for two additional spots in the finals! The problem was written by JacoCronje.

Full text and comments »

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

By Nickolas, 8 years ago, translation, In English

All solutions use the same verb definitions to read and write data as the example:

print =: 1!:2&2
read =: 1!:1[3

Besides, the scripts have to end with verb exit ''.

640A - Lazy Caterer Sequence

As usual, the first problem tests competitor's ability to do basic arithmetics. Even in a language so unusual as J arithmetic verbs look pretty standard. Well, except for the fact that in absence of brackets operations are performed right-to-left, without any operator precedence, and division is denoted with %.

Full text and comments »

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

By Nickolas, 8 years ago, translation, In English

The contest is over; the editorial is available here.


The language of this round is J.

The traditional A+B program (A and B are written in one line and separated with space) looks as follows:

print =: 1!:2&2
read =: 1!:1[3

in =. (read-.LF)-.CR
print +/ ". in

exit ''

The main source of information about the language is http://code.jsoftware.com/wiki/Main_Page. Version used is J804.

Full text and comments »

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

By Nickolas, 8 years ago, translation, In English

TCO16 Marathon Round 1 CutTheRoots started today. It will run for 2 weeks, the top 2 participants will advance to the finals, and the top 15 will get t-shirts! The idea of the problem is mine, and implementation was done by JacoCronje.

UPD. TopCoder added 2 more spots in the finals! They will go to people who 1) didn't advance to the finals via standard route, 2) took part in all three online rounds and 3) have the lowest sum of ranks in the three rounds.

Full text and comments »

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

By Nickolas, 8 years ago, In English

I'm happy to see that this year there were 3 people who managed to solve all 7 problems! Unfortunately, only 1097 participants solved at least one problem, which is less than in 2014.

656A - Da Vinci Powers

This problem asked to figure out an integer sequence from two samples and problem title. It turned out to be surprisingly hard, a lot harder than I anticipated. A quick search through OEIS shows that while there are a lot of sequences which have these two numbers in them, only one is related to Leonardo da Vinci (and if you're looking for da Vinci, there are only two sequences overall). http://oeis.org/A221180 is an erroneous series of powers of 2, written down by da Vinci in his diaries and available as part of "Codex Madrid I".

656B - Scrambled

Just one word: typoglycemia.

Full text and comments »

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

By Nickolas, 8 years ago, translation, In English

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


The fourth April Fools Day Contest will take place on Friday 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 and Codeforces team for their help in preparing problems.

In this round you'll be given 7 weird problems 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 ;-) To get an idea of what the contest will look like, you can check out the contests of the past years: 2012, 2013, 2014.

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

Full text and comments »

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

By Nickolas, history, 8 years ago, translation, In English

TopCoder has announced Algo and Marathon tracks of TopCoder Open 2016. There are several interesting things in the rules:

  1. The T-shirts are back! There are 120 T-shirts to be awarded to Algo Round 3 participants and 10 T-shirts for top 10 scorers in each Marathon round.

  2. There will be 10 Algo finalists and 6 Marathon finalists.

  3. Online Algo rounds will take place in different days of week, not only on weekends.

  4. Onsite regional rounds will happen again in Algo track, but this year they are separate competitions. Top 10 scorers in each regional round advance to wildcard round, and top 2 scorers from wildcard go to finals without having to compete in the regular online rounds.

Algo rules

Marathon rules

Full text and comments »

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

By Nickolas, history, 9 years ago, translation, In English

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

Full text and comments »

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

By Nickolas, 9 years ago, translation, In English

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

Full text and comments »

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

By Nickolas, 9 years ago, In English

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

Full text and comments »

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

By Nickolas, 9 years ago, translation, In English

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

Full text and comments »

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

By Nickolas, 9 years ago, translation, In English

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.

530A - Quadratic equation

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 =>
    A = read_real(), B = read_real(), C = read_real(),
    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.

Full text and comments »

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

By Nickolas, 9 years ago, translation, In English

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 =>
  A = read_int(),
  B = read_int(),
  C = A + B,
  println(C).

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

Full text and comments »

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

By Nickolas, 9 years ago, In English

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

Full text and comments »

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

By Nickolas, 10 years ago, translation, In English

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.

Full text and comments »

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

By Nickolas, 10 years ago, translation, In English

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.

Useful links:

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.

Full text and comments »

Announcement of Surprise Language Round 7
  • Vote: I like it
  • +153
  • Vote: I do not like it

By Nickolas, 10 years ago, translation, In English

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.

Full text and comments »

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

By Nickolas, 10 years ago, translation, In English

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

Full text and comments »

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

By Nickolas, 10 years ago, translation, In English

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 -

Full text and comments »

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

By Nickolas, 10 years ago, translation, In English

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!

Full text and comments »

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

By Nickolas, 11 years ago, translation, In English

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;
use 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.

Full text and comments »

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

By Nickolas, 11 years ago, translation, In English

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?

Full text and comments »

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

By Nickolas, 11 years ago, translation, In English

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.

Full text and comments »

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