Hi Friends! This problem is one of five in recently closed "semifinal" round of local contest held by MTS mobile operator (true tech champ 2024 or something like this). Out of 5 problems this is the only one I do not know how to approach. Round is over so it should be ok to discuss.

Mobile network operator sells "beautiful" phone numbers. They consist of 11 digits — first four are regional prefix, while other seven could be arbitrarily chosen by customer — the whole eleven-digit number should be prime (to be considered beautiful).

Input data give 4-digit prefix — and output should give the total amount of beautiful (i.e. prime) numbers with such prefix. Example: 8916 yields 396749.

I initially very silly tried to build array of primes up to about sqrt(1e11) = 330000 and then iterate over 5 mln candidate odd numbers, testing with that prime array as divisors.

This is too slow — and no wonder. There could be over 300000 primes in the range and each of them will require trying every of 300000+ divisors :) I tried to use probable prime function from standard library, but it is still slow.

Precalc on 10000 prefixes seemed feasible but I didn't care to try (and anyway precalc time would be significant given 5 hours on all problems).

P.S. contest was notable for some issues so there is no guarantee the problem is not buggy/malformed.

The problem calls digits in integer number "special" if they are "local maximum" (2 points) or "minimum" (1 point) among neighbors. And asks to calculate points for all numbers in a given range. It won't be hard for bruteforce if ranges are not on order 10^18 :) Thus it is most probable some kind of DP but I'm completely out of ideas how exactly to approach it. If someone can give such a subtle hint as direct me without spoiling the solution, it would be great!

Hi Friends!

If you want to have your own website with programming exercises, puzzles and challenges — for your friends, classmates or students — here is something for you, making it pretty easy!

I started my own meek site called CodeAbbey more than 10 years ago — and now it is opensource! Not only you can grab the files here — but there is also an instructive video (see link in readme) how to deploy and setup them on a free hosting (while free, it is not as bad — we use it for years for interactive problems).

https://github.com/codeabbey/src — CodeAbbey Opensource

What is inside?

It is not in ACM/ICPC style — rather submissions are (mainly) judged by the correct answer (if you participated in Facebook Hackercup, you know it is not as bad approach — allows to solve problems in any language). Consequently the site is quite light-weight and can run for years on a free hosting. You can add sandbox for running the code optionally (main site uses this also for some language-specific problems).

There are no short-lived contests, rather problems exist continuously and there is a global ranking users table.

Additionally there is a way to create "challenge" problems which are not judged binary (ok/fail), but may be solved better or worse — thus you can create small competitions on a larger problems (somewhat resembling long forgotten topcoder-marathon or yandex-mathematics).

Problems' checking code could be written in whatever language your chosen web-hosting supports. By default it is PHP obviously, with Python and Perl provision out of the box (though generally free hosting won't give you many options).

There are still some minors features to be added from the code of the main site to the opensource version, but the whole main functionality is, well, just ready-to-use. As the school year is starting, you may find it useful for setting up training grounds for your colleagues, candidates etc.

Video link

Hi Friends!

UPD: the issue described below is clear now and could be traced to some waving reports on the Go itself — their Scanf seemingly mistreats \r\n and Codeforces for some reason still uses windows line ending format.

Could please someone cast a look and help me with debugging curious little issue: 278470193

You see, the code is straightforward — reads number of testcases in t, then on every loop reads number of points in p and points themselves into pts array.

I added debug output after YES and NO answer and see the values were read incorrectly. Most probably I don't know or remember something about feeding input at Codeforces to my code? Needless to say, when I run code locally it works fine.

Hi Friends! Small game for coders have been added at my site: Space Invaders Automation

If you have, perhaps, 30 minutes to spare, I invite you to have fun with it! It is to be coded in Lua, but don't hesitate — language is simple (similar to Python) and we have small introduction, so you'll be an expert in 15 minutes — and can write reasonably good code in another 15, moreover there are a couple examples :)

The goal is to defend against aliens at least for 60 seconds. Current "standings" are (only 3 participants yet):

tzyLee         417 seconds
gardengnome    162 seconds
TestUser (me)   63 seconds

Many thanks to gardengnome for proof-solving it — actually it was he who suggested converting it to "challenge" format — so now you can compete, whose program stand longer!

Perhaps there are a few people who haven't yet learned about Cartesian Tree — this curious data structure allows many interesting uses and actually is very simple! Years ago I read about it here at CodeForces, but felt slightly confused/horrified and put it aside. Very silly :)

Returning to it years ago I created small exercise which could be solved, perhaps, in 15 minute — to help learning the idea, so to say, "practically". Here it is: Cartesian Tree Visualization — feel free to skip the intro about Descartes (kinda local joke).

Regard a simple problem of adding elements to a "list", every time into random place, e.g. in Python:

arr = []
for i in range(1000000):
    pos = random.randint(0, len(arr))
    value = random.randint(1000000, 9999999)
    arr.insert(pos, value)

With what data structure it can be effective? Linked list will allow O(1) insertion, but to find a place where to insert, we need to run O(n) from start. Some variants of trees may allow O(log(N)) insertion but it seems finding the proper index is equally difficult.

Wikipedia suggest Skip List with "minor modification" is what we want. Are there another structures (e.g. perhaps some modifications to some type of tree, perhaps, cartesian) useful for this task?

Hi Friends! Here is the problem created by one of the user's at my site. I don't ask for solution (at least yet, ha-ha, going to try thinking a bit more) — but invite you to check your skills, presumably, at DP.

It has somewhat lengthy description, but boils down to counting number of differing subsequences in 01-string with required balance of zeroes and ones. I quickly started scratching typical DP-like double loop, but soon found it doesn't account for possible duplicates: i.e. in the sequence 1010 we can pick 10 subsequence in two ways but they are not considered different. Results seemingly can grow somewhere to 10^18 so naively keeping all sequences in hashtable doesn't look like a viable approach. Sorry for my naive thoughts, I'm obviously lame at this and perhaps there is a known solution. However if you, like me, don't know it, you can spend some time on it...

Hi Friends!

I know you all are probably busy solving some ongoing contest or preparing to some upcoming. But in case you have half an hour to spend on funny problem without clear solution, I invite you to try Jewels at my site.

You may know this game as "Match-3" or "Bejeweled". Now the question is to write small function to "auto-play" it - i.e. to suggest some good move. Code is accepted in Python or Lua (supposedly many of us know Python anyway — and who don't, I recommend investing 15 minutes in learning Lua — there is "intro" link included).

Writing naive implementation of about dozen lines which iterates over the board and tries to find any valid move probably won't take more than another 15 minutes from you. However running time is limited to 1 second so that it probably is not possible to carefully and slowly examine all possible moves at each step. This means you can try some fancy ideas of "inexact" solution.

We know the problem of "maximal pair matching" (or "maximal matching in bipartite graph) — one of solutions for it is via "maximum flow" algorithms.

But how to solve certain extension of the problem?

Statement

There is a set of 3*N persons, gender-agnostic. We want to split them into N groups of 3.

For every two of them we know the value of mutual happiness of being together in the same group (e.g. we have a diagonally symmetric table 3N by 3N of happiness).

Now, how to maximize happiness? Assuming happiness of a group is sum of 3 pair's happiness in it — and total happiness is the sum over group's happiness.

Any ideas? Iterative random swaps may help in improving happiness but is there precise solution (without brute-force iterating over all possible group arrangements as their number increases pretty fast).

Thanks in advance!

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?