Hi Gurus and Colleagues!

Sorry for distracting you from coding — but e-maxx-eng project needs your advice — as you probably remember, it is a collection of articles on algorithms seen as important for mastering competitive programming :)

Since the past November project have got real boost — especially due to dedicated efforts of Jakube, adamant and other wise people. So its statistics grew several times, its content too... Over 100 articles and crawling to 1000 daily pageviews... And probably it is now a time to improve its appearance on the web by choosing a dedicated domain name.

Currently it resides on default appengine's e-maxx-eng.appspot.com. It's all right, but probably not extremely clear for people not aware of who is e-maxx, it is 3-rd level — and also clashes with Traxxas E-Maxx toy %)

So it is now tricky situation. It seems to be easy to order a dedicated domain name and bind it to the site. But we can't easily choose one. There were a few suggestions — but probably you'll be able to advice something better suitable — or vote for one of these variants:

• competitive-programming.com — bit too wide, site is not everything about CP
• cp-algorithms.com — looks good for me, though CP is used for other abbreviations...
• competitive-programming-algorithms.com — not sure anyone will type it in
• cs-algorithms.com — similar to cp-algorithms, but more known abbreviation... regretfully more wide too
• e-maxx-eng.com — not clear whether retaining E-Maxx name is a good move or bad
• hard-algorithms.com — not very clever (and like tough-algorithms, tricky-algorithms)
• algorithms-wiki.com, algorithms-hub, algo-hub — however "algohub" is already taken in several variants

So feel free to participate, to suggest, to cast your vote! Also you may express what suffix you feel suits better. Though .com seems to be ok — I personally feel .net or .org may highlight it is not commercial enterprise. Also there is .info — probably it may be more descriptive to the nature of the site.

Few Points: name should not resemble some existing domain too closely (e.g. differ in suffix and spare dash), not should be already taken of course, probably should express some relation to its content :)

Thanks in advance!

I was informed by some bot of removal of wikipedia page about Codeforces.

It was created some years ago when someone asked why there still is no such page. Then some material was added to it by few people, but it seems that either notability criteria were not reached or some other factors were involved (Russian hackers hysteria, maybe).

It is somewhat strange for me, since Codeforces is steaming extremely well, seemingly surpassing Topcoder by popularity and many other sites moreover.

Perhaps some people will decide to invest time and recreate/improve such a page. For now let there be the link to one of the latest snapshots of the page from wayback machine:

https://web.archive.org/web/20160114012719/https://en.wikipedia.org/wiki/Codeforces

Suddenly I've got a few questions in PM and e-mail about Hacktoberfest 2017 participation with e-maxx-eng — I dare to confirm and explain a few details in a post.

1. Yes, digitalocean announced new Hacktoberfest: https://blog.digitalocean.com/hacktoberfest-2017/

2. Yes, it is possible (and easy) to get t-shirt here — just create 4 meaningful pull-requests on github to any meaningful repository (which are accepted) and then claim your T-shirt (you'll need to enter your nickname at their site and then probably your postal address and T-shirt size).

3. Yes, we have tried it in 2016 inspired by Maria (aka Nickolas) — and yes, T-shirts came. I received mine in about a month. (only I think the colors of design were somewhat bleak — see picture below)

4. Yes, e-maxx-eng project is as suitable for contribution as others — you can either translate one of still untranslated pages from original site, or propose your own original article. Please kindly refer to instruction or our 2016 post.

5. As about the effect of our attempt — it seems thanks to all your help was not in vain — current website stats show that user activity gradually increased from roughly 5 to 500 pageviews per day through the year. I know it is not much, but given that site is rather specific in its content and comparatively young — you may be sure people visit it, people read your work.

So feel free to participate. You even need not use git for nowadays github allows editing in web-interface (see instruction and demo-video). Feel free to ask and sorry if sometimes (we are somewhat slow to respond). Feel free to report bugs, suggestions.

And Thanks to Maria (aka Nickolas) for driving this process through the last year!

P.S. As to question "how t-shirts looked like" — I've found a picture in Anna Dodson blog post which may give some idea:

Hi Friends!

Briefly: E-Maxx in English project is now semi-automated so it would be far easier (I hope) to contribute.

Updated web-site is http://e-maxx-eng.appspot.com. It grabs source texts from github and converts them from markdown. So now if you want to add an article, you can do this just in your browser, in github's interface. No more need to kick with local PHP installation etc.

You can read details in Contributors Manual or watch this demo video.

In details:

I've started E-Maxx-Eng project two years ago, as described in this post.

• the first part of idea was that people would be able to add or update texts via GitHub fork / pull-request functionality;
• the second part was to convert markdown article sources into html with PHP script on local computer and then upload result to github pages.

The second part was total crap, as it appeared. I myself felt it is difficult to update the site in such manner so the site soon become forsaken as I got more involved in my personal projects. I'm sorry for this.

I_love_Hoang_Yen provided much help with reviewing and merging recent pull-requests, however I'm afraid it seemed far from comfortable for him either. Thanks a lot to him!

Recently Nickolas wrote to me with the question whether anything could be improved. As I admire and love her greatly, I felt quite ashamed that the project is neglected. So big thanks too! And thanks to everyone who tried to contribute, to help or simply wrote some kind words.

So I composed my brain and tried to make appengine project which can:

• automatically grab new pages from github project as they are merged;
• provide live preview for the text you are going to add;
• and render all these page, so becoming a new e-maxx-eng site.

It seems to work now. Though perhaps you will be able to point some bugs or suggest improvements. Please sorry again for it take that long, but honestly speaking 2 years ago I have no clear idea of how this could be done. We all learn new things by and by.

P.S. I hope we'll be able to add few more "admins" to the github e-maxx-eng organization by and by who have the power to accept pull-requests and also to provide technical advice to contributors (e.g. with github, markdown etc).

Dear Admins and Developers of the CF! Thanks a lot for all your efforts in maintaining and extending the functionality of this wonderful site.

If possible, please change the "Recent Actions" box on the right to be loaded via AJAX. There are two reasons:

• Google crawler is fooled with the topic names from there so when I search in Google for some phrase (trying to find some CF blog post), Google usually includes into results several unrelated pages which by coincidence contained the "recent" link with the phrase during the time the page was indexed — but surely do not contain it now (it is even more important as the site currently have no full-text search of its own);
• less important, but this will allow you easily make this box periodically updating — say, once per minute — just repeating the initial ajax call by the timer.

Thanks in advance!

P.S. Simple example on the first reason: open google.com and search for cool new feature site:codeforces.com — or just click this link — besides the first result (leading to the proper page) there are many others which lead to pages containing no words "cool" or "feature" at all! E.g. Gassa profile etc :)

Hi Friends! Sorry if this was already mentioned. You perhaps know that ProjectEuler was hacked again recently and was shut down for almost a week (since 2 to 7 of August 2015).

It is now back, but Mr. Euler stated they failed to determine how the site was hacked and ask for people skilled in vulnerability hunting to help.

Here is his post in the news: https://projecteuler.net/news

And here are few details about the recent troubles: http://forum.projecteuler.net/viewtopic.php?f=5&t=3937

Hi Colleagues! I need to have about 20 programming exercises (i.e. their statements) translated from English to Chinese, German, French. (this is for CodeAbbey site)

They are on average 100-250 words each (somewhat similar). I can offer small reward — about $25 per 10 translations — about 2 hours work for native speaker. Texts are in Markdown format. Few more technical details could be found here along with texts translated so far (but in different languages). Feel free to contact me with any questions / suggestions.

I'm so pleased — I have first great cheater at my site CodeAbbey. Well... damn! This fellow was not lazy — he copied and slightly refactored about 125 solutions (I believe, shared by his colleague) — and then asked for certificate. Why he want it — no idea! It is not certificate by Oracle or Microsoft. Anyway he spent about 3 weeks and see how it looks like:

original source

source pretending to look different

(And probably it is only my imagination — their similarity?)

Well, jokes aside — I have a trouble — this time it was easy enough to find cheating since there are not too many users — and only few dozens top-users. But if such cases will repeat when there are more people... I may want some automated comparison of sources.

Current idea — I can calculate certain metrics / hashes over the solution and save them along with it. They can be, well, amounts of puncuation symbols, operator symbols etc. And when I need to check the user — we would find few with the closest set of metrics. Something like Locality-Sensitive Hashing. But I before trying to experiment with this blindly I decided to ask clever community — perhaps some people already have worked with similar tasks and could hint on some good ideas to look at / learn from?

I believe, for example, that CF administration have their own tools — but as one wise colleague suggested, they probably are not going to share their know-how to avoid sharing secrets with cheaters at the end... :o

About half a year ago I posted there announcement of my site CodeAbbey. Since then the site have been evolving by and by (many thanks to all people who provided invaluable hints and suggestions!) — and few of them looks funny enough to me so that I'm eager to tell a bit about two of them.

Certificates

They [are awarded] for certain achievements (currently for 125 problems) — and are shown in profile — though you can also print it and hang above your desk. Of course they are still useless papers, but they are somewhat funny I think:

Certificates bear unique number on them so that their authenticity could be verified on site. You may read more here about them.

Interactive problems

They were introduced recently — to solve the problem user is to play a kind of game against a server. HTTP Post requests are used for interchange (sample code fragments in Python are provided).

Currently there are only four such problems:

• Say 100 — simple test that you can work with HTTP;
• Nim Game — also simple but allowing several moves;
• Maze of the Wumpus — by the motives of old game — requiring a bit of heuristic I suppose;
• Connect Four — once popular tic-tac-toe-like game allowing to practice minimax algorithm.

Though of course I hope to add more in future — and to improve clumsy infrastructure of these games also, he-he :)

Concluding I'd say it appeared to be a funny matter to try building my own site, though small and puny. Besides other things it made me acquainted with several interesting people all around the world — I hope I'll be able to write about some of them later in separate posts.

Currently Top Contributors List is the same for English (international) and Russian version of the site.

As sweiss pointed out (here), this means that English-speaking users may see here users without slightest idea what is contributed by them. Especially if most of user's contributions consist of good old Russian Humor instead of programming-related stuff :)

Suggestion:

This should not be hard to build separate contributors list filtered by only English posts and comments and show it on the English version of the site.

This should be more "foreigner-friendly", I think, since this will give some English-speaking contributors a chance to get to this top...

Here was idea about forum for Codeforces — which probably would not be implemented (at least soon) since probably administration have no resources for it.

And then I thought to myself:

But CF already have a cool API. If only we can use it also for Authentication "via CF"! Then surely creating such forums (or other add-on resources) could be done by any 3-rd party enthusiasts!

User only need to click link Login via Codeforces from such resource (and login to CF if needed) — and then the resource will be told by CF about identity of this user, his nickname, color, profile page etc.

This will allow anyone to create custom supplementary resources which could be easily used by CF users!

BTW: this is far easier to implement than the forum! :)

Here was the post on searching for "interesting" job by red coder. And here was the question by Konstantin.Zakharov about whether it is possible to get used to some dull job over the time. So this trashy post is just an answer to this question (I failed to fit it into comment field).

The full question reads like this:

Not meaning to offend with my question — but does not the dislike (disgust?) to dull/general/non-creative job disappear with the time (or age)? What about other people, colleagues etc.? I can say for sure that I met people who enjoy simple job all right!

I'd say that people are different! I think there are two major categories of coders in IT-industry:

1. Those who do coding even when at home, in their free time;
2. And those who do not.

I do not mean they are "good" and "bad" programmers :)
But I learned of the existence of such division late enough. I was telling to some of my colleague of some problem I've recently met at ProjectEuler — and he suddenly asked:

You do coding at home? Why???

And I also asked "And you do not???" — and he answered "No surely, I prefer to watch TV". I said I have no TV (I put it out of my apartments for some good people may take care of it).

Two kinds of coders in industry and their career profile

A couple of years ago I worked in some big outsourcing company. I met several nice people here, working in neighboring project. Let us call them Eve, Peter, Hiram and Simon (all four were senior developers building some national search portal for one of European countries).

During the course of the year Hiram and Simon left the company. Since then they probably changed jobs once more. Also they both are slightly crazy about side-projects.

Hiram tried to create some unsuccessful finance-related web-site, then some multi-player Android game — later they both left their jobs and spent a month on some vague start-up (unsuccessful too as I understand). And now they are hired again by some great high-load related company providing services for giants like paypal etc.

Meanwhile Eve and Peter continue working in the same company where I met them (I myself changed the job twice since then).

They are quite content with the job here. They do not code at home. For them it is a nice job which allows to gain enough money for other activities or hobbies.

Though as far as I suspect Simon and Hiram now have fatter salaries (my own grew about 1.5 times since then).

Conclusion

So I just say — people are different. I suspect that most of coders involved in competitive programming belong to the first group of "passionate coders", but nevertheless there exist many other nice developers. Well, not all of them even know hexadecimal though they may work for many years. I think it is good. :)

P.S. probably it is also worth mentioning that when junior coder gets his first (or second) job, he/she usually enjoys it very much not regarding whether it is dull or creative. But this is because of novelty, so I do not mention this case.

It is a well-known problem for beginners (after learning searching minimum through array): to choose M smallest elements of an array of size N.

Here is an evolution of this problem on bigdata scale:

We have terabytes of log-files, say with N records. Each record contains value for some parameter A (among other auxiliary data). We want to choose M (say, million) records with smallest values of this parameter. How to manage with it?

There are two difficulties:

• source data could not be stored into RAM, so we could not access arbitrary element in O(1) — instead we rely on sequential processing;
• algorithm should be parallelizable since N is about 1e12 and single pass with a single thread will took about a day (however source data are stored in distibuted file system and are accessible by fragments of about 100Mb - 1Gb so several processors may work with different fragments simultaneously).

What approaches there are?

I came up with few basic ideas:

1. Go through source data and store them into binary heap of maximum size M — i.e. next element is skipped if is greater than maximum of the heap — and if it is otherwise stored, then the maximum is popped out of a heap to preserve the size. It will work with about N + M*log(M) but I know not how to parallelize the binary heap... So probably it will not do.

2. If M itself is so large that could not be stored in RAM we can store elements in the list instead of binary heap. After list grows to size 2M for example, we sort it and cut to the size M throwing away unnecessary elements and proceeding. This is well paralelizable but speed is about N*log(M) I think.

3. I like stochastic variant: just pass through data and choose all for which A is less than some threshold k. How to determine this threshold? For example we can make pre-pass and choose randomly as many records as could be stored into RAM. Then chose among them few minimal (in proportion to M/N) and assign the maximum of these minimums as threshold k. Of course we can end up with few or less than M elements (but we can artificially increase k and at the end throw away the surplus).

However all these variants are not extremely good. Could you propose something better, please?

I found this "ancient" computer game browsing through an old book:

Player is controlling the rocket approaching the Moon. Current height and speed are reported along with the mass of remaining fuel.

Player can specify how many fuel should be fed to engines for each next 10-seconds period.

The goal is to land the rocket with the speed not exceeding safe small value (say, 10 m/s).

The physics is obvious enough. New height and speed are reported each 10 seconds, so the height is decreased by roughly speed * 10 sec and speed is changed also according to gravity and working engines.

I liked the idea and readily converted it into exercise for my site and also added javascript "demo" to play it:

Game demo and more thorough explanations

Then I started playing the game myself... Well, it appeared tricky!!!

Sometimes I burned too much fuel before reaching the surface, the rocket lost the speed (or even started climbing up), then began free falling and crashed.

And sometimes I was too hesitant to burn the fuel in time so I crashed with tanks still containing more fuel than I could use (because burning rate is limited by 100 kg / second).

So I came to the question which I currently could not answer:

Which algorithm could help to calculate optimal burning rate settings (for a chain of 10-second periods) so that the rocket lands with safe speed and, additionally, maximum possible fuel left?

M.Gardner in some of his books describes the puzzle: there is a set of squares, each divided into 4 triangular sectors — and these triangles are painted in 3 colors. There exists 24 different squares and it is possible to arrange them into 6*4 rectangle, so that:

• all triangles touching the border of the rectangle have the same color;
• each two neighbor squares have triangles of the same color on their common edge.

To make it more clear, here is an illustration of the solution:

You can try to play with the puzzle at this page.

Gardner told that the author is Percy Alexander MacMahon.

Though it is not easy to find solution at once, there exist many of them. Gardner wrote that some of his readers counted analytically and other with the help of computer the number about 12 thousands.

This phrase made me curious how to write a program to count these solutions.

I have no other idea except to play with puzzle and find out some "laws" about placing some specific squares — and then to write brute-force limited with these laws. But it looks complicated.

So my question is whether there exist easier methods to limit the brute-force or some more cunning approaches?

Four months ago I asked about existence of algorithmic solution for "Color Cubes" game.

Now I created the challenge based on this game — the goal is to gain maximum points:

Color Cubes challenge

Rules of the game are described in this exercise and here is also small playable demo to get better idea.

Here are current stats — you see that during last three days only three participants submitted successful solutions. Perhaps you will decide to join? Be sure, it requires only 10-15 minutes to write the simple code producing answer good enough to be submitted!

Challenge is not limited by any dead-line and no solution is going to be posted officially (though no one is restricted from discussing approaches)

Update

PLEASE NOTE this post have become slightly outdated. Nowadays we have more automated process. So I have just remove outdated technical details and added more contemporary links.

Uptodate info:

Here is the E-maxx site in English: https://e-maxx-eng.appspot.com

And still here is github project with article sources: https://github.com/e-maxx-eng/e-maxx-eng

To contribute one just needs to create PR in github, so generally one even may work in github web-interface for the whole process. Detailed instructions are here https://e-maxx-eng.appspot.com/contrib.html

Older text follows below

Preface

Non-zero amount of users have suggested translating E-Maxx Algo to English. As far as I know some people even started translating in their blogs, though I'm not aware of any attempt seeing great advance and evolution.

This comment suggested to attempt to do this in collaborative manner using github.

I've created a project and pushed few files here. My idea is that we can write or improve articles in Markdown format (you know it since it is used in posts/comments on CF) using pull-requests here (at least at beginning).

The results are converted HTML pages and hosted at the google appengine website.

Remaining is removed to decrease bewilderment

I was somewhat surprised to learn that besides Pi Day celebrated on the 14-th of March we have Pi Approximation Day celebrated today, on the 22-th of July.

Don't be surprised, both link lead to the same page.

I'm curious, whether it is possible to invent the day for another well-known approximation 355 / 113? Well... It could be the 113-th minute of the 355-th day of the year — something closer to astronomic time notation...