Hi everyone!

Sponsored by

Last Sunday marked the conclusion of the fourth Osijek Competitive Programming Camp (OCPC). In this camp, 54 teams solved at least one problem, of which 10 teams participated onsite. Congratulations to the top-3 teams by overall rating:

1. Singapore Legged Forces: first place cheated 🤙 (Wailydest, errorgorn, 244mhq)
2. Kyiv National University: 0_GB_RAM (KostasKostil, kostia244, VladProg)
3. Competitive programmers sometimes hide their feelings in the code (Savior-of-Cross, tfg, Sana)

QuantCo Challenge

For this camp, QuantCo joined us as a platinum sponsor. As a part of the sponsorship, we organized a fun CTF-style event with prizes for the camp. Camp participants were allowed to join in teams of up to 4 people and participate in the CTF challenge virtually in a 3 hour window within 24 hours of the second day-off. Congratulations to the winners:

1. bimbimbambam (244mhq, Wailydest, errorgorn, kostia244).
   Prize: WEEFUN Upgraded Tina2 3D Printers!
2. KIVI_GB_RAM (VladProg, KostasKostil, Denisov).
   Prize: QuantCo branded headphones.
3. 4inaz3s (Valera_Grinenko, Barichek, Mustang98, BigBag).
   Prize: Digital planners.

Thank you, QuantCo, for the event! I think it was very fun, and I hope that we can do something similar in the future :)

Day-off activities

As usual, we had social outings during camp day-offs: Our participants played paintball on Monday, and bowling on Friday.

I like to think that our far ancestors played ping pong on such stone tables... :)

Also this time I noticed a ping pong table in the courtyard, and got some spare ping pong net, rackets and a ball to play it with some of the camp participants. The experience was somewhat unusual, as the ball movement were less predictable due to wind and stone table material, but nevertheless fun. I jokingly called it playing ping pong on hard mode 😁

Overall, the whether in Osijek in Summer is pretty hot (up to 35℃), which makes it somewhat difficult to run some outdoors activities during the day, but on the other hand Osijek also has a very nice river beach in 15 minutes walking distance from the camp site, and I had some great time swimming there when not being busy with the camp stuff!

Retrospective

Overall, this camp had fewer participants than some previous camps, which we attribute to a combination of factors:

1. Tight scheduling: Due to ICPC WF being early, and the Osijek university being on holidays in August, we had no choice but to schedule for the first week of September, leading to an unfortunate intersection with IOI 2024;
2. University holidays: Many people have internships/exams/personal holidays in Summer;
3. Abundance of training opportunities: Many teams were overwhelmed by 3 distinct training camps hosted in Europe, and many were too exhausted to join all of them;
4. Complicated commute: Most places require 1-2 layovers when going to Osijek by a plane.

Unfortunately, not all of these factors are within our control. For example, while I was often granted an official leave from my studies or internships to attend training camps, I understand that not all participants are comfortable asking for this (or might not want to spend personal leave days on this), and not all companies/institutions would actually grant them even when asked.

However, we still want to mitigate these issues to the best of our ability! That being said:

• Location: We are exploring options of opening mirror sites and possibly moving the main site. If you are connected with a place that may be interested in hosting an OCPC event, please reach out to me!
• Schedule: We will reach out to potential participants in advance, and consult them about best dates to arrange the camp.
• General: We will try our best to make participation in the onsite camp more attractive to potential participants. While it is still too early to talk about any specific arrangements, I really hope that it will work out, so stay tuned!

And, of course, feedback is very important to us, both from people who participate and from people who would potentially like to participate, but for some reasons can not. If you hesitate about participating, but in principle it is something of interest to you, I'd really appreciate it if you reached out to me, so that we can discuss the issue and try to improve in a way that will resolve your doubts.

Other than that, thank you everyone for your attention, and hopefully see you this winter :)

Hi everyone!

We are thrilled to invite you to The 3rd Universal Cup, Stage 6: Osijek, taking place on August 10th, 2024.

This stage is based on the Potluck contest of OCPC 2024 winter, which featured 52 official teams competing onsite and online during the camp. If you like the contest, please consider participating in our future camps, so that we are able to deliver more high quality contests in the future. Your continuous support is essential for OCPC to keep running and be able to compensate problem authors!

I would like to thank all authors for their efforts on preparing the contest: ToxicPie9, flamestorm, jeroenodb, -is-this-fft- and adamant.

We are looking forward to your participation!

Hi everyone!

Sponsored by

We are happy to announce that Osijek camp will be returning this Autumn, on August 31-September 8 2024, right before the ICPC World Finals 2024 on 15-20 September 2024 in Astana, Kazakhstan. The camp is hosted by the School of Applied Mathematics and Computer Science of the University of Osijek and is brought to you by the organizing team of adamant and -is-this-fft-.

The camp is inspired by various competitive programming camps that we attended during our active years in ICPC, and is aimed to help college students prepare for ICPC regional contests and finals. The camp will consist of 7 ICPC-style contests and 2 days off.

Details

Participation fee for onsite participants is 150€ per person. It does not include regular meals, travel or accommodation. Some further details about location, travel and food options can be found on the website.

If you want to participate, but are unable to come onsite, we offer a reduced fee of 100€ per person for online participation. It is also possible to reduce fees individually if you are unable to attend some of the contests. This will be handled on a case-by-case basis.

We support and empathize with those affected by the ongoing war in Ukraine, therefore we offer a 100€ discount for affected individuals and teams affiliated with Ukrainian institutions. In other words, the fees would be 50€ and 0€ per person for onsite and online participation correspondingly.

The expected starting time for the contests is 10am CET. For online participants, it is still a preferred starting time, but we will make accommodations for virtual participation at a later time, whe really necessary.

Most of our contests are originally developed for the camp. A small number of contests may be based on previous contests that have not been released to the general public. If you have seen some problems of a contest before, you can't participate on that day. We will privately contact participants who might be affected.

After the camp, we will have a silence period during which camp materials will not be released to the public. We ask participants not to discuss the problems in public unless they obtained an explicit permission from contest authors.

Participants

If you are interested in participating, please fill the form here.

We ask you to register before August 23 if you want to participate online and before August 16 if you want to participate onsite.

Also, if your university or organization has a lively ICPC community that may be interested in attending the camp, and you have some contacts of people in charge (e.g. coaches) we would highly appreciate if you could share some details in a direct message to me (adamant) or Tähvend (-is-this-fft-). Thanks!

Problemsetters

We'd like to thank and praise the authors of the contests in the camp:

• conqueror_of_tourist — ICPC 2022 world finalist. Codeforces LGM in Python.
• tfg — ICPC 2018 and 2019 World Finalist, sqrt decomposition enjoyer and the person that optimized the intended complexity of 1508F - Optimal Encoding.
• Farhod — Codeforces IGM, 2x IOI silver medalist, hates ad hoc problems.
• Amtek — CERC 2022 and 2023 champion. ICPC 2023 and 2024 finalist.
• jacynkaa — CERC 2022 champion. ICPC 2021 and 2023 finalist.
• teapotd — CERC 2019 and 2021 gold medalist. ICPC 2020 and 2022 finalist.
• wuhudsm — Codeforces Master, maintainer of TheForce community, author of over 100 competitive programming problems.
• chromate00 — Problemsetter of 28 tasks on Baekjoon, also known for blogs reinventing the wheel several times.
• ToxicPie9 — ICPC 2021 and 2022 finalist. Authored more geometry than non-geometry problems.
• Mustang98, BigBag, Barichek, Denisov, Valera_Grinenko — ICPC World Finals 2020 bronze medalists, SEERC 2023 champions.
• Kevin114514, yaoxi_std, JCY_, Daniel_lele, ducati, Evier., WaReTle, J.Doe, schrodingerstom — students of Nanjing Foreign Language School.

... And others. We would also like to thank Arpa, two times ICPC World Finalist and former Codeforces Contest Coordinator, for his help with reviewing problem proposals. You can find more details about contest rules and technical setup on the website.

Special thanks

Finally, we say special thanks to

• our sponsors, who make the camp possible;
• ICPC foundation for their help and support;
• Codeforces for guidance and promoting this announcement to the main page;
• eolymp for providing an online judge for the contests;
• School of Applied Mathematics and Computer Science of the University of Osijek for the invaluable help and providing a physical location for the camp.

Hi everyone!

Today, I noticed a comment by djm03178 who at the moment has +51 successful and -23 unsuccessful hacks in Round 952. If you look on the hacks, you'll see that e.g. last four were made in the span of one minute, and there are similar streaks before that.

It looks like djm03178 (and, to be fair, some other users too) uses some kind of automated tools that detect solutions using unordered_set or unordered_map, and then send hack tests in bulk. From my perspective, hacks that exploit programming language's internal bugs are generally unsportsmanlike and should not be encouraged, as hacks (imo) were designed to exploit algorithmic inefficiencies, rather than obscure language properties.

But even that aside, Codeforces rules seem to forbid using any kind of assistive tooling for hacks:

Attempting to digitally extract other contestant's code during the hacking is considered cheating. You may not use any technical/digital tools to obtain other contestant's code, including (but not limited) OCR, traffic capture, browsers plugins and so on. The only allowed method to analyze other contestant's solution is reading it in a hacking window. However it is allowed to manually retype the solution or it's parts to run it locally.

Sure, it may be questionable whether the paragraph applies when it is unofficial participation, and in an open hacking phase, where you can just copy paste code directly, but the wording as it is now is prohibitive in all cases. It also seems that such extensive hacking creates additional load on systests, as stefdasca recently noticed, so such automated hacking are also likely to violate the following:

You are forbidden to perform any other actions that can in any manner destabilize the judging process.

Also pinging MikeMirzayanov to draw attention to the situation and for potential comments.

Hi everyone!

Quite recently, a problem named Palindromes in Deque was added to the Library Checker that asks you to execute the following:

1. Add a character $$$c$$$ to the beginning or the end of a string $$$s$$$;
2. Remove a character from the beginning or the end of $$$s$$$.

In-between the queries you also need to maintain the number of distinct palindromes, and the size of the largest prefix- and suffix-palindromes of the current string.

The problem on Library Checker uses the approach from Double-Ended Palindromic Trees article by, presumably, liouzhou_101. The paper is quite long though, so after briefly looking through introduction part to familiarize myself with their main concepts, I decided to do something a bit different than they did. In this blog, I will explain my approach.

Hi everyone!

Shayan invited me for an interview on his YouTube channel, to which I agreed. The interview will be recorded, hopefully this weekend, and made available on Shayan's channel (hopefully) shortly after. If you have any questions that you'd like me to answer during the interview, please feel free to post them in the comments below or in Shayan's Discord server.

A bit of context about myself, in case you don't know yet:

• I was born and raised in Zaporizhia (Ukraine), then I graduated Moscow Institute of Physics and Technology with Bachelors degree, then I worked at think-cell in Berlin, at Google in Munich and am now working as a Software Engineer at ETH Zürich.
• I ranked top-1 Codeforces contributor at some point in time.
• I'm an organiser of the Osijek competitive programming camp, and a maintainer of CP-Algorithms.
• I've never participated in IOI or ICPC WF.
• I'm currently 28 years old.

I'm looking forward to the interview and hope that you will enjoy it as well :)

Hi everyone!

We organized an onsite competitive programming contest at ETH Zürich on May 11th, 2024. The contest is now uploaded to the Codeforces gym at ETH Zurich Competitive Programming Contest Spring 2024.

The onsite contest was 5h long and we recommend for you to participate in teams. In the onsite contest only one computer was allowed but participants could access the internet freely. The difficulty of the problemset is slightly easier than a regional ICPC contest but also offers a few hard problems. Difficulty range is from div2 A to div2 G.

Thanks a lot to all problem setters: BenniKartefla, Lakii, Lebossle, MihneaDAVID, OhLee, TecTrixer, ackj, adamant, alagorithmet and mango_lassi.

Additionally, a big thanks to all our testers and reviewers: Petr, Evirir, CSQ31, atakanysr, FatihSolak, qwexd, AhmetKaan, Macdu, atli164, SATSKY_2024target_IGM, SuprDewd, Tagl, Tobo, wildfire032, fried-chicken, theodor.moroianu and sischu74.

Tutorial Slides can be found here.

Congratulations to the top 5 of the onsite contest:

1. mETHroners: GRT_2018, Meloric, paula
2. Mr Malnars Lethal Peppers: pavkal5, DBradac, dpaleka
3. uhh this should actually be first place, sorry, system error: AimShootReload, donentseto
4. ML and AC: miguell, Andrei1998
5. CrispyBeef: tiagodias, jonathanplsmith, Blackphoenyx

Hi everyone!

Some time ago I started developing a linear algebra library for Library Checker, and it turned out to be much fun. I'd like to write this blog to outline how one can implement a linalg library with a very good Library Checker performance, while also avoiding highly technical low-level details that are common in other similar blogs. Instead, we will learn a few high level ideas that will let us write a code that the compiler will then optimize using all these fancy techniques in our stead.

Huge thanks to ToxicPie9 and magnus.hegdahl for explaining me some of the optimizations used here! You may also look into sslotin's entry about how it can be sped up even further with more advanced and low-level techniques.

Tl'dr.

In this blog, I present my matrix library, which maintains a simple and elegant implementation of basic matrix operations without advanced techniques, while also having a remarkable performance on most Library Checker linear algebraic tasks:

• $$$1024\times 1024$$$ matrix product: 400ms, roughly top-15% of Library Checker submissions.
• $$$200\times 200$$$ matrix pow: 27ms with Frobenius form, top-1 performance. 200ms with binary exponentiation, top-10 performance.
• $$$500 \times 500$$$ determinant: 29ms, top-2 performance.
• $$$nm \leq 2.5 \cdot 10^5$$$ rank of matrix: 38ms, top-1 performance.
• $$$500 \times 500$$$ system of linear equations: 39ms, top-1 performance.
• $$$500 \times 500$$$ inverse matrix: 84ms, top-2 performance (current top-1 is the same code + fast IO).
• $$$500 \times 500$$$ characteristic polynomial: 93ms, top-1 performance.

Unlike most implementations, I do not manually optimize each of these tasks separately, but rather use a uniform optimized approach to implementing them via simple array operations, and only the later ones are somewhat optimized (with a very simple high-level approach). This also allows to avoid a significant code bloat into unreadable mess, which is common for regular Library Checker's superfast solutions.

Note: All the implementations above are focused on integer arithmetics module a prime number known at compilation time. Results of operations when the underlying type does not form a field (e.g. pure integers, composite mod, etc) may be unexpected, and will most likely be so if any division is expected.

While the library theoretically also supports floating point underlying data types (as in, compiles when they're plugged in), this functional is completely experimental, untested and may easily behave in an unexpected manner.

Hi everyone!

Sponsored by

Yesterday marked the conclusion of the third Osijek camp (also see the announcement on Codeforces). Similar to the last time, the camp was organized by Tähvend Uustalu (-is-this-fft-) and me (adamant) with an immense help from Josipa Sabljo and university staff who helped us organize onsite events and handle accounting for the camp.

The camp consisted of 7 contests, and 2 days off during which onsite participants had an opportunity to attend a paintball session and local escape rooms. Overall, 71 teams solved at least one problem, and 19 of them attended the camp onsite in Osijek, which marks an increase by 50% compared to the last year (13 teams). We're really happy to see the camp grow and attract more teams!

Me, my wife Ksenia and Radewoosh flying from Osijek to Zagreb on a completely empty plane

Onsite participants having fun at a local escape room

During contests and at the closing dinner in Hotel Osijek

As promised in the announcement, we will maintain a silence period until ICPC World Finals 2023 this April, so none of our contest will go public until then. After the date, at least one contest will be used in the Universal Cup, and we also plan to upload at least one contest to Codeforces, so that potential participants will have an opportunity to get a feel for what they may expect at the camp.

Call for problemsetters

We're looking for problem authors for the next iteration of the camp (late Summer or early Autumn 2024)!

To express interest, write a direct message to me (adamant) or Tähvend (-is-this-fft-) here on Codeforces or wherever's the most convenient to you if you already have our other contacts (Discord, Telegram, etc). We offer a generous monetary compensation for the contests, and will also waive the participation fee for one team of your choosing (e.g. yours if you also participate in the camp).

Full ICPC style contest proposals are preferred, but feel free to reach out to us even if you only have some individual problems, and we may try to find other potential authors to collaborate with you on a joint contest.

Feedback request

Did you hear about Osijek camp before but chose not to participate? Was it an inconvenient timing, doubts about our contests, online judge, location, pricing or something else entirely? Whatever that is, we would really appreciate it if you could spare a minute to fill this form (anonymously if you prefer), so that we may improve and better cater to your individual needs. Thank you!

Hi everyone!

Sponsored by

After successful camps last year (winter wrap, fall wrap), we are happy to announce that Osijek camp will be returning on 17.-25. February 2024 — just in time to prepare for the World Finals in... Maybe this spring? As well as several regional contests throughout the fall. The camp is hosted by the School of Applied Mathematics and Computer Science of the University of Osijek and is brought to you by the organizing team of adamant and -is-this-fft-.

The camp is inspired by various competitive programming camps that we attended during our active years in ICPC, and is aimed to help college students prepare for ICPC regional contests and finals. The camp will consist of 7 ICPC-style contests and 2 days off.

If you want to get a feel of the contests, two contests from the last edition will be featured in Universal Cup contests soon:

1. Estonia contest, scheduled on 2024.01.20.
2. Delft contest, scheduled on 2024.02.03.

After Universal Cup rounds, the contests will also be uploaded to Codeforces gym.

Details

Participation fee for onsite participants is 150€ per person. It does not include regular meals, travel or accommodation. Some further details about location, travel and food options can be found on the website.

If you want to participate, but are unable to come onsite, we offer a reduced fee of 100€ per person for online participation. It is also possible to reduce fees individually if you are unable to attend some of the contests. This will be handled on a case-by-case basis.

We support and empathize with those affected by the ongoing war in Ukraine, therefore we offer a 100€ discount for affected individuals and teams affiliated with Ukrainian institutions. In other words, the fees would be 50€ and 0€ per person for onsite and online participation correspondingly.

The expected starting time for the contests is 10am CET. For online participants, it is still a preferred starting time, but we will make accommodations for other starting times.

Most of our contests are fresh and developed for this camp. A small number of contests may be based on previous contests that have not been released to the general public. If you have seen some problems of a contest before, you can't participate on that day (and your participation fee will be reduced accordingly). We will privately contact participants who might be affected. Based on feedback, we will have a silence period until the end of World Finals 2023, during which camp materials will not be released to the public. Therefore, we ask participants to not discuss the problems in public until that date.

Participants

If you are interested in participating, please fill the form here.

We ask you to register before February 9 if you want to participate online and before February 3 if you want to participate onsite.

Also, if your university or organization has a lively ICPC community that may be interested in attending the camp, and you have some contacts of people in charge (e.g. coaches) we would highly appreciate if you could fill the form here, so that we can send an invitation. Thanks!

Problemsetters

We'd like to thank and praise the authors of the contests in the camp:

• qwerty787788 — ICPC 2015 World Champion, Google HashCode 2019 and 2020 winner, CodeChef SnackDown 2016 and 2019 winner.
• antontrygubO_o — author of 1188B - Count Pairs.
• jeroenodb — Codeforces International Grandmaster, Computational geometry enjoyer. NWERC 2023 silver medalist.
• 998kover — IOI gold medalist, problemsetter for IZhO and data structure enjoyer.
• TheScrasse — Codeforces International Grandmaster, SWERC 2023 silver medalist, Codeforces coordinator.
• KLPP — Codeforces International Grandmaster, SWERC 2023 silver medalist, IOI silver medalist.
• Lebossle — Codeforces Grandmaster, problemsetter for ICPC Latin America 2021+.
• adamant — Codeforces Grandmaster, maintainer of cp-algorithms.com, Osijek camp organizer, author of over 60 competitive programming problems.
• gen — ICPC 2012 and 2014 world finalist, Google Hashcode 2017 finalist, coauthor of 7 Codeforces contests.
• de_sousa — SWERC 2023 silver medalist.
• flamestorm — MIT student, author of over 50 competitive programming problems.

... And others. We would also like to thank Um_nik and errorgorn for their help with reviewing problem proposals.

You can find more details about contest rules and technical setup on the website.

Sponsors

Last but not least, we would like to say special thanks to our sponsors, who make the camp possible. If you are interested in sponsoring next editions of the camp or have any questions, please feel free to reach out at ocpc (at) mathos (dot) hr.

We would also like to thank Codeforces for guidance and promoting this announcement to the main page, eolymp for providing us an online judge for the contests and the School of Applied Mathematics and Computer Science of the University of Osijek for all their organizational support and providing us a physical location to conduct the camp.

Finally, we kindly thank ICPC foundation for their help and support.

Hi everyone!

Today, ETH Zürich, EPFL and the University of Lugano selected their teams for SWERC using the individual contest prepared by BenniKartefla, Lebossle, MihneaDAVID, OhLee, SnowfuryGiant, adamant, alagorithmet, ghassan, johannesk, majk, monika.

Special thanks to Suika_predator, fallleaves01, Sugar_fan, Okrut, AsiBasi, atli164 and Tagl for testing it!

The contest is now uploaded to the Codeforces gym at 2023-2024 ICPC, Swiss Subregional.

Congratulations to the newly formed ICPC teams! Contest tutorial:

Hi everyone!

Mandatory orz to Elegia whose blog introduced me to MMT as an elegant approach to prove Dixon's identity.

Today, I would like to write about MacMahon's master theorem (MMT). It is a nice result on the intersection of combinatorics and linear algebra that provides an easy proof to some particularly obscure combinatorial identities, such as the Dixon's identity:

Besides that, MMT has large implications in Quantum Physics, which we will hopefully discuss. For now, let's formulate MMT.

MMT. Let $$$\mathbf A = [a_{ij}]_{n\times n}$$$, $$$\mathbf X = \operatorname{diag}(x_1,\dots,x_n)$$$, $$$\mathbf t = (t_1,\dots,t_n)$$$, $$$\mathbf x = (x_1,\dots,x_n)$$$ and $$$\mathbf k = (k_1,\dots,k_n) \geq 0$$$. Then,

where $$$\mathbf t^\mathbf k$$$ stands for $$$t_1^{k_1} \dots t_n^{k_n}$$$, and $$$\mathbf x^\mathbf k$$$, correspondingly, for $$$x_1^{k_1} \dots x_n^{k_n}$$$, and $$$\mathbf I = [\delta_{ij}]_{n\times n}$$$ is the identity matrix.

Hi everyone!

Supported by

The Osijek competitive programming camp (also see the announcement on Codeforces) concluded on September 24, and I'd like to write this blog post as a wrap to this fall's iteration of the camp. Overall, 62 teams joined the camp, and 9 of them attended the camp onsite in Osijek. Tähvend (-is-this-fft-) and I (adamant), as organizers, were also there! And we would like to say a big thanks to ajovanov who immensely helped us with the organisation onsite.

Compared to previous camp, we grew in supporters a bit, as this time we were also supported by Wolfram Research, who offered all camp participants free 6 months of Wolfram|One Personal Edition and Wolfram|Alpha Pro, and by Art of Problem Solving who supported us by a few AoPS 25$ coupons, which we presented to the best onsite team.

On top of that, similar to the winter edition of the camp, each onsite participant was provided by 2 t-shirts, one from the camp itself and another from our sponsor, Jane Street.

More importantly, we have established contact with ICPC global, and for this installment of the camp, we were also sponsored by ICPC foundation. We are very happy about this opportunity to develop a stronger tie with official ICPC, and we are looking forward to the products of this collaboration in the future.

The camp consisted of 7 contests, and 2 days off. On the first day off, the onsite participants had an opportunity to go to laser tag, and on the second day off, to visit an escape room and a local zoo. As for the contests, you may check the combined scoreboard for further information. Congratulations to the top teams!

As promised in the announcement, we will maintain a silence period until the end of November, so none of our contest will go public until then. After the date, at least one contest will be used in the universal cup, and we also plan to upload at least one other contest to Codeforces, so that potential participants of the camp can have a demo of our contest quality and difficulty levels.

Yet again, I'm very happy that the idea of the camp works out, and as such I want to make an announcement:

Hi everyone!

Recently, my interactions with Codeforces met certain milestones. Here they are:

My total blog count passed over 100:

I reached the rated contribution top:

I'm red again for the first time since 2021:

To celebrate these 3 happy occasions, I want to make an AMA session. There were some AMA from people that are generally much more popular than I am (see here, here and here), and I am mentally preparing to see that nobody comes to the party, but who knows? :)

So... Let's go. Ask me anything you want in the comments.

Hi everyone!

if you read about Dinic algorithm on CP-Algorithms, especially the section about how it works on unit networks, you'll notice that its supposed runtime for bipartite matching is $$$O(E \sqrt V)$$$, where $$$E$$$ is the total number of edges, and $$$V$$$ is the total number of vertices of a bipartite graph. Let's try it out on the following problem:

Library Checker — matching on Bipartite Graph. Given a bipartite graph with $$$V, E \leq 2 \cdot 10^5$$$, find the maximum matching.

The implementation of the Dinitz algorithm that I typically use looks as follows:

struct unit_network {
    int n;
    vector<int> to, cap;
    vector<vector<int>> g;
    
    unit_network(int n): n(n), g(n) {}
    
    void add_edge(int a, int b, int cp) {
        g[a].push_back(size(to));
        to.push_back(b);
        cap.push_back(cp);
    }
    
    void add(int a, int b) {
        add_edge(a, b, 1);
        add_edge(b, a, 0);
    }

    vector<int> dist;
    bool build_layers() {
        dist.assign(n, n);
        dist[0] = 0;
        deque<int> que = {0};
        while(!empty(que)) {
            int v = que.front();
            que.pop_front();
            for(auto i: g[v]) {
                if(cap[i] && dist[v] + 1 < dist[to[i]]) {
                    dist[to[i]] = dist[v] + 1;
                    que.push_back(to[i]);
                }
            }
        }
        return dist[1] != n;
    }

    vector<size_t> ptr;
    bool push(int v = 0) {
        if(v == 1) {
            return true;
        }
        for(auto &i = ptr[v]; i < size(g[v]); i++) {
            int e = g[v][i];
            if(cap[e] && dist[v] + 1 == dist[to[e]]) {
                if(push(to[e])) {
                    cap[e] -= 1;
                    cap[e ^ 1] += 1;
                    return true;
                }
            }
        }
        return false;
    }
    
    void dinic() {
        while(build_layers()) {
            ptr.assign(n, 0);
            while(push());
        }
    }
};

Now, if we make a submission with this implementation, we get... Time Limit Exceeded?! Okay, that's weird. Apparently, roughly the fastest practical algorithm for maximum bipartite matching is so-called Hopcroft-Karp algorithm. Maybe it has a better complexity? Nope, Wikipedia page says it's $$$O(E \sqrt V)$$$. Maybe it's somehow fundamentally different from Dinitz? No, not really — Wikipedia page explicitly states that it is essentially a special case of Dinitz algorithm. So... What gives such bad performance?

Of course, there can simply be a bug in my Dinitz algorithm implementation, but after some checks, it seems that it's not the case. On particular failing test-case, we can see that the algorithm really just executes around $$$200$$$ iterations of traversing the whole flow network of roughly $$$8 \cdot 10^5$$$ edges. So, it seems that the core reason is just the enormous constant-time overhead.

So... If Hopcroft-Karp is just the special case of Dinitz algorithm, applied to bipartite graphs, how do we make it 50x faster?

Hi everyone!

Two problems were recently added to Library Checker:

• Multipoint Evaluation (Geometric Sequence). Given $$$f(x)$$$, find $$$f(ar^i)$$$ for the given $$$a, r$$$ and $$$0 \leq i < m$$$.
• Polynomial Interpolation (Geometric Sequence). Given $$$f(ar^i) = y_i$$$ for $$$0 \leq i \leq n$$$, find $$$f(x)$$$ of degree $$$n$$$.

Note: We can divide or multiply the $$$k$$$-th coefficient of initial/resulting polynomial by $$$a^k$$$, so we may assume $$$a=1$$$.

Today we'll learn how to solve both of them in $$$O(n \log n)$$$.

Hi everyone!

In combinatorics, you often need to compute Stirling numbers for various reason. Stirling numbers of the first kind count the number of permutations of $$$n$$$ elements with $$$k$$$ disjoint cycles, while Stirling numbers of the second kind count the number of ways to partition a set of $$$n$$$ elements into $$$k$$$ nonempty subsets. Besides that, they're often arise when you need to change between powers of $$$x$$$ and rising/falling factorials. There are three problems on Library Checker that go as follows:

Library Checker — Stirling Number of the First Kind. Given $$$N$$$, find $$$s(N, k)$$$ for $$$0 \leq k \leq N$$$.

Library Checker — Stirling Number of the Second Kind. Given $$$N$$$, find $$$S(N, k)$$$ for $$$0 \leq k \leq N$$$.

Library Checker — Stirling Number of the First Kind (Fixed K). Given $$$N$$$ and $$$K$$$, find $$$s(n, K)$$$ for $$$K \leq n \leq N$$$.

Here $$$s(n, k)$$$ are Stirling numbers of the first kind, and $$$S(n, k)$$$ are Stirling numbers of the second kind. Let's solve them!

Hi everyone!

Recently I've published a blog about how one can multiply and divide sequences with Dirichlet convolution. In this blog, we will learn about a convenient framework to reason about them in a "coordinate-free" notation, similar to how generating functions are used to analyze sequences under the regular convolution.

• Part 1: Fast prefix sum computation
• Part 2: Dirichlet series and prime counting

We will learn how to deal with Dirichlet multiplication and division in the framework of Dirichlet series, and derive a number of well known number theoretic results from this perspective. While doing so, we will learn about Riemann zeta function and will have a glimpse into why it is so important in analyzing behavior of prime numbers.

We will also learn how Dirichlet series framework helps us to, given $$$g(1), \dots, g(n)$$$, to compute $$$f(1), \dots, f(n)$$$ in $$$O(n \log n)$$$ such that $$$g(n)$$$ is the Dirichlet product of $$$f(n)$$$ with itself, repeated $$$k$$$ times. Besides that, we will learn how to count prime numbers below $$$n$$$ in $$$O(n^{2/3})$$$ using logarithms on Dirichlet series.

Hi everyone!

Suppose that you need to compute some sum of a number-theoretic function that has something to do with divisors:

As it turns out, such and many similar sums can be computed with Dirichlet convolution in $$$O(n^{2/3})$$$, and in this article we will learn how.

Let $$$f(n)$$$ and $$$g(n)$$$ be two arithmetic functions. Let $$$F(n)$$$ and $$$G(n)$$$ be their prefix sums, that is

We need to compute a prefix sum of the Dirichlet convolution $$$(f * g)(n)$$$. In this article, we will consider some general methods, and show how to do so in $$$O(n^{2/3})$$$ if we can compute prefix sums of $$$F(n)$$$ and $$$G(n)$$$ in all possible values of $$$\lfloor n/k \rfloor$$$ in this complexity.

• Part 1: Fast prefix sum computation
• Part 2: Dirichlet series and prime counting

ecnerwala previously mentioned that it is possible, but did not go into much detail. There is also a blog by Nisiyama_Suzune, which covers prefix sums of Dirichlet inverses in $$$O(n^{2/3})$$$.

Hi everyone!

Today I would like to write about some identities that might come handy when using generating functions to solve competitive programming problems. I will also try to include some useful examples about them.

Some notation

For brevity, we will sometimes skip the specific bounds in indexed sums, meaning that the summation happens among all valid indices. Please also read the information below if you're not familiar with generating functions, or want to brush up on some aspects.

Hi everyone!

Some time ago the following "simple math problem" was shared in a Discord chat:

As a lover of simple math problems, I couldn't just pass by this problem. It turned out much harder than any other genfunc problem that I solved before, as the structure of the answer depends on the parity of $$$n$$$ and $$$m$$$, and it's not very natural to track it through genfuncs. It took me few months, I even called for help from higher powers (i.e. sent a pm to Elegia) but I finally have a solution that I somewhat like.

Hi everyone!

There is an article on cp-algorithms about how to compute $$$n!$$$ modulo prime number $$$p$$$. Today I was wondering, how to do it if we need to compute modulo $$$p^k$$$ rather than just $$$p$$$. Turns out one can do it efficiently if $$$p$$$ is small.

Motivational example

Xiaoxu Guo Contest 3 — Binomial Coefficient. Given $$$1 \leq n,k \leq 10^{18}$$$, find $$$\binom{n}{k}$$$ modulo $$$2^{32}$$$.

There are also some projecteuler problems that require it, including with several queries of distinct $$$n$$$ and $$$k$$$.

Task formulation and outline of result

To clarify the task a bit, our ultimate goal here is to be able to compute e.g. binomial coefficients modulo $$$p^k$$$. Thus, what we really need is to represent $$$n! = p^t a$$$, where $$$\gcd(a, p)=1$$$, and then report $$$t$$$ and $$$a$$$ modulo $$$p^k$$$. This is sufficient to also compute $$$\binom{n}{r}$$$ modulo $$$p^k$$$.

We will show that, assuming that polynomial multiplication of size $$$n$$$ requires $$$O(n \log n)$$$ operations, and assuming that arithmetic operations modulo $$$p^k$$$ take $$$O(1)$$$, we can find $$$t$$$ and $$$a$$$ in $$$O(d^2 + dk\log k)$$$, where $$$d=\log_p n$$$. It requires $$$O(pk\log^2 k)$$$ pre-computation that takes $$$O(pk \log k)$$$ memory.

Hi everyone!

As I continue working through Project Euler, I want to write a blog about another piece of general mathematical knowledge that is both interesting on its own and might be useful in some problems. Consider the following Diophantine equation:

We assume that we're given a specific number $$$z \in \mathbb Z$$$, and we need to check if there are $$$x, y \in \mathbb Z$$$ for which the identity above holds. Then, if such numbers exist we should find them and report. Example of a problem that might need it:

Timus — 1593. Square Country. Version 2. You're given an integer $$$n$$$. Find minimum $$$k$$$ such that $$$n = a_1^2+\dots+a_k^2$$$.

Tl;dr.

Let $$$z = 2^{k_0} p_1^{k_1} \dots p_n^{k_n} p_{n+1}^{k_{n+1}} \dots p_m^{k_m}$$$, where $$$p_1, \dots, p_n$$$ are different prime numbers with remainder $$$3$$$ modulo $$$4$$$, and $$$p_{n+1}, \dots, p_m$$$ are different prime numbers with remainder $$$1$$$ modulo $$$4$$$. Then there are two cases. If any of $$$k_{1}, \dots, k_n$$$ is odd, there are no solutions. Otherwise there is always a solution $$$z = x^2 + y^2$$$ that looks like

where $$$i^2=-1$$$ and $$$x_k^2+y_k^2 = p_k^2$$$ for $$$k$$$ from $$$n+1$$$ to $$$m$$$. For each $$$p_k$$$, to find such $$$x_k, y_k$$$ we need to find an integer $$$i$$$ such that $$$i^2 \equiv -1 \pmod{p}$$$, then find a minimum $$$x_k = i y_k \bmod p_k$$$ for $$$1 \leq y_k < \sqrt {p_k}$$$. This is doable in $$$O(\log p_k)$$$.

And if we want to count solutions, their number is given by Jakobi's two-square theorem: The number of ways of representing $$$z$$$ as the sum of two squares is $$$4(d_1(z) - d_3(z))$$$, where $$$d_k(z)$$$ is the number of divisors of $$$z$$$ that have remainder $$$k$$$ modulo $$$4$$$.

Hi everyone!

Recently I started solving projecteuler, and while doing so I encountered two concepts about which I heard before, but I didn't really bother to learn them. I made a few notes to myself about how they work, and thought it could be useful for somebody else too. This blog focuses on Pythagorean triples and Pell's equations, which are recurrent concepts on projecteuler.

Great thanks to nor, Endagorion, Golovanov399 and Neodym for useful discussions about these topics.

Hi everyone!

Previously, I had a blog on how, given $$$s$$$ and a polynomial $$$f(x)$$$, to compute coefficients of the polynomial $$$f(x+s)$$$.

Today we do it in values space. Consider the problem Library Judge — Shift of Sampling Points of Polynomial. In this problem, you're given $$$s$$$ and the values $$$f(0), f(1), \dots, f(n)$$$ of a polynomial of degree at most $$$n$$$ and you need to find $$$f(s), f(s+1), \dots, f(s+n)$$$.

In particular, I used this to generate test cases for 1817C - Similar Polynomials, there might be other applications too.