After quite a pause, I participated in recent Codeforces Global Round 27. After solving A–E in some admissible time but unfortunately struggling for some time with 2035F - Tree Operations, I chose to take the risk and solve the last problem, 2035H - Peak Productivity Forces for which fortunately there was quite much time to sit and figure everything out. Soon it became obvious that it was just a constructive problem without any horrible data structures; one just needs to carefully sort out all cases and not bug a lot. I was very happy to perform it — in these latter days I pretty often feel frustrated that I solve all easy problems (gentleman's set, so to say) but stop at one which is a bit harder, and I seldom am able to solve this one problem (which is usually enough to get a very cool place). Well, today is a nice day!

I explained the problems that I solved right after the screencast itself, you are welcome to watch it: https://youtu.be/WdkTDjb1knw.

UPD: the sound was too quiet, I tried amplifying it: https://youtu.be/jRKJbNO-3kg

Hello!

Recently I published two posts one, two featuring users that were first, second, etc. to reach some rating value.

The reason I was able to create these posts was that preliminarily I downloaded all users' rating change history via Codeforces API. It took some time, but now, when the job is done, I have more than 700000 files, in each one of them a json is stored which represents one user's full rating change history (as an array, and each change consists of the old rating, the new rating, contest name, link and date, taken place and probably something else). I feel a slight feeling of something left unsaid/undone. Probably, because, even though I built that tables, I did not use 99.9% information at all. That simply means that more can be done now!

Could you please suggest some ways to aggregate this data and get some entertaining results? For instance,

• get the rating list sorted by maximum rating rather than the actual rating;
• get the maximum amount of rating gained by someone in two, three, four, five, etc. consecutive contests; or in two, three, four, five first contests taken by the user (though I dislike the idea with the word first as it encourages people to register twin accounts);
• rank all users by the number of times they defeated tourist;
• as a development of the previous bullet, for each user their tourist number can be calculated (it is defined similarly to Erdős number: tourist is the only person with zero tourist number, and for all positive integers $$$n$$$ people with tourist number equal to $$$n$$$ are defined as ones who defeated a person with $$$n-1$$$ tourist number but never defeated anyone with a smaller tourist number);
• rank all users by the number of rated contests (or rated Div. 1 contests, or rated Div.1 + Div.2 contests) they participated in;
• rank all users by the numbers of contests which they won / were second / were third;
• rank all users by the number of contests they participated in (ruban?) / by minus the number of contests they skipped since their first participation;
• rank all users by the difference of their maximum and the minimum rating / by the maximum difference of some reached rating and some previously reached rating / by the number of colors they have been colored in since their fifth contest (although this encourages stalactites and stalagmites);
• rank all users by their volatility (e.g. how many times the sign of their rating change differed from the previous one, or how many times they changed their title or color, or what is the standard deviation of their rating, or what is the sum of absolute values of their rating changes, etc.), or find most stable users who participate a lot but still have a very horizontal graph (or a very horizontal segment);
• find the highest place in which there happened to be a draw in a contest;
• rank all users by the smallest place they reached;
• rank all users by the smallest place which they reached and got a negative delta;
• rank all grandmasters by the number (or minus the number, to discourage twin account creation and encourage hard work) of contests it took them to reach their title;
• rank all users with the substring orz in their handles;
• and much more!

Please share your ideas in the comments and upvote/downvote others' ideas, and I'll try to implement the nicest ones of them!

Note. This is an updated version of this post. If you like this style more, please tell me in the comments.

Since tourist's breakthrough, I've received a lot of requests to update my old posts with rating achievements. However, I wasn't able to do it immediately since my method of doing it requires to download the rating change history of every user, which, in turn, requires to perform several hundred thousand requests to Codeforces, about which the website (and Cloudflare) is not happy. It took more that three days, but finally the job is done!

Below are two tables. The first one is the greatest (by absolute value) negative rating changes. The second one is the first users ever to reach some rating value.

Note. This is an updated version of this post. If you like this style more, please tell me in the comments.

Since tourist's breakthrough, I've received a lot of requests to update my old posts with rating achievements. However, I wasn't able to do it immediately since my method of doing it requires to download the rating change history of every user, which, in turn, requires to perform several hundred thousand requests to Codeforces, about which the website (and Cloudflare) is not happy. It took more that three days, but finally the job is done!

Below are two tables. The first one is the greatest positive rating changes. The second one is the first users ever to reach some rating value.

I solved problems A–D, but I was quite slow, also I had two incorrect submissions for problem A, so my rating delta was -21.

If you want to watch my screencast and editorial, it will appear (UPD: has appeared) behind this link in several minutes: https://youtu.be/NuyV1LIMX3E; or in this box:

And, of course, my warmest congratulations to tourist on reaching 4000 rating points milestone!

The video is already uploaded: https://youtu.be/ItdpgiFG-Bw

The video is already uploaded: https://www.youtube.com/watch?v=9MXalADEPZk

I solved A–F from Codeforces Global Round 26. Unfortunately, I had experienced issues with judgement system, so the participation was a bit spoiled for me, and it was made unrated. Nevertheless, the problems were quite fun, hope I'll become much faster one day!

Please watch! https://youtu.be/4B3g4NLdbuA

I've solved and explained all five problems of Codeforces Round 948 (Div. 2), the video will appear in about an hour.

UPD: the video is available.

I have recorded a screencast & editorial for Codeforces Round 947 (Div. 1 + Div. 2). It will upload on https://youtu.be/DrBmSO86xUQ in an hour or two.

UPD: the video is uploaded.

Tomorrow (in 12 hours) is the main day of my first ICPC WF! The preparation is over. We are not worried, but, unfortunately, after all the rounds of Ptz, UCup, previous years' ICPCps, it is clear to us that we will not win a medal without any luck. Please cheer for us and wish us luck! For two of our team, including me, this is our last attempt at the finals.

You should be able to find us tomorrow somewhere on https://www.youtube.com/@ICPCLive/, we will be 47^th WF St. Petersburg State University team.

Good evening everyone!

TL;DR: I am in Luxor preparing for ICPC WF and making some photos, and also I was offered to (and I will) give an interview to Shayan, please send your questions.

I really liked today's Codeforces Global Round 25! I got a pretty nice positive delta, although, unfortunately, I failed to settle down all the nasty conditional probabilistic formulae in 1951G - Clacking Balls and solved one problem less than I could have.

I uploaded my screencast and editorial on YouTube: https://www.youtube.com/watch?v=4-8kp8B2Dig. Surprisingly, the video is still processing, so it is still impossible to watch it. But it should become available in several minutes.

UPD: the video is available.

UPDUPD: the video is available in high resolution.

Today I participated in a pretty nice CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!) and recorded a pretty nice Screencast and Editorial of problems A–G. You are welcome to watch it!

UPD: now the video is in high quality.

In contests and in the custom invocation, after a pause, one can again find GNU G++20 64-bit. However, the slowdown issue because of which the language disappeared persists, there are still snippets of code that can slow down the execution on Codeforces servers by a factor of 100 or so.

So what is the official position of Codeforces headquarters and of our community on that?

1. Are there general methods of constructing testcases that can exploit this GCC/Windows bug and therefore slow down solutions (like there are anti-hash tests for solutions using unordered_set)? Are there methods that slow down both contest mode and custom invocation mode (since 249807302 is only slow in the contest mode whereas 253289473 is only slow in the custom invocation)?

2. If so, should we expect such tests in future contests, will such methods be used during the test preparation in contests?

3. If this is deemed an unwanted bug, will participants be protected from unscrupulous hacks and tests? (For example, if the solution was hacked or FSTed because of a compiler bug rather than because of anything else, will the author be able to appeal against it and get their solution accepted?)

4. Is there no bug in 32-bit version? If it's 64-bit only, maybe CF team could add a C++20 32-bit compiler? UPD: 32-bit version can also be slowed down, see 253400416.

5. Is there this bug in Microsoft Visual C++ compilers (32 or 64 bits)? If so, is it the reason why we cannot see it among the options?

6. Are there generic methods of protecting against the bug (except switching to 32 bits)? I read (and enjoyed) a blogpost by ToxicPie9 regarding this issue, he suggested to add several lines of code to the solution. However, it does not always help: 253290209 still gets TL (and the author said about that).

7. Has anyone a clue what is going on, why do the aforementioned programs run slowly? Is this bug reported to the GNU or Microsoft developers who are responsible for this strange behavior?

8. Why does behavior in custom invocation and in contest/gym mode differ?

9. Is this bug reproducible on other platforms? For instance, on godbolt there are some windows compilers. Is there a way to slow down this code: https://godbolt.org/z/5G73dfezK (by cleverly choosing the value of evil or anything else)? UPD: probably no way since Godbolt uses UCRT rather than MSVCRT. UPDUPD: this code is slow on Godbolt: https://godbolt.org/z/WE4Mxv9cK, so UCRT is also flawed.

10. Is there surely no such bug on Linux? (Anyway, with regard to Codeforces it is probably a pointless question. I am quite certain that transition of all invokers to Linux is the last thing MikeMirzayanov would prefer to do since it is for sure really costly in time, effort, architecture changes, and/or money.)

Наслаждайтесь! https://youtube.com/watch?v=pnX0ku58JXk

14 January 2024 I tested Codeforces Round 922 (Div. 2). It was under secrecy until the round was published. Now you can see me testing this round! https://youtu.be/yPaIT0h8tcE

Radewoosh вдохновил меня, решив весь Project Euler, и я недавно начал сам медленно, но верно решать оттуда задачи. Буду рад каждому, кто добавит меня в друзья в Project Euler, мой токен дружбы 2127163_HmDkRoxUDZa38znoBSPq2n4Prg996WEX, можете ввести его на этой странице, если вы зарегистрированы и хотели бы видеть меня в своём списке друзей. (Аналогично, и вы появитесь в моём списке друзей.)

Также я записываю весь процесс (на английском) и загружаю на Youtube, так как, согласно правилам, задачи 1–100 разрешено публично разбирать и обсуждать (впрочем, боюсь, в первой сотне не окажется сколько-нибудь серьёзных или интересных задач). На данный момент опубликованы видеоролики:

• задачи 1–3;
• задачи 4–12;
• задачи 13–24;
• задачи 25–36;
• задачи 37–48;
• задачи 49–60.

Это скринкасты, я бы даже назвал их разборами, но (по крайней мере среди совсем начальных задач) объяснять там почти что нечего. В любом случае, если хотите, то смотрите!

Ну и, конечно, призываю и вас регистрироваться и решать задачи, если вы ещё не приступили!

UPD. Неприятно это говорить, но на Project Euler есть лимит в 64 друзей. Таким образом, я не могу добавить в друзья всех желающих.

Поэтому мне придётся сделать какой-то приоритет и удалять тех, у кого он самый низкий. Некоторые варианты вроде времени добавления в список друзей — очень низкокачественные приоритеты, так что рассматривать их не будем. Вместо этого я решил удалять тех, кто решил меньше всего задач. На данный момент требуется 11 решённых задач. Так что, если я вас удалил, а вы почему-то хотите назад, просто решите пару задач и возвращайтесь!

Here you can watch how I solved A–F from Hello 2024: https://youtu.be/3TV2VpVbUjM. Unfortunately, I only solved 1919E - Counting Prefixes after the contest has ended because my C++ template was too poor. This is an important lesson for me to collect all important algorithms and finally sit down and include them in the template.

UPD: the video is high resolution now.

Usually Euclid's algorithm, which computes $$$\gcd(a, b)$$$, is implemented as follows:

while b != 0:
  a %= b
  swap(a, b)
return a

Or, in recursive fashion,

if b == 0:
  return a
else:
  return gcd(b % a, b)

While it works in $$$\mathcal O(n)$$$ time (where $$$n$$$ is the maximum of binary lengths of $$$a$$$ and $$$b$$$ — that is, big-Theta of the length of the input), it uses quite an expensive operation of integer division. The fastest known procedure of integer division works in $$$\mathcal O(n \log n)$$$ time, so, if we take into account the time spent on arithmetic operations, the time complexity is $$$\mathcal O{\left(n^2 \log n\right)}$$$. But even if we don't, int64 division is still much slower than such operations as addition, subtraction and binary shifts.

If you didn't know there is an algorithm which doesn't need division at all!

def remove_trailing_zeros(a):
  return a >> count_trailing_zeros(a)

def gcd_of_odd_numbers(a, b):
  if a == b:
    return a
  if a < b:
    swap(a, b)
  return gcd_of_odd_numbers(b, remove_trailing_zeros(a - b))

def gcd(a, b)
  if a == 0:
    return b
  if b == 0:
    return a
  return gcd_of_odd_numbers(remove_trailing_zeros(a), remove_trailing_zeros(b)) << min(count_trailing_zeros(a), count_trailing_zeros(b))

The function count_trailing_zeros(a) finds the maximum $$$k$$$ such that $$$a$$$ is divisible by $$$2^k$$$. The function remove_trailing_zeros(a) divides $$$a$$$ by the maximum power of two that divides $$$a$$$. Both these functions can be easily implemented in $$$\mathcal O(n)$$$ time, if we take into account the complexity of arithmetic operations. gcd_of_odd_numbers(a, b) finds gcd of the two numbers $$$a$$$ and $$$b$$$, given they are both odd. Everything except the recursive call works in $$$\mathcal O(n)$$$ time. Note that the sum of binary lengths of numbers is decremented by at least one from call to call, so there will be only $$$\mathcal O(n)$$$ recursive calls. Therefore, gcd_of_odd_numbers(a, b) works in $$$\mathcal O{\left(n^2\right)}$$$ time. Finally, gcd(a, b) is also obvious to take $$$\mathcal O{\left(n^2\right)}$$$ time.

My question is: why does everyone use the implementation with divisions? Are there some hidden advantages? I didn't compare how much these two take with fixed-length integer types and arbitrary-precision integer types in practice. Did someone in community investigated this question? Did you know about division-less gcd implementation at all? Please let me know in the comments.

Please watch: https://youtu.be/TutRcb1-K3s

UPD: the video is high resolution.

Here it is, already uploaded, already in high quality. Problems 1917D - Yet Another Inversions Problem and 1917F - Construct Tree were hard, so no editorial, only me struggling to solve them.

Сегодня я поучаствовал Pinely Round 3 (Div. 1 + Div. 2) и решил задачи A–G. Я записал видео участия и выложил сюда: https://www.youtube.com/watch?v=CZ6D-5bhgOQ. Там же вы найдёте разбор этих задач сначала на английском, потом на русском. Вы можете воспользоваться таймкодами, чтобы найти ту задачу, которую вам интересно было бы посмотреть.

Наконец, позвольте поделиться радостью: я неплохо выступил, победил tourist, Petr, Benq и Ormlis и вернул титул международного гроссмейстера!

The ICPC Northern Eurasia Finals (a.k.a. Northern Eurasia Regional Contest) took place on 13 December 2023. The onsite participants competed on four venues: St. Petersburg, Russia; Novosibirsk, Russia; Astana, Kazakhstan; and Kutaisi, Georgia.

Congratulations to the medalists of the contest:

As a result, several teams qualified for the ICPC Finals, which will be held in 2024 in Astana, Kazakhstan:

It is possible that the ICPC committee will increase the quota and allow more NERC teams to attend the Finals.

For the contestants who did not participate onsite, there was an online mirror on Codeforces: 2023-2024 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred). I would like to especially highlight the teams who scored total during the contest:

The problemset was prepared by the jury headed by elizarov: cdkrot, VArtem, Aksenov239, goldvitaly, tourist, kgeorgiy, isaf27, izban, _LeMur_, orz, niyaznigmatul, PavelKunyavskiy, pashka and Elena Kryuchkova:

You can find the PDF statements here, and the tutorials here.

Finally, you are welcome to share your thoughts on the problemset in the comments. Also please tell me if there are mistakes in this post. Thanks to all of you who participated and attempted our problems!

I recorded my participation in CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!), after which I explained the solutions of problems 1896A - Jagged Swaps, 1896B - AB Flipping, 1896C - Matching Arrays, 1896D - Ones and Twos and 1896F - Bracket Xoring. The link to the video is https://youtu.be/xNYdRfbuBQ8, but the video is still processing and will be ready for watching in several minutes.

I guess some of you, who will watch this video, have solved problem C. Could you please share your observations which led to the solution? I believe that the fact presented in the editorial is really unobvious, although I didn't have the worst intuition possible in this problem's plot. Instead I came up with a solution which took a (code)ton of time and featured an intricate way of applying std::set with upper_bound and discrete continuity. Not bad for making the editorial educational, but really inappropriate for succeeding in the actual contest.

UPD: the video is uploaded, but is temporarily in low resolution.

UPDUPD: the video is now high quality.