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.

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 Apr/29/2023 17:35 (Moscow time). 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, c_plus_plus, amiya, willy108, madlogic, LeticiaFCS, tanus_era, nigus, Plurm, mathdude42, SajidZakaria, ace-in-the-hole, 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. fantasy
5. QAQAutoMaton

Div. 2:

1. RGB_ICPC4
2. zhukovaliza
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.com/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: