For everybody new to cp-algorithms.com. It is a community project, that started as a translation project of the Russian algorithm website e-maxx.ru. In the meantime most of the articles are translated, multiple new articles have been added, old articles have been improved and extended. In total we have 143 article about different competitive programming topics, anything from algebra, graphs, string algorithms, data structures, geometry, and more. So check it out ;-)

Although in the last months not many improvements/new articles has been done (I've been busy with work/study), the website is still growing a lot. Especially last October we had a lot of new content. A year ago we had translated only 71% of the Russian articles from e-maxx.ru, today over 85% are translated. And according to Google Analytics the number of users is growing still a lot. Last year we had over 250.000 users. The following graph shows the user numbers of the last 3 years.

As every year, we want to remind people of the Hacktoberfest. It is an initiative by DigitalOcean. They will award everyone (well, actually the first 50.000 people) which will make 4 pull-requests on Github during the month of October with a cool, free shirt.

As we also develop cp-algorithms.com using Github (see link), this is a perfect opportunity to join our project, help a little, and earn a free shirt. You just need to register on their website, connect your Github account and start making pull-requests.

If you want to join, we prepared a page explaining how to contribute to the project, and how to make a pull-request on Github. Take a look here: link

We use Markdown, Latex (for mathematical formulas) and Git/Github for development. Markdown and Git are very simple technologies, that everybody has to know if he ever wants to work in IT. And Latex is also taught at any technical university. So you don't have to learn any new difficult technologies, that you can't use in other projects or in your job.

You don't talk Russian? No problem, I also understand not a single article without the help of a translator. Luckily there are really good automatically translators, that you can use. Google translate and Yandex translate work pretty good. They are not perfect (e.g. Google translate might say top instead of vertex), but from the context it is always clear what the correct translation should be.

So what exactly are the task that you can help us with? We are pretty much open for everything:

• Translating an article. Here you can see the list of all articles that still need a translation. (Warning! Only choose to translate an article that you understand very well. Some of the remaining articles are quite advanced.)
• Write a new article. There are still many topics that are not covered. For instance:
  • Binary search
  • Introduction to dynamic programming
  • SOS DP
  • Digit DP
  • ...
• Improve old articles. E.g. some articles are written in a bad style of English, some of the explanations are pretty bad, some code pieces are unnecessary long, or the opposite — too short, ...
• Add practice problems
• Add images
• Styling: the website looks quite old, some redesign could be really cool.
• See the issues page:
  • Fixing an CSS bug: No margin-top on div#footer
  • Replacing Graph algorithm with SPFA
  • Add implementation for k -th smallest number in an array range

I hope most of you know your project e-maxx-eng. If you heard about it the first time: there is this really awesome Russian website (link) about algorithms used in competitive programming by e-maxx. e-maxx-eng is a community project that translates the material, so that competitive coder from all around the world can read and learn from the incredible useful and detailed source. Currently we have a pretty good and huge number of articles about algorithms, data structure, their implementation, lots of applications and general useful tips.

Here's a quick updates on what we achieved in the last year:

• There are translations available to over 100 articles (about 71% of all articles). Last year it was only about 45%.
• We published a couple of original articles (e.g. about the Sqrt Tree, Convex hull trick and Li Chao tree, or about the stars and bars theorem).
• We purchased a dedicated domain: http://cp-algorithms.com/
• We added test cases (hidden), which test the code snippets in some articles for errors. This helped finding quite a few bugs.
• We have increased the number of readers by a lot. Especially in the last few months we had more than 500 users each day, according to Google Analytics.

A huge thanks to the other project admins RodionGork and Nickolas, and to the countless other helpers, who translated articles, written new articles, fixed bugs in the code, improved articles, reported bugs, ...

We are developing the website on Github. And as always, we are looking for new helpers, to translate more articles (there are still a bunch missing), create new articles, and improve the website in general.

To make it more interesting, we will join Hacktoberfest for the third year in a row. Hacktoberfest is a really great initiative by DigitalOcean. They will will send a free shirt to everybody who makes 5 or more pull requests during the month of October. So this is a perfect opportunity to join our project, help a little, and earn a free shirt. For this you have to register on their website and connect your Github account.

If you want to join, we prepared a page explaining how to contribute to the project, and how to make a pull-request on Github. Take a look here: link We also prepared a page where you can see the translation progress. It shows exactly which articles still need a translation, and which ones are already translated.

We use Markdown, Latex (for mathematical formulas) and Git/Github for development. Markdown and Git are very simple technologies, that everybody has to know if he ever wants to work in IT. And Latex is also taught at any technical university. So you don't have to learn any new difficult technologies, that you can't use in other projects or in your job.

You don't talk Russian? No problem, I also understand not a single article without the help of a translator. Luckily there are really good automatically translators, that you can use. Google translate and Yandex translate work pretty good. They are not perfect (e.g. Google translate might say top instead of vertex), but from the context it is always clear what the correct translation should be.

So what exactly are the task that you can help us with? We are pretty much open for everything:

• Translate an article. Here you can see the list of all articles that still need a translation. Here are some short and simple articles, which might be suited for beginners:
  • The factorial N! modulo P
  • Finding the largest zero submatrix
  • Finding rank of a matrix
  • Integration by Simpson's formula
  • Covering segments
  • Check if point inside polygon
  • Segment intersection
  • Eulerian path
  • Joseph's Problem
  • Find maximum subsegment
  • Theory Spraga Grande. Nim (I'll accept incomplete translations, the article is long...)
  • Finding the equation of the straight line to cut
  • The centers of gravity of polygons and polyhedra
  • inverse SSSP problem
  • inverse MST
  • The Tree Stern-Brocot. A Number Farea
  • ...
• Write a new article. There are still many topics that are not covered. For instance:
  • Binary search
  • Easy/advanced DP techniques
• Improve articles:
  • Fix bugs in code snippets.
  • Reword sections that are hard to understand
  • Fix spelling or grammatical errors.
  • Create helpful images and add them to an article.
  • Add practice problems to articles.
• Design a new template for the website. I don't like the current design, it looks pretty old and outdated. Maybe somebody is talented and creates a complete new look.
  • Current template can be found here

So if you want to help (and earn a free shirt :-P), join our project and start with a task. If at any time you need help during some task, have questions about the project, or just want to talk, write me a message. I'm happy to help with anything related to the project.

I solved 986F - Oppa Funcan Style Remastered today and faced the following problem.

You had to solve a linear diophantine equation:

This is of course quite easy, with the extended Euclidean algorithm you can find a solution:

and by multiplying with c / g gives a final solution:

And all solutions can be written as

The problem is, that this can easily give an integer overflow. E.g. when a, b and c are as large as 10¹⁸. To solve the problem I just took my BigInteger implementation. But this is of course quite ugly (400 additional lines of code just for one simple calculation).

How can we avoid the overflow? I want a solution for a·x + b·y = c with |x|, |y| ≤ 10¹⁸.

I found the following code in the solution of tourist. But I'm unable to wrap my head around it. Can somebody explain me the logic of this formula?

g = extgcd(a, b, x, y);
if (c % g != 0) {
  return false;
}
long long dx = c / a;
c -= dx * a;
long long dy = c / b;
c -= dy * b;
x = dx + mulmod(x, c / g, b);
y = dy + mulmod(y, c / g, a);
g = abs(g);

On the e-maxx website about the Disjoint Set Union data structure there is a paragraph about computing range minimum queries offline using DSU. (http://e-maxx.ru/algo/dsu#15)

It is claimed that it works in O(α(n)) time per query on average (α is the inverse Ackerman function).

My Russian is terrible at best, and the Google/Yandex translations also is quite hard to understand for this paragraph. So I didn't really understand the complete idea and have some questions about this one.

From what I can understand using Google translate is the following:

• this only works if the elements are actually a permutation of 1 to n (otherwise we would have to sort the elements beforehand)
• for each index in the array we store the reference to the closest query that ends right of the index.

From this information I was able to construct this tree/forest structure. (red are the range queries, blue arrows are the references that point to the parent)

Now the algorithm then goes as follows:

• We start with the empty array.
• We insert the smallest number 1 and follow the references. In that way we visit all range queries where 1 is the answer. Therefore we can answer those, and shorten some of the paths via path compression and Union by rank (the typical DSU optimizations).
• The repeat the procedure with the other elements in increasing order.

I'm pretty sure I know how to create the data structure in linear time [first store every query (left, right) at left, then do walk through it and store the queries at right (this assures that multiple queries that end in the same element are sorted by size in descending order). Then iterate over those in reversed order keeping a stack with the current biggest/active queries.]

So everything looks quite lovely and fine.

But now I have one main concern.

I'm pretty sure that I can create test cases in which a query takes O(n) time on average. E.g. take the sorted array 1, 2, 3, ..., n, and taking n/3 queries of the type [1, 2n/3], [2, 2n/3], [3, 2n/3], ..., and the add n/3 queries of the type [n/3, 2n/3], [n/3+1, 2n/3+1], [n/3+2, 2n/3] ... For each inserted element we would have to iterate over all n/3 queries of the second type to be sure that none of these has the current element as answer. Because theoretically they could all start at the index 1 of the array.

So my question: Have I completely misunderstood what the Russian explanation says? Do I have to structure the DSU differently? Or is the explanations wrong and doing RMQ with a DSU in that time actually impossible?

Btw, searching for this algorithm / implemenation / papers produced nothing. It seems that this is only documented on e-maxx.ru.

Last Educational Round I solved 6/7 problems, but one of the problems 911G - Mass Change Queries got hacked in the 24h hacking period. Since then I tried to fix the solution and submitted it a few times, but still had no luck.

The bug on Codeforces is, that it shows the problem incorrectly as solved. On the PROBLEMSET page, the problem has a green background. And on the CONTESTS page it shows: Solved: 6 out of 7 (although it should be 5 out of 7). Only on the contest page itself Educational Codeforces Round 35 (Rated for Div. 2) the problem is correctly colored with red.