Блог пользователя orz

Автор orz, история, 3 дня назад, По-английски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +281
  • Проголосовать: не нравится

Автор orz, история, 6 недель назад, По-русски
  • Проголосовать: нравится
  • +86
  • Проголосовать: не нравится

Автор orz, история, 2 месяца назад, По-английски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +65
  • Проголосовать: не нравится

Автор orz, история, 3 месяца назад, перевод, По-русски

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

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

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

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

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

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

Спойлер

Полный текст и комментарии »

  • Проголосовать: нравится
  • +229
  • Проголосовать: не нравится

Автор orz, история, 3 месяца назад, По-английски

Here you can watch how I solved A–F from Hello 2024: https://youtu.be/3TV2VpVbUjM. Unfortunately, I only solved 1919E - Подсчёт префиксов 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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +32
  • Проголосовать: не нравится

Автор orz, история, 3 месяца назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +86
  • Проголосовать: не нравится

Автор orz, история, 3 месяца назад, По-английски
  • Проголосовать: нравится
  • +28
  • Проголосовать: не нравится

Автор orz, история, 3 месяца назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

Автор orz, история, 3 месяца назад, перевод, По-русски

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +124
  • Проголосовать: не нравится

Автор orz, история, 3 месяца назад, По-английски

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:

Rank Team = Time
🏆 1 MIPT: Yolki-palki (Pechalka, Tikhon228, Kapt) 12 1266
🥇 2 HSE: Youthful Passion Fruit (alexxela12345, daubi, talant) 10 982
🥇 3 SPb ITMO: pengzoo (iakovlev.zakhar, golikovnik, DishonoredRighteous) 9 713
🥇 4 MIPT: Log-rank conjecture (sadovan, receed, Jatana) 9 759
🥈 5 SPb SU: block of cats (LeoPro, fastmath, turmax) 9 843
🥈 6 SPb SU: \_ -> chill (UnstoppableChillMachine, D.Pavlenko, Volkov_Ivan) 9 904
🥈 7 MIPT: In God We Trust (antonis.white, gop2024, PeregudovSergey) 9 935
🥈 8 MIPT: Shawarmasters (stepanov.aa, RP-1, PBBx0) 9 1072
🥉 9 HSE: Muffix Sassif (sevlll777, crazyilian, tem_shett) 9 1076
🥉 10 HSE: Drunk Driving in Moscow (Siberian, blyat, Nybik) 9 1223
🥉 11 HSE: am nyam) (vaaven, Ormlis, vsinitsynav) 9 1368
🥉 12 MIPT: Wake right (ZorikVar, ShadowLight, serg3000) 8 905

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

Rank Team = Time
🏆 1 MIPT: Yolki-palki (Pechalka, Tikhon228, Kapt) 12 1266
🥇 2 HSE: Youthful Passion Fruit (alexxela12345, daubi, talant) 10 982
🥇 3 SPb ITMO: pengzoo (iakovlev.zakhar, golikovnik, DishonoredRighteous) 9 713
🥈 5 SPb SU: block of cats (LeoPro, fastmath, turmax) 9 843
13 Belarusian SU: 1: Last hope (MathBoy, ne4eHbKa, VEGAnn) 8 944
14 AITU: jaujurek 3 bala (dolbaeb, dimachine, nkamzabek) 8 1089
15 Yerevan SU: SD3 (mcdx9524, Andreasyan, erankyun) 8 1446
16 MAI: 1 (Inyutin, Belousov, Plyushkin) 7 551
18 Belarusian SUIR: 1: So Stuffy (kartel, p3rfect, romarkovets) 7 673
19 Novosibirsk SU: 1: Avdim last hope (amokrousov, Lylova, Timonnable) 7 770
21 Skoltech: Caravella (madn, kek1234, Goldman) 7 819
22 Tbilisi SU: Darwin Nunez (Macharashvili, Pipia, Khvedelidze) 7 834

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:

Rank Team = Time
1 xinyoudui: PubabaOnO, orzdevinwang, jqdai0815 12 842
2 HoMaMaOvO: maroonrk, hos.lyric, maspy 12 1266
3 P+P+P: 244mhq, 353cerega, 998kover 12 1339

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:

Problem Author Developer
1912A - Accumulator Apex Aksenov239 Aksenov239
1912B - Blueprint for Seating VArtem niyaznigmatul
1912C - Cactus Transformation _LeMur_ _LeMur_
1912D - Divisibility Test elizarov elizarov
1912E - Evaluate It and Back Again VArtem VArtem
1912F - Fugitive Frenzy orz orz
1912G - Great City Saint Petersburg cdkrot cdkrot
1912H - Hypercatapult Commute pashka pashka
1912I - Innovative Washing Machine isaf27 isaf27
1912J - Joy of Pokémon Observation goldvitaly goldvitaly
1912K - Kim's Quest Elena Kryuchkova izban
1912L - LOL Lovers orz orz

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!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +193
  • Проголосовать: не нравится

Автор orz, история, 4 месяца назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

Автор orz, история, 5 месяцев назад, По-русски

4 ноября 2023 года в Университете ИТМО прошёл Тридцать первый командный чемпионат школьников Санкт-Петербурга по программированию. Он является отборочной региональной олимпиадой для Двадцать четвертой открытой всероссийской командной олимпиады школьников по программированию, которая пройдёт 11–12 декабря 2023 года в очном формате. Задачи подготовило жюри во главе с andrewzta: ba.tasya, Niko, Thinkbuge, Volkov_Ivan, golikovnik, orz, DishonoredRighteous, Volodya333, polipolinom, GShark, VArtem, peltorator, doreshnikov, Toy_mouse, step_by_step и fedor.tsarev.

По задачам этого набора прошли также несколько других отборов на XXIV открытую ВКОШП. Вот их список со ссылками на результаты:

В настоящее время контест уже выложен в тренировки: XXXI командный чемпионат школьников Санкт-Петербурга по программированию (СПбКОШП 2023) | Отборочный интернет-тур XXIV открытой всероссийской командной олимпиады школьников по программированию (ВКОШП 2023).

UPD: в контест добавлены призраки, чтобы при прорешивании вы могли видеть в таблице результатов, как успехи у тех команд, которые официально участвовали в этом соревновании.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +49
  • Проголосовать: не нравится

Автор orz, история, 5 месяцев назад, По-английски
  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

Автор orz, история, 5 месяцев назад, перевод, По-русски

Здесь можно посмотреть, как я участвовал в Квалификационном раунде Yandex Cup 2023 Алгоритма, комментируя процесс на английском языке.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +29
  • Проголосовать: не нравится

Автор orz, история, 6 месяцев назад, По-английски
  • Проголосовать: нравится
  • +36
  • Проголосовать: не нравится

Автор orz, история, 6 месяцев назад, По-английски

Today a horrible thing almost happened: I barely stayed an International Grandmaster on Codeforces after participation in CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!). I would't say I was exceptionally slow or that I solved problems too clumsily, but for some reason the majority of participants near my level were faster than me on these problems.

I recorded a five hour long video about my adventures. If you're interested in a particular problem, follow the timecodes:

Problem Solving Implementation Editorial
1870A - МЕХанизированный массив 01:37 02:45 3:23:28
1870B - Дружные массивы 06:23 10:54 3:30:20
1870C - Разноцветная таблица 12:48 14:12 3:41:00
1870D - Покупка префиксов 22:14 24:41 3:58:20
1870E - Очередная задача на MEX 39:37 58:42 4:34:24
1870F - Ленивые числа 1:31:03 2:54:32 2:30:37

If you open a video and see it's low quality, you might want to wait several minutes until YouTube processes the higher resolutions.

UPD. This is high quality now. Please watch!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +91
  • Проголосовать: не нравится

Автор orz, история, 7 месяцев назад, По-английски

Dear friends,

Today I tried an experimental format: separate videos. So, today I participated in Codeforces Round 896 (Div. 1) and recorded a screencast, but, unlike the previous times, I did not immediately record the editorials. Instead several videos are dedicated to them. So here are the links:

UPD: I recorded the upsolving of 1869F - Flower-like Pseudotree (see the link above). I guess my explanation was quite fine, but in one case I incorrectly calculated the preconditions, which resulted in WA (223630659) and, subsequently, a huge mess and pain. It is still quite educational stuff though: the first half of the video is just a normal editorial (but, alas, with a technical mistake which should't screw the flow of the problem though), and the second one can teach you how to seek for bugs in problems like this one (with a big number of cases).

Also keep noted that for now the video is low-resolution. It will fix itself in half an hour or so. UPDUPD: the high resolution version has been processed and is available on YouTube.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +67
  • Проголосовать: не нравится

Автор orz, история, 8 месяцев назад, По-русски

Today I participated in Codeforces Round 887 (Div. 1). My experience was terrible (I wasn't able to solve 1852A - Ntarsis' Set during the contest, hope it tells you a lot), but it's still recorded, so hopefully it'll be useful for somebody. As usual, during the first half I participate while explaining aloud what and how I do, during the second part I explain more slowly the solutions of Div.1 problems A–D.

Note that the audio is quite high quality, and the high-quality video is coming in a couple of hours (Youtube is still processing it right now).

https://www.youtube.com/watch?v=2Dvi4WdFliM

UPD: The video now is high-quality.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +21
  • Проголосовать: не нравится

Автор orz, история, 10 месяцев назад, По-английски

Congratulations to Ormlis for taking the first place in a public Div. 1 Codeforces contest for the first time!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +278
  • Проголосовать: не нравится

Автор orz, история, 13 месяцев назад, По-английски
  • Проголосовать: нравится
  • +46
  • Проголосовать: не нравится

Автор orz, история, 13 месяцев назад, По-английски

Today I screencast and explained solutions of problems A–D and F. The video is uploaded to YouTube: https://youtu.be/B48ykX0NpUY

I have to inform that the round quality wasn't exceptionally high: the translation was noticeably Google translated from Russian (for example, представление has at least two meanings — representation or performance, and Google Translate wasn't able to discriminate between these two), the pretests were weak in B, C and F (many people were simply TL-hacked or had their solution fail during system testing). I will elaborate on problem F: there I wrote a square root decomposition with incorrect constants, but still got AC though my solution was incorrect on these simple tests:

2 3
2 2

and

4 24
5 5 5 5

With the first of these, I was able to uphack six accepted solutions, including my own.

Nevertheless I knew what to expect (I call such rounds contests for schoolchildren) and overall experience was satisfactory.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +77
  • Проголосовать: не нравится

Автор orz, история, 15 месяцев назад, По-английски

Good Bye 2022: 2023 is NEAR finished, and I participated in it with usual explanations of everything that I do and with editorial of A–E in the end. You're welcome to watch, the video is already on the channel!

https://youtu.be/VBOi99QMfTw

Полный текст и комментарии »

  • Проголосовать: нравится
  • +58
  • Проголосовать: не нравится

Автор orz, история, 16 месяцев назад, По-английски

Two days ago Northern Eurasia Finals 2022 took place, mirror of which was on Codeforces: 2022-2023 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred). In the next few hours the standings got unfrozen, thereby we know the list of the teams that qualified to the ICPC Finals this year:

1st place 🏆 MIPT: Yolki-palki (Pechalka, Kapt, Tikhon228)

2nd place 🥇 HSE: FFTilted (Kirill22, teraqqq, Ormlis)

3rd place 🥇 SPb SU: Urgant Team (sava-cska, 74TrAkToR, orz)

4th place 🥇 Belarusian SU: 1: Dungeon Thread (Septimelon, RED_INSIDE, programmer228)

4th place 🥇 SPb ITMO: pengzoo (iakovlev.zakhar, DishonoredRighteous, golikovnik)

12th place 🥉 Innopolis: U A (Farhod, Mprimus, Laggy)

14th place Kazakh-British TU: DeoxyriboNucleic Acid (amanbol, Na2a, DimmyT)

15th place SPb HSE: Just3Keks (Xrite, vmos1999, NeKpoT)

20th place Nazarbayev U: wf or gf? (dulatcodes, CMaster, krauch)

23rd place AITU: 1 (Muratov, Aliaidar, Kamzabek)

24th place Moscow SU: apes together strong (voyrus, Vladithur, revelcoS)

27th place BSUIR: #1: So stuffy (kartel, p3rfect, romarkovets)

Congratulations to everyone aforementioned!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +230
  • Проголосовать: не нравится

Автор orz, история, 16 месяцев назад, По-русски

I started coding after I discovered LOUD Enough's cp journey, they showed me that all three barracks can fall simultaneously within first ten minutes of Survival Chaos round

so thank you, tranquility, nikgaevoy, Kaban-5 for your introduction to the CP world

In my deepest gratitude I've drawn all three some of you solving questions on Codeforces site

As Makoto Soejima said, never give up!

please don't down vote, it's my first blog post

Полный текст и комментарии »

  • Проголосовать: нравится
  • +123
  • Проголосовать: не нравится

Автор orz, история, 17 месяцев назад, По-английски

After a bit of a pause I release a new video on my channel — screencast of explanation Codeforces Round 833 (Div. 2). Although my participation was not that successful, I solved five problems and explained all six problems in the video. Feel free to watch!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится