Hi everyone!

Today we will talk about something that might be useful in programming competitions. Yay! Also great thanks to antontrygubO_o for sharing this with me and others in a Discord server.

Let's implement a data structure that maintains a big number $$$N$$$ in base $$$b$$$ and supports the following:

• Given (possibly negative) integers $$$|x|, |y| \leq n$$$, add $$$x b^y$$$ to $$$N$$$.
• Given $$$k$$$ and assuming $$$N \geq 0$$$, print the $$$k$$$-th digit of $$$N$$$.
• Check if $$$N$$$ is positive, negative or equals to $$$0$$$.

Each operation should take at most $$$O(\log n)$$$ amortized time and $$$O(q)$$$ memory. While some approach you may think of immediately would imply using segment tree, or a similar structure, the solution proposed here only requires std::map, so it's much shorter and easier to implement (at the slight expense of increased constant factor). It may be used in the following problems:

• #2302. 「NOI2017」整数
• 1817E - Half-sum
• 1810F - M-tree

If you implement the big integers in these numbers the standard way (i.e. keeping digits in the $$$[0, b)$$$ segment, carefully executing carries, etc), you will quickly learn that you may get in trouble because you may be forced to do and undo a lot of carry operations which chain up and so you need to frequently change large segments between the values of $$$0$$$ and $$$b-1$$$.

Now, stop being fooled by the non-negative propaganda! You don't have to do it! Let's give ourselves some slack and allow negative digits. Well, just a bit of them. Instead of maintaining digits in $$$[0,b)$$$, let's now maintain them in the interval $$$(-b, b)$$$. It seems like a tiny change, but the effect is tremendous. On one hand, the representation of any number is not unique anymore. On the other hand, when we actually reach the value $$$b$$$ or $$$-b$$$, we wrap them back to $$$0$$$, and carry $$$1$$$ or $$$-1$$$ to the next digit correspondingly.

Noticed anything? The carry now wraps us from the endpoints of the interval to its middle instead of from one endpoint to another! It would be easy to add $$$1$$$ to a particular bit, turn it into $$$b$$$ and cause a chain of carries by it. But! If after that we add $$$-1$$$ to the same bit, it will not wrap all the bits back to $$$b-1$$$! It will just change this specific bit to $$$-1$$$! So, we give up the uniqueness of the representation, but we gain a whole lot of stability in exchange.

The C++ implementation for the first two queries is also quite concise:

struct trygub_num {
    const int base = 1 << 30;

    map<int, int> digs;

    void add(int a, int b) {
        digs[b] += a;
        int t;
        do {
            t = digs[b] / base;
            digs[b + 1] += t;
            digs[b] -= t * base;
            if(digs[b] == 0) {
                digs.erase(b);
            }
            b++;
        } while(t);
        if(digs[b] == 0) {
            digs.erase(b);
        }
    }

    int get(int k) {
        auto it = digs.lower_bound(k);
        int ans = it == end(digs) || it->first > k ? 0 : it->second;
        if(it != begin(digs) && prev(it)->second < 0) {
            ans--;
        }
        return (ans + base) % base;
    }
} me;

I tested it on #2302. 「NOI2017」整数 and it works!

P.S. Applying it to 1817E - Half-sum and 1810F - M-tree is left to the curious reader as an exercise :)

P.P.S. Is this trick well-known? Does it have a name?

Hi everyone!

In this blog, I would like to present a somewhat novel concept in competitive programming, which is, while being relatively simple, allows us to enumerate directed graphs with specific type of strongly connected components. This allows us to easily and uniformly compute generating functions e.g. for acyclic digraphs or strongly connected digraphs. The formalism introduced here is also very intuitive at that.

I initially wanted to make a problem based on the content of this blog to appear in today's round, but after some discussions we decided to exclude it, as the contest already had a sufficient amount of difficult problems. You may try the original problem [problem:441297A] via the invitation link.

Prerequisites

You are expected to be familiar with exponential generating functions, and the exponential formula for connected structures, that is, that if $$$A(x)$$$ is the EGF for combinatorial structures $$$A$$$, then $$$\exp A(x)$$$ is the EGF corresponding to sets of isolated instances of $$$A$$$.

Hi everyone!

It's been a while since I set problems for Codeforces competitions, so I hope that you had sufficient opportunity to rest before dealing with my problems again. Oh, no-no, there's nothing to worry about! Probably! I promise!

jeroenodb and adamant (that's me!) are happy to invite you to Codeforces Round 869 (Div. 1) and Codeforces Round 869 (Div. 2) which are going to take place at 29.04.2023 17:35 (Московское время). Participants with a rating strictly lower than 1900 will participate in Division 2, while participants with a rating of at least 1900 will participate in Division 1.

All the problems are prepared by us, and we would like to thank:

• dario2994 for rejecting sufficient amount of problems for me to be able to set Oleksandr Kulkov Contest 3, for thorough and dedicated coordination and for suggesting one of the problem ideas for the round.
• izban, gamegame, tfg, fedimser, Endagorion, nor, rivalq, errorgorn, antontrygubO_o, redpanda, Runtime-Terr0r, izhang, Everule, NemanjaSo2005, ak2006, ayhan23, SlavicG, hashman, jqdai0815, willy108, madlogic, LeticiaFCS, tanus_era, nigus, Plurm, mathdude42, SajidZakaria, ace_loves_xq, InternetPerson10, alwyn, -is-this-fft-, DJeniUp and dorijanlendvaj for testing and/or valuable feedback and insights about the problems.
• MikeMirzayanov for Codeforces and Polygon and KAN for all his effort in coordinating coordinators :)

In both divisions, you will have 2 hours and 15 minutes to solve 6 problems.

Score distribution in both divisions: 500 — 1000 — 1250 — 2000 — 2500 — 3000.

Good luck and have fun!

The editorial is out.

Congratulations to the winners!

Div. 1:

1. A_G
2. tourist
3. ecnerwala
4. Rewinding
5. QAQAutoMaton

Div. 2:

1. RGB_ICPC4
2. elizazh
3. lintd
4. -LAP-
5. STOC

Hi everyone!

As it is widely known, Zermelo–Fraenkel set theory with the axiom of choice, also widely known as ZFC, has several fatal flaws:

• Nobody remembers the axioms accurately;
• in ZFC, it is always valid to ask of a set ‘what are the elements of its elements?’, and in ordinary mathematical practice, it is not.

From now on, please use the Lawvere's Elementary Theory of the Category of Sets instead of ZFC:

Only by switching to a superior set of set theory axioms we can save mathematics. Thank you for your attention.

P.S. On a more serious note, I think that their approach is quite interesting and it is useful to revisit the fundamentals once in a while. Overall, as highlighted in An Infinitely Large Napkin, we understand things much better when we think about them as "sets and structure-preserving maps between them" rather than just "sets and their elements", as suggested by ZFC.

Hi everyone!

Consider the following problem. You're given two arrays $$$a_1, a_2, \dots, a_{n!}$$$ and $$$b_1, b_2, \dots, b_{n!}$$$.

You need to compute the array $$$c_1, c_2, \dots, c_{n!}$$$, such that

where $$$i \circ j$$$ denotes the composition of the $$$i$$$-th and the $$$j$$$-th lexicographically smallest permutations of $$$n$$$ elements.

Generally, typical approach to such things would be to escape into space in which the convolution corresponds to the component-wise product of two vectors, and then to transform back into initial space. For example, with the summation rule being $$$i + j \equiv k \pmod n$$$, it is well known that the corresponding transform is exactly the discrete Fourier transform of vectors $$$a_i$$$ and $$$b_j$$$.

But with more generic groups, things may be much more complicated. This is the second blog in a series of blog posts explaining it.

• Fourier transform on groups. Part 1: Irreducible representations
• Fourier transform on groups. Part 2: Characters

Great thanks to Endagorion and Golovanov399 for helping to understand the theory for this part!

In this blog, we will learn the basics of character theory which will allow us to define the inverse Fourier transform on finite groups.

Prerequisites

Difficulty: ★★★★★

One is expected to have some reasonable intuition with group theory and be well-familiar with linear algebra, and be familiar with some tangent definitions (e.g. what is a ring, what is a field, what is a linear span, what is a vector space, dot product, hermite product etc). Familiarity with discrete Fourier transform, and similar transforms used to compute convolutions is also essential.

Hi everyone!

I saw that a lot of people write meta blogs recently. As my blog count approaches 90, I feel like it may make a lot of sense to write another one that kind of focuses on the philosophy behind my blogs and explains potential readers what they should expect from my blogs and how to approach them. So, without further ado...

Tldr.

1. Read my blogs if and only if the general setup itself appeals to you. Don't feel obliged to do it to get better at competitive programming.
2. Don't be driven away by seemingly dense math notation if the topic looks interesting. Ask questions if something is difficult to comprehend, I will explain in a more detail and it will help others too.
3. Be ready to fill some possible gaps in the story yourself, as an exercise.
4. Be open-minded about analyzing setup in general, rather than working towards predetermined goal.
5. Be prepared to see too little explanation on how abstract nonsense from my blogs connects with concrete applications.
6. Give feedback, it motivates me a lot and helps make future blogs better.

Hi everyone!

Consider the following problem. You're given two arrays $$$a_1, a_2, \dots, a_{n!}$$$ and $$$b_1, b_2, \dots, b_{n!}$$$.

You need to compute the array $$$c_1, c_2, \dots, c_{n!}$$$, such that

where $$$i \circ j$$$ denotes the composition of the $$$i$$$-th and the $$$j$$$-th lexicographically smallest permutations of $$$n$$$ elements.

Generally, typical approach to such things would be to escape into space in which the convolution corresponds to the component-wise product of two vectors, and then to transform back into initial space. For example, with the summation rule being $$$i + j \equiv k \pmod n$$$, it is well known that the corresponding transform is exactly the discrete Fourier transform of vectors $$$a_i$$$ and $$$b_j$$$.

But with more generic groups, things may be much more complicated, and I will write a series of blog posts explaining it.

• Fourier transform on groups. Part 1: Irreducible representations
• Fourier transform on groups. Part 2: Characters

Prerequisites

Difficulty: ★★★★★

One is expected to have some reasonable intuition with group theory and be well-familiar with linear algebra, and be familiar with some tangent definitions (e.g. what is a ring, what is a field, what is a linear span, what is a vector space, dot product, hermite product etc). Familiarity with discrete Fourier transform, and similar transforms used to compute convolutions is also essential.

Hi everyone!

This blog is inspired by some contestant solutions to 104234F - Palindromic Polynomial. In short, problem asks you to find a polynomial such that $$$A(x_i) = y_i$$$ for several given pairs $$$(x_i, y_i)$$$, and the coefficients of $$$A(x)$$$ read the same left-to-right and right-to-left (i.e., they form a palindrome). The intended solution utilizes the fact that for such polynomial, it always holds that

as $$$x^n A(x^{-1})$$$ is exactly the polynomial $$$A(x)$$$ with reversed coefficients (assuming the degree is $$$n$$$).

Representing palindromic polynomials with polynomials in $$$x+\frac{1}{x}$$$

Several solutions from contestants, however, relied on a different criterion for $$$A(x)$$$. Rather than using the identity above, participants found out that palindromic polynomials can always be represented as

when its degree $$$2d$$$ is even, or as

when its degree $$$2d+1$$$ is odd. In both cases, $$$B(x)$$$ is a polynomial of degree $$$d$$$. This representation allows for much simpler solution, but in this blog we will talk about why it exists in the first place, rather than how to use it to solve the problem.

Thanks to ecnerwala for explaining me this approach in more detail!

Hi everyone!

As the Universal Cup stage 7 which mirrored my contest from the Osijek Competitive Programming Camp 2023 just concluded, I decided to also upload the contest to gym as OCPC 2023, Oleksandr Kulkov Contest 3, and post the tutorial here. I hope you enjoyed the contest!

My previous ICPC-style contests:

• Oleksandr Kulkov Contest 1 in gym
• Oleksandr Kulkov Contest 2 in gym

Compiled PDF Tutorial for all problems: link.

To make it worth a separate blog post, I will also add some brief meta comments :)

P.S. Congratulations to the team USA1 (ecnerwala, ksun48, scott_wu) for solving all the problems in-contest!

Hello everyone! The 7th Stage of the 1st Universal Cup: Zaporizhzhia, will be held on March 11th, 2023.

The contest is based on the Day 2: Oleksandr Kulkov Contest 3 from the Osijek Competitive Programming Camp 2023. Please, don't participate if you have seen these problems.

Authors of the problems: adamant, fedimser, I would also like to thank -is-this-fft- for the help with the preparation of the contest.

We hope you will like the problems!

You can participate in the contest in the following three time windows:

• Mar 11th 13:00 — 18:00 (UTC +8)
• Mar 11th 19:00 — 24:00 (UTC +8)
• Mar 12th 02:00 — 07:00 (UTC +8)

Please note that you can see two scoreboards in DOMjudge. The 'Local Scoreboard' shows the standings ONLY IN THE CURRENT TIME WINDOW. And the 'Combined Scoreboard' shows all participants, including the onsite participants, and the cup participants in the previous time windows.

Contest link: https://domjudge.qoj.ac/

Universal Cup Scoreboard: https://qoj.ac/ucup/scoreboard

About Universal Cup:

Universal Cup is a non-profit organization dedicated to providing trainings for competitive programming teams. Up to now, there are more than 200 teams from all over the world registering for Universal Cup.

A more detailed introduction: https://codeforces.me/blog/entry/111672

Register a new team: https://ucup.ac/register

Hi everyone!

Sponsored by

The Osijek competitive programming camp (also see the announcement on Codeforces) just concluded last Sunday, on February 26, and I'd like to write this blog post as a wrap to this winter's iteration of the camp. Overall, 74 teams joined the camp, and 13 of them attended the camp onsite in Osijek. Tähvend (-is-this-fft-) and I (adamant), as organizers, were also there!

The camp consisted of 7 contests, and 2 days off. On the first day off, the onsite participants had an opportunity to go to bowling, and on the second day off, to play paintball (see the photos). As for the contests, two of them were shared with the Universal Cup, so that our participants didn't have to choose what to attend between the camp contests and the UniCup. On top of that, three other contests will be used in the Universal Cup for later stages. Here is a brief contest summary:

Combined scoreboard, also ITMO rating table (thanks, awoo!). Congratulations to the top teams (by ITMO score):

• HoMaMaOvO (maroonrk, hos.lyric, maspy)
• University of Warsaw: Polish Mafia (Swistakk, Radewoosh, mnbvmar)
• Kyoto University: Heno World (heno239, yamunaku, Moririn2528)

And also to the top onsite teams (by ITMO score):

• University of Oxford: nwerc is bad (Ronnie007, gamegame, Sorting)
• University of Zagreb: Zagreb (dorijanlendvaj, keko37, ppavic)
• School No. 14 in Wrocław + School No. 8 in Warsaw: PokorFanClub (kamilszymczak1, Rafi22, surgutti)

I can't express enough how happy I am that the idea worked out, and we gathered so many cool people to participate in this! I'm very optimistic towards the idea of conducting it again sometime, and as such I wanted to make an announcement:

Hi everyone!

This is the blog for infinite sums. For finite sums of power, see here.

As everybody knows, it is true that

Moreover, it is widely known that

Historically, it seems that the result was first discovered by Ramanujan, who described it in one of his letters to G. Hardy as

In this blog, I want to explain how this summation could be easily done with the competitive programmer's favorite tool: generating functions. Moreover, I will explain how to compute the infinite sums of form $$$1^k + 2^k + 3^k + 4^k + \dots = S_k$$$ for any non-negative integer $$$k$$$.

Hi everyone!

In my previous blog, I wrote about how generating functions can be used to enumerated labeled species. In this blog, I want to continue the topic by writing about how one can account for different kinds of symmetries when counting different combinatorial structures. Ultimately, we will end up deriving and hopefully understanding the analogue of Pólya enumeration theorem in species.

Difficulty: ★★★★☆

Prerequisites:

• Familiarity with combinatorial species (see my prev. blog), OR
• Very good intuition with enumerative combinatorics, genfuncs and recap below.

I will try to use plain language rather than formulas as much as possible, as it seems to be the preferred format for readers.

Recap

Below is a very brief recap of the most important things from the previous article. I tried to keep it as informal as possible.

Previously on combinatorial species

Labeled species

The species $$$F$$$ is a rule that produces:

1. For each finite set $$$A$$$, a finite set $$$F(A)$$$ consisting of all possible structures defined by the species $$$F$$$ that can be built using the elements of $$$A$$$ as atoms;
2. For each bijection $$$\sigma : A \to B$$$, a bijection $$$F_\sigma : F(A) \to F(B)$$$ between the structures $$$F(A)$$$ and $$$F(B)$$$, that describes how structures change if we change one set of atoms for another.

When we use the term "atoms", we mean the units used to enumerate the species, such as the vertices of a graph, the pairs of brackets in a bracket sequence, etc. For example, you may see $$$F(A_2)$$$, $$$F(A_3)$$$ and $$$F(A_4)$$$ for the species of labeled trees below:

Labeled trees on sets $$$A_2 = \{{\color{red} \bullet}, {\color{blue} \bullet}\}$$$, $$$A_3 = \{{\color{red} \bullet}, {\color{blue} \bullet}, {\color{green} \bullet}\}$$$ and $$$A_4 = \{{\color{red} \bullet}, {\color{blue} \bullet}, {\color{green} \bullet}, {\color{goldenrod} \bullet}\}$$$.
The image by Júlio Reis is distributed under CC BY-SA 3.0 license.

Unlabeled structures

The theory of combinatorial species described in the previous blog post is based on an assumption that all atoms are pairwise distinguishable ("labeled"). I also very briefly mentioned the concept of unlabeled structures in the end of the previous blog post:

On the left and on the right are equivalent trees. In the middle is the representation of their unlabeled structure.

We say that two structures $$$\alpha, \beta \in F(A)$$$ are equivalent if one can be obtained from the other by re-ordering the atoms in $$$A$$$. For example, on the picture above all the trees on the bottom row are equivalent to each other, as well as all the trees on 3 rows above it.

All unlabeled ordered trees on $$$n \in \{1,2,3,4\}$$$ vertices.

An unlabeled structure is what we get by essentially erasing the "labels" from the elements of $$$F(A)$$$ and treating atoms as indistinguishable from each other. Formally, it is an equivalence class in $$$F(A)$$$ with regard to the equivalence relation defined above.

Species composition

Perhaps a single most powerful aspect of combinatorial species is the notion of species composition.

A $$$G$$$-structure is formed on each set of the atom partition, and an $$$F$$$-structure is formed on top of the partition itself.
The image by Brent Yorgey is distributed under CC BY-SA 3.0 license.

Informally, a composition of species $$$F$$$ and $$$G$$$ is a species $$$F \circ G$$$ whose combinatorial structure can be described as an $$$F$$$-structure whose atoms are substituted by instances of $$$G$$$-structures.

Function species is a set of cycles of rooted trees
An illustration from Combinatorial Species article by François Bergeron

Species composition allows us to think about one species as a combination of simpler species. Typical example of which is a species of permutations which can be interpreted as a species of sets of cycles due to cyclic presentation of permutations.

If $$$A(x)$$$ and $$$B(x)$$$ are the generating functions for species $$$A$$$ and $$$B$$$, then $$$A(B(x))$$$ is the generating function for their composition.

It is a fundamental result for labeled species. Unfortunately, there is no simple analogue with unlabeled structures, and deriving the composition formula in some reasonable formulation for them is the ultimate goal of this article.

Hi everyone!

This is yet another blog that I had drafted for quite some time, but was reluctant to publish. I decided to dig it up and complete to a more or less comprehensive state for the $300 contest.

Essentially, the blog tells how to combine CDQ technique for relaxed polynomial multiplication ("online FFT") with linearization technique from Newton method (similar approach is used in the first example of the ODE blog post by jqdai0815), so that the functions that typically require Newton's method can be computed online as well. I will try to briefly cover the general idea of "online FFT" too and provide some examples, in case you're not well familiar with it. That being said...

Hi everyone!

I had this blog drafter for quite a while, but the $300 contest motivated me to actually finish and publish it. I don't care about the prize that much as I think many other blogs published recently are talking about something even cooler. But I like to make people suffer, so I will apply anyway to make peltorator read even more stuff >:)

Besides, the contest makes it harder to stay on contribution top, so I got to do something to stay afloat. That being said...

Today I'd like to write about an algorithm that solves the following problem:

You're given a set of permutations $$$G = \{g_1, \dots, g_m\}$$$. Find the size $$$|\langle g_1, \dots, g_m \rangle|$$$ of the group generated by $$$G$$$.

At first, I wanted to get into a lot of group-theoretic details with proofs and all, but then I felt like it would make the article harder to comprehend, so I will try to keep group-theoretic stuff to minimum, while telling more about the high-level idea.

Prerequisites

It is strongly recommended to be familiar with some simpler basis constructing algorithms, e.g. Gauss elimination or XOR basis.

Familiarity with basic group theory (e.g. definitions) will also be beneficial.

Hi everyone!

I am happy to announce the Osijek Competitive Programming Camp that is scheduled to happen on 18-26 February 2023 in Osijek, Croatia. The camp is hosted by the Department of Mathematics at J. J. Strossmayer University of Osijek and is brought to you by the organizing team of adamant (that's me!), -is-this-fft-, mblazev, Tomx and antontrygubO_o.

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.

Up until now, most top competitive programming training camps have been organised in Russia, or by Russian entities. Due to the current situation in the world, attending such camps is not possible or desirable for a large number of participants, and we hope to offer a European alternative to Russian camps.

This is the first edition of the camp, and we all are very excited about it and hope that we may see you soon!

Details

Participation fee for onsite participants is 150€ per person. It does not include regular meals, travel or accommodation.

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 (e.g. because of the overlap with SWERC).

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 if it is not an option for you, we will also offer an opportunity to compete virtually within 24 hours after the main window is over.

Participants

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

We ask you to register before February 10 if you want to participate online and before February 4 if you want to participate onsite.

If you want to participate onsite, especially if you require visa support, we would urge you to register as soon as possible, as visa processing may take 30+ days.

Also, if your university 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 praise the authors of the contests for the camp:

• jqdai0815 — a guy who changed CF username every year and labeled the contest by prime numbers.
• conqueror_of_tourist — ICPC 2022 world finalist. Codeforces LGM in Python.
• antontrygubO_o — IMO 2017 gold medalist, NAC 22 winner, contest coordinator, Codeforces LGM.
• Savior-of-Cross — ICPC 2023 world finalist.
• rivalq — Codeforces grandmaster, ICPC 2021 and 2022 world finalist.
• Adam_GS — Codeforces grandmaster, EJOI 2021 gold medalist.
• ToxicPie9 — ICPC 2021 world finalist.
• adamant — a maintainer of cp-algorithms.com, author of nearly 50 competitive programming problems.

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 [email protected].

Finally, 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 Department of Mathematics at J. J. Strossmayer University of Osijek for all their organizational support and providing us a physical location to conduct the camp.

Hi everyone!

Today I saw a discussion in AC Discord server about how many problems some people made for different competitions. It was sparkled by this CF entry. I haven't keep track of this before, so it made me curious to go through everything that I made and publish in a comprehensive list. I'm doing it mostly out of curiosity, but maybe it might be interesting for someone else too :)

Hi everyone!

Today, I participate in AtCoder contest, which I quite rarely do. Of course, my performance was quite poor, but I stumbled with quite nice idea along the way. To those who didn't read it, the problem goes as follows:

AGC 058 — Yet Another ABC String. How many ternary strings are there such that they contain exactly $$$A$$$ characters a, exactly $$$B$$$ characters b and exactly $$$C$$$ characters c, and do not have any sub-string that is a cyclic shift of abc?

My approach is very different from the one in the editorial, and seems insightful to me, so I decided to share it in detail.

Besides, I can't reject the request by Um_nik to explain it further :D

Hi everyone!

Previously, I wrote a general introduction to linear programming duality. In this blog, I would like to write about several problems that could be solved with this technique. Familiarity with the first blog, or general knowledge of dual problems and how to construct them is generally expected to navigate in this one.

Thanks to brunovsky and Golovanov399 for problem suggestions!

And particularly special thanks to WeakestTopology for problem suggestions and all insightful discussions on the topic!

Hi everyone!

There is a well-known result about bipartite graphs which is formulated as follows:

In any bipartite graph, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover.

Knowing it you can easily find the size of a minimum vertex cover in a given bipartite graph. But what about actually recovering such cover? Well... There is an algorithm to it, but it's lengthy and not very motivated, so I constantly forget its details. However, there is a simple alternative, which is easily reproduced from scratch, even if you forget specific details.

Besides, there is another well-known result which is formulated as follows:

A bipartite graph has a perfect matching if and only if every subset $$$\alpha$$$ of one part has a neighborhood $$$\beta$$$ in the other part such that $$$|\beta| \geq |\alpha|$$$.

This result can be proven with a similar approach. It is likely known to those familiar with the topic, but still might be of interest to someone.

Hi everyone!

Previously I wrote about theoretical grounds of "aliens trick". Specifically, I introduced the concept of the Lagrangian duality and explained its connection with the trick. Today I want to elaborate a bit more on the concept of dual problems and their applications to linear programming as well as to common problems in competitive programming.

I initially wanted to also write about some applications in competitive programming problems, but given that the introduction is already quite lengthy, I decided to leave it for another blog, while using most common and well-known theoretical examples here, focusing more on how to construct and interpret dual problems to begin with, rather than how to use it in contests.

I think, it is a crucial first step towards using the duality in actual programming challenges.

Prerequisites

It is highly recommended to have some general understanding of basic mathematical optimization concepts (e.g. convexity, Lagrange multipliers), as well as basic understanding of flow algorithms and most well-known results around them, such as cycle-path decomposition of flows, maximum flow / minimum cut duality, minimum cost flows (ideally, the algorithm that computes it using Dijkstra with potentials). The article should hopefully shed some further light on these topics.

Hi everyone!

Here's another collection of little tricks and general ideas that might make your life better (or maybe worse).

Most of them are somewhat well-known, but perhaps would still be useful to someone.

Hi everyone!

In today's blog I'd like to write about the theorem that allows to efficiently solve the following problems:

• What is the number of partitions of a non-negative number $$$n$$$ for $$$n \leq 10^5$$$?
• What is the number of partitions of a non-negative number $$$n$$$ for $$$n \leq 10^5$$$, so that no summand repeats $$$d$$$ or more times?
• What is the number of partitions of a non-negative number $$$n$$$ for $$$n \leq 10^5$$$, so that no summand is divisible by $$$d$$$?
• HackerEarth — Perfect Permutations: What is the number of permutations of length $$$n$$$ with $$$k$$$ inversions for $$$k \leq n \leq 10^5$$$?
• 102354E - Decimal Expansion: Let $$$\phi = \frac{9}{10} \cdot \frac{99}{100} \cdot \frac{999}{1000} \cdot \dots$$$, what is the $$$k$$$-th digit of $$$\phi$$$ for $$$k \leq 10^{18}$$$?
• SNSS-2018 Round 5 — Investment Portfolio: You have $$$2n$$$ dollars and there are $$$n$$$ types of products in the market. There are $$$a_i$$$ instances of the $$$i$$$-th product, costing $$$i$$$ dollars each, such that $$$a_i > a_j$$$ when $$$i > j$$$. Besides that, there are also $$$m$$$ individual offers, $$$j$$$-th of them costing $$$b_j$$$. How many ways are there to spend all $$$2n$$$ dollars, while taking exactly one individual offer for $$$n, m \leq 10^5$$$?

The core fact that allows us to solve these problems efficiently is the pentagonal number theorem:

Prerequisites

• Familiarity with generating functions, formal power series and operations on them.
• Basic notion of combinatorics.
• Basic notion of number theory.

Hi everyone!

There is a concept that is sometimes mentioned here and there. The Lagrange inversion theorem.

Let $$$x = f(y)$$$. We want to solve this equation for $$$y$$$. In other words, we want to find a function $$$g$$$ such that $$$y = g(x)$$$.

The Lagrange inversion theorem gives an explicit formula for the coefficients of $$$g(x)$$$ as a formal power series over $$$\mathbb K$$$:

In a special case $$$y = x \phi(y)$$$, that is $$$f(y) = \frac{y}{\phi(y)}$$$, which is common in combinatorics, it can also be formulated as

Finally, to avoid division by $$$k$$$ one may use (see the comment by Elegia) the following formula:

which may be formulated for $$$y = x \phi(y)$$$ as

Prerequisites

Familiarity with the following:

It is required to have knowledge in the following:

• Polynomials, formal power series and generating functions;
• Basic notion of analytic functions (e.g. Taylor series);
• Basic concepts of graph theory (graphs, trees, etc);
• Basic concepts of set theory (describing graphs, trees, etc as sets, tuples, etc).

I mention the concept of fields, but you're not required to know them to understand the article. If you're not familiar with the notion of fields, assume that we're working in real numbers, that is, $$$\mathbb K = \mathbb R$$$.

It is recommended (but not required) to be familiar with combinatorial species, as they provide lots of intuition to how the equations on generating functions below are constructed.

Hi everyone!

The usage of generating functions is quite common in competitive programming these days. But it seems to happen so, that they're mostly presented as a way to simplify formal manipulation with polynomial coefficients, rather than something meaningful. But there actually is a meaning to all of this, and today I'm going to shed a light on it.

Alongside the blog post we'll uncover the combinatorial meaning of

• The addition $$$F(x)+G(x)$$$,
• The multiplication $$$F(x)G(x)$$$,
• The exponent $$$\exp F(x)$$$,
• The logarithm $$$\log F(x)$$$,
• The sum of the infinite geometric progression $$$\frac{1}{1-F(x)}=1+F(x)+F^2(x)+\dots$$$,
• The general composition $$$F(G(x))$$$

for the generating functions $$$F(x)$$$ and $$$G(x)$$$ and the underlying structures they represent.

Prerequisites

• Basic notion of set theory (cardinality of sets, mappings, bijections, cartesian product, disjoint union, etc);
• Polynomials and formal power series (representation, convolution formula, power series definitions of $$$\exp$$$ and $$$\log$$$);
• Elementary combinatorics (combinations, partitions, etc).

Although combinatorial species are defined with category theory concepts, I will try to avoid them for simplicity. However, knowledge of some category theory concepts would greatly simplify the reading experience.

Some of definitions use pretty dense mathematical notation, I will follow up with informal explanation right away when it is the case.

Commutative diagrams

I will also use commutative diagrams to illustrate complicated identities. You may use the explanation below as a reference.

Explanation

As a simplest example, the diagram below

A simple commutative diagram.

mentions four functions:

$$$ \begin{matrix} f : A \to B, & g : A \to C, \\ h : B \to D, & k : C \to D. \end{matrix} $$$

The composition of functions on every path between two nodes of the diagram should be the same, hence

$$$ h \circ f = k \circ g, $$$

which is equivalently written as

$$$ h(f(a)) = k(g(a)), \forall a \in A. $$$

Every diagram is also provided with a more verbose text description, so don't be afraid if the concept seems complicated.