adamant's blog

By adamant, history, 41 hour(s) ago, In English

Okay guys, I know it sounds like Top 10 optimizations 2017- (collectors edition) but hear me out

Hi everyone!

Recently, a problem ordered set has been added to Library Checker.

Essentially, the problem asks you to maintain a set $$$\{a_1,\dots,a_n\}$$$ that supports the following operations:

  1. Insert an element;
  2. Erase an element;
  3. Find the $$$k$$$-th smallest element;
  4. Find the order index of an element;
  5. Find lower bound of an element;
  6. Find pre-upper bound of an element.

Of course, all these can be done with GNU policy-based data structures (pbds) in $$$O(\log n)$$$ per query, which leads to the shortest code. At the same time, it has a huge constant factor in practice, so a natural question arises. What would be the fastest way to solve this? One of my earliest blogs already addressed this: we can use a Fenwick tree over the bitmask of the set and then do a jumping binary search to get the $$$k$$$-th element. I implemented this in two separate structures: fenwick and fenwick_set.

The first one is the actual implementation of a Fenwick tree, while the second is a wrapper with set-like interface. Then, the fenwick structure is standard and straightforward, including finding lower bound of a prefix sum:

code

Then, the replies to the queries would look like this:

code

Here, we use an additional bit vector present to test if the element is actually present in the set. Submitting this solution, we find out that it works 213ms, while the top solution is around 140ms. How come? Isn't Fenwick so fast it's close to $$$O(1)$$$ in practice?

I brought this topic up in the Discord AC server, and chromate00 suggested quite a clever trick to enhance it further: Just integrate the Fenwick tree more with our favorite little mrmriend bitset! What it actually means is, since we represent a set, we can split its bitmask into blocks of 64 bits, each stored in a single uint64_t, and then Fenwick tree will be used to approximately answer queries based on popcounts of these 64-sized blocks, while the last part would be covered by bit magic.

In other words, this allows us to reduce memory consumption of the Fenwick tree itself from $$$n$$$ to $$$\frac{n}{64}$$$ (should be slightly better for cache too), and correspondingly query performance from $$$\log n$$$ to $$$\log \frac{n}{64}$$$. Note that for this, we also need to quickly find the $$$k$$$-th set bit in a 64-bit integer, and also find the number of set bits before the $$$k$$$-th bit. The second one is straightforward with std::popcount:

    size_t order_of_bit(uint64_t x, size_t k) {
        return k ? std::popcount(x << (64 - k)) : 0;
    }

The first one is less so, but it is also doable "quickly" with bmi2 intrinsic:

    size_t kth_set_bit(uint64_t x, size_t k) {
        return std::countr_zero(_pdep_u64(1ULL << k, x));
    }

Here, _pdep_u64 takes a bitmask as the first argument and applies it to only set bits of the second argument. In other words, _pdep_u64(1 << k, x) is 1 << t, where $$$t$$$ is the $$$k$$$-th bit of $$$x$$$. Doing all this, and also adding fast io on top, I've managed to outperform the top-1 solution by 4 ms 😃

Note: You might want to do #pragma GCC target("bmi2,popcount") for this to work properly.

Bonus

Do you like me hate coordinate compression? Well, you're in the right place! From now on, you can use

    auto compress_coords(auto &coords) {
        std::vector<int> original;
        original.reserve(size(coords));
        std::ranges::sort(coords);
        int idx = -1, prev = -1;
        for(auto &x: coords) {
            if(x != prev) {
                idx++;
                prev = x;
                original.push_back(x);
            }
            x.get() = idx;
        }
        return original;
    }

The code above takes a range of reference_wrapper<int>, then automatically assigns all concerned values to their order index in the sorted array, and returns the sorted vector of all distinct original values. This way, you no longer need to disrupt your main function with stupid things such as a[i] = lower_bound(begin(srt), end(srt), a[i]) - begin(srt), you just collect all your references in the array, and give the array to compress_coords! See how simple it is:

    vector<reference_wrapper<int>> coords;
    for(auto &it: a) {
        cin >> it;
        coords.push_back(ref(it));
    }
    vector queries(q, pair{0, 0});
    for(auto &[t, x]: queries) {
        cin >> t >> x;
        if(t != 2) {
            coords.push_back(ref(x));
        }
    }
    auto values = compress_coords(coords);

After that, you can treat a[i] and q[i] as if they are already compressed, and you can always put them as an index in values if you want to recover their original value. Simple and universal, am I right?

P.S. All these are conveniently implemented and structured here in CP-Algorithms library, so you might check it out if you want.

P.P.S. Are there any more efficient yet simple structures for Ordered Set problem?

Full text and comments »

  • Vote: I like it
  • +195
  • Vote: I do not like it

By adamant, history, 44 hours ago, In English

Hi everyone!

As Codeforces now supports C++23, it seems to be the right time to discuss some of the particularly interesting features.

Some noteworthy ones that were already mentioned elsewhere include:

  • views::zip that maps two ranges into pairs (A[i], B[i]).
  • views::enumerate that maps range into pairs (i, a[i]).
  • views::adjacent<k> that maps range into tuples (a[i], ..., a[i+k-1]).
  • views::cartesian_product that maps two ranges into pairs (A[i], B[j]) with all possible i and j.
  • Some more specialized views.
  • ranges::to<Container> that creates a container out of a view, e.g. to<vector>(views::iota(0, n)).
  • ranges::fold_left and ranges::fold_right, range versions of std::accumulate/std::reduce.
  • insert_range/append_range/prepend_range/assign_range for containers (not in GCC yet).
  • print/println for formatted printing (it seems that standard formatters for ranges are not in GCC yet).

But there are also two features that weren't covered in as much detail as they deserve, deducing this and generators.

Deducing this and recursive lambdas

Assume that you want to write a recursive lambda. What are your options? Naturally, you'd try something like this:

    auto fact = [&](int x) {
        return x ? x * fact(x - 1) : 1;
    };

You will not be allowed to do it, because inside the lambda, you use fact before its type is deduced. One way to circumvent it is to write function<int(int)> fact = ... instead. While it is attractive, it makes the calls to fact more expensive, and in certain cases might even lead you to TLE, e.g. if you try to use this for depth-first traversal of a big graph.

Until C++23, the best practice was to do something like this:

    auto fact = [&](auto &&self, int x) -> int {
        return x ? x * self(self, x - 1) : 1;
    };
    cout << fact(fact, n) << endl;

While much more efficient on practice, it looks very ugly. And C++23 helps us, allowing to do this instead:

    auto fact = [&](this auto fact, int x) -> int {
        return x ? x * fact(x - 1) : 1;
    };
    cout << fact(n) << endl;

Just as if it was a proper recursive function!

std::generator

Another interesting feature that I haven't seen mentioned in competitive programming discussions at all are coroutines. Assume that you need to factorize a number. If you depend on Pollard's rho algorithm, your flow probably looks as follows:

    vector<int> factors;
    void factorize(uint64_t m) {
        if(is_prime(m)) {
            factors.push_back(m);
        } else if(m > 1) {
            auto g = proper_divisor(m);
            factorize(g);
            factorize(m / g);
        }
    }

And it's always annoying that to store the result, you have to either keep a global vector, or take output vector as an argument by reference (and pass it around each time). Ideally you'd want to return a vector, but then you might be afraid of accidentally getting a quadratic runtime, and even besides that you'd need to write extra code to merge the results. Coroutines allow us to rewrite it as follows:

    std::generator<uint64_t> factorize(uint64_t m) {
        if(is_prime(m)) {
            co_yield m;
        } else if(m > 1) {
            auto g = proper_divisor(m);
            co_yield std::ranges::elements_of(factorize(g));
            co_yield std::ranges::elements_of(factorize(m / g));
        }
    }
    
    for(int p: factorize(m)) {
        ...
    }

In this manner, factorize will return a generator, which is basically a view wrapper to the function above which generates consecutive elements on the range "on the fly", while also suspending execution of the function between accesses to the resulting range. This way, we avoid the need to store the results of the recursive function somewhere, as well as the need to incorporate external logic or callbacks into the function if we want to do something as soon as you get the next element.

From performance perspective, of course, coroutines may be slightly inferior to having a global vector to store the results. For example, this submission to finding strongly connected components takes 278ms and 108 MB of memory, while its global vector version only needs 229ms and 65 MB. Still I think coroutines are pretty nice concept to keep in mind and might simplify code or make it better structured in a lot of cases.

Full text and comments »

  • Vote: I like it
  • +197
  • Vote: I do not like it

By adamant, history, 11 days ago, In English

Hi everyone!

In this blog, we will learn how to find the asymptotic expansion of $$$H_n = \sum\limits_{k=1}^n \frac{1}{k}$$$.

Motivational example

In the recent Meta Hacker Cup, problem C of the round 3 reduced to finding the sum of $$$\frac{1}{a+bk}$$$ for given $$$a$$$ and $$$b$$$, over all $$$k \in [L, R)$$$.

Now, putting it into Wolfram, you can see that

$$$ \sum\limits_{k=L}^{R-1} \frac{1}{a+bk} = \frac{\psi(\frac{a}{b}+R)-\psi(\frac{a}{b}+L)}{b}, $$$

where $$$\psi(z)$$$ is the digamma function. It is sufficient to solve this problem, as you can use boost or scipy to find it. But I feel like it's long time to satiate my curiosity on how it can be computed without knowing the digamma function in advance, and this blog is focused just on that.

Harmonic numbers

First of all, let's define $$$H(n) = \sum\limits_{k=1}^{n} \frac{1}{k}$$$, the $$$n$$$-th harmonic number. If $$$a = 0$$$, we can say that

$$$ \sum\limits_{k=L}^{R-1} \frac{1}{bk} = \frac{H(R-1)-H(L-1)}{b}. $$$

Notice how it is similar to the formula with the digamma function? That's not a coincidence! In fact, we can e.g. re-define $$$H(n)$$$ as

$$$ H(n) = \sum\limits_{k=0}^{n-1} \frac{1}{n-k}, $$$

and this definition will be quite easy to update to also allow non-integer $$$n$$$, by changing the upper sumation limit to $$$\lfloor n \rfloor - 1$$$.

With this in mind, we can re-express the whole sum as

$$$ \sum\limits_{k=L}^{R-1} \frac{1}{a+bk} = \frac{1}{b} \sum\limits_{k=0}^{R-L} \frac{1}{\frac{a}{b}+(R-k)} = \frac{H(\frac{a}{b}+R-1) - H(\frac{a}{b}+L-1)}{b}. $$$

This is also similar to the formula with $$$\psi$$$, because $$$\psi(n) = H(n-1)-\gamma$$$ for integer $$$n$$$, where $$$\gamma$$$ is the Euler–Mascheroni constant.

Asymptotics of $$$H(n)$$$

As a very rough first estimate, we can approximate

$$$ H(n) = \sum\limits_{k=1}^n \frac{1}{k} \approx \int\limits_1^n \frac{1}{x} dx = \ln n, $$$

which is a quite known estimation in many applications, e.g. when finding all divisors of all numbers up to $$$n$$$.

Now, the approach that we will use to finding the true asymptotic expansion of $$$H(n)$$$ is assuming that $$$H(n) = \ln n + F(\frac{1}{n})$$$, where $$$F(x)$$$ is an analytic function, meaning that it can be expressed as $$$F(x) = a_0 + a_1 x + a_2 x^2 + \dots$$$, i.e. as a power series.

Note: While $$$F(\frac{1}{n})$$$ is a convenient way to represent the expansion, it actually does not converge in any $$$n$$$. The idea here is rather that each prefix sum $$$F_k(x) = a_0 + \dots + a_k x^k$$$ serves as an increasingly better approximation as you put $$$n \to \infty$$$, but also provides worse approximations on smaller $$$n$$$.

Finding the expansion of $$$F(\frac{1}{n})$$$

With this assumption, let's find the coefficients of $$$F(x)$$$. For this, consider

$$$ H(n) - H(n-1) = \ln n - \ln (n-1) + F(\frac{1}{n})-F(\frac{1}{n-1}) = \frac{1}{n} $$$

In this form, we can rewrite the LHS as a power series in $$$\frac{1}{n}$$$. Indeed,

$$$ \ln n - \ln(n-1) = \ln \frac{n}{n-1} = \ln \frac{1}{1-\frac{1}{n}} = \sum\limits_{k=1}^\infty \frac{1}{kn^k}, $$$

as follows from the standard expansion $$$\log \frac{1}{1-x} = \sum\limits_{k=1}^\infty \frac{x^k}{k}$$$. At the same time,

$$$ F(n) - F(n-1) = \sum\limits_{k=1}^\infty a_k \left(\frac{1}{n^k} - \frac{1}{(n-1)^k}\right) $$$

can also be represent as a power series in $$$\frac{1}{n}$$$ as

$$$ \frac{1}{(n-1)^k} = \frac{1}{n^k} \frac{1}{(1-\frac{1}{n})^k} = \frac{1}{n^k} \sum\limits_{t=0}^\infty \binom{k+t-1}{t} \frac{1}{n^t}, $$$

as follows from the standard expansion for $$$\frac{1}{(1-x)^k}$$$. Putting it all back together, we arrive at

$$$ \sum\limits_{k=1}^\infty \frac{1}{n^k}\left[\frac{1}{k}-\sum\limits_{t=1}^{k-1} \binom{k-1}{k-t} a_t\right] = \frac{1}{n} $$$

For $$$k=1$$$, the coefficients near $$$\frac{1}{n^k}$$$ on both sides are already same, and for all higher $$$k$$$ this requirement turns into

$$$ \boxed{\sum\limits_{t=1}^{k-1} \binom{k-1}{k-t} a_t = \frac{1}{k}} $$$

Using the identity above for $$$k=2,3,\dots$$$ allows us to find $$$a_1 = \frac{1}{2}$$$, $$$a_2 = -\frac{1}{12}$$$, $$$a_3=0$$$, $$$a_4=\frac{1}{120}$$$, and so on. Okay but what about $$$a_0$$$? Well, actually, $$$a_0=\gamma$$$! But it is not important for our purposes at all, because it cancels out when we subtract $$$H(L-1)$$$ from $$$H(R-1)$$$.

Relation to Riemann zeta function

One can also derive the same result in the form

$$$ H(n) = \ln n + \gamma + \frac{1}{2n} + \sum\limits_{k=2}^{\infty} \frac{\zeta(1-k)}{n^k}, $$$

where $$$\zeta(x)$$$ is the Riemann zeta-function that already occurred e.g. here, but I fail to give any meaningful interpretation to this fact.

One highly "illegal" way to interpret this is as follows. We previously said it makes sense to define

$$$ H(n) = \sum\limits_{k=0}^{n-1} \frac{1}{n-k} $$$

But we can rewrite it as

$$$ H(n) = \frac{1}{n} \sum\limits_{k=0}^{n-1} \frac{1}{1-\frac{k}{n}} = \frac{1}{n}\sum\limits_{k=0}^{n-1} \sum\limits_{t=0}^\infty \frac{k^t}{n^t} = \sum\limits_{t=0}^{\infty} \frac{1}{n^{t+1}} \sum\limits_{k=0}^{n-1} k^t $$$

Now, we already know that $$$\sum\limits_{k=1}^{\infty} k^t = \zeta(-t)$$$, so at $$$n \to \infty$$$ we get

$$$ H(n) \approx \frac{1}{2n} + \sum\limits_{t=2}^\infty \frac{\zeta(1-t)}{n^t}, $$$

except that what we did was very illegal, and hence it missed the $$$\ln n + \gamma$$$ part completely. But as always with Riemann's zeta function, it quite surprisingly allows us to get estimations for stuff that is actually analytic quite precisely.

Afterthoughts

Are there any simpler ways to derive it?

Full text and comments »

  • Vote: I like it
  • +105
  • Vote: I do not like it

By adamant, history, 5 weeks ago, In English

Hi everyone!

I'm posting this on behalf of CP-Algorithms, a community project that started off in 2014 by RodionGork as a translation of e-maxx, a Russian go-to resource at the time by e-maxx for learning core competitive programming algorithms. Since then, CP-Algorithms grew quite a lot (which also prompted a rename from original project name e-maxx-eng) and includes a lot of new, original articles, and a lot of translated articles were enhanced and/or extended or even completely rewritten, amounting to a total of 157 articles at the moment.

At the moment, the project is largely maintained by Jakube and adamant (that's me), but as it happens, we don't have as much time to dedicate to it as we used to, so we're looking for some fresh blood to join the effort. This means both potential contributors and maintainers.

Contributors

As a community project, it is largely driven by volunteering efforts of people who write and translate articles. Moreover, similar to previous years, right about now DigitalOcean is conducting Hacktoberfest, an initiative that will award every participant which will make 4 approved pull requests on Github (in participating projects) during the month of October with a cool, free shirt

UPD: sorry, it's just a digital badge on holopin instead of t-shirts starting last year ☹️

Our project participates in Hacktoberfest, so it could be an easy way for you to contribute into open source and get a t-shirt for it. Not sure what to help us with? Consider the following:

  • GitHub issues marked with "bug" or "enhancement" tags;
  • Translation progress indicates which articles still need to be translated;
  • Write a new article on the topic of your liking or from a "new-article-suggestion" tags in GitHub issues;
  • Improve old articles (fix typos, grammar, style, etc);
  • Add images (make sure they're your original work, or adhere to image's license!).

See How to Contribute page for some instructions, or just click on a pencil icon in the upper-right corner of any article to propose changes. You can also use the Article Preview page to see how your changes will look like when they're actually added to the site. If you still have any questions about the process, don't hesitate to reach out to me directly 😊

Maintainers

Besides regular contributors, we're in dire need of having more people joining the maintainer team. You would be granted a right to contribute to the project directly without prior approval, and will need to exercise it appropriately, both when making your own contributions and when reviewing open issues and pull requests that you will be able to merge into the main branch once you think they're good enough.

On top of it, some time ago I started out a competitive programming library with automatic verification via Library Checker as an auxiliary project to CP-Algorithms. Ideally, I would like to let more people join it in the future, and also facilitate its integration into the main website and its articles somehow. Having another motivated maintainer to discuss it and work on it together would be fantastic!

Please reach out to me or Jakob if you're interested, and let us know of any of your prior experience in technical writing, computer science and competitive programming. We will be happy to expand our team!

Full text and comments »

  • Vote: I like it
  • +347
  • Vote: I do not like it

By adamant, history, 2 months ago, In English

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

Full text and comments »

  • Vote: I like it
  • +200
  • Vote: I do not like it

By adamant, history, 3 months ago, In English

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!

About Universal Cup

Full text and comments »

  • Vote: I like it
  • +52
  • Vote: I do not like it

By adamant, 5 months ago, In English

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:

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

Full text and comments »

  • Vote: I like it
  • +228
  • Vote: I do not like it

By adamant, history, 5 months ago, In English

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.

Full text and comments »

  • Vote: I like it
  • -25
  • Vote: I do not like it

By adamant, history, 5 months ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +133
  • Vote: I do not like it

By adamant, history, 6 months ago, In English

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

Full text and comments »

  • Vote: I like it
  • +118
  • Vote: I do not like it

By adamant, history, 6 months ago, In English

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

Full text and comments »

  • Vote: I like it
  • +120
  • Vote: I do not like it

By adamant, history, 6 months ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +259
  • Vote: I do not like it

By adamant, history, 9 months ago, In English

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!

Full text and comments »

  • Vote: I like it
  • +355
  • Vote: I do not like it

By adamant, 10 months ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +362
  • Vote: I do not like it

By adamant, history, 11 months ago, In English

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:

A
B
C
D
E
F
G
H
I
J
K

Full text and comments »

  • Vote: I like it
  • +109
  • Vote: I do not like it

By adamant, history, 11 months ago, In English

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:

$$$ \sum\limits_k (-1)^k \binom{a+b}{a+k} \binom{b+c}{b+k} \binom{c+a}{c+k} = \binom{a+b+c}{a,b,c}. $$$

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,

$$$ \boxed{[\mathbf t^\mathbf k] \prod\limits_{i=1}^n \left(\sum\limits_{j=1}^n a_{ij} t_j\right)^{k_i} = [\mathbf x^\mathbf k] \det(\mathbf I-\mathbf X \mathbf A)^{-1}} $$$

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.

Full text and comments »

  • Vote: I like it
  • +111
  • Vote: I do not like it

By adamant, history, 13 months ago, In English

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.

You can find the remaining photos here

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:

Full text and comments »

  • Vote: I like it
  • +92
  • Vote: I do not like it

By adamant, history, 16 months ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +379
  • Vote: I do not like it

By adamant, history, 16 months ago, In English

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:

code

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?

Full text and comments »

  • Vote: I like it
  • +245
  • Vote: I do not like it

By adamant, history, 16 months ago, In English

Hi everyone!

Two problems were recently added to Library Checker:

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

Full text and comments »

  • Vote: I like it
  • +147
  • Vote: I do not like it

By adamant, history, 16 months ago, In English

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!

Full text and comments »

  • Vote: I like it
  • +197
  • Vote: I do not like it

By adamant, history, 17 months ago, In English

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.

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.

Full text and comments »

  • Vote: I like it
  • +113
  • Vote: I do not like it

By adamant, history, 17 months ago, In English

Hi everyone!

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

$$$\begin{gather} \sum\limits_{k=1}^n \varphi(k) = ? \\ \sum\limits_{k=1}^n \sum\limits_{d|k} d^2 = ?? \\ \sum\limits_{x=1}^n \sum\limits_{y=1}^x \gcd(x, y) = ?!? \end{gather}$$$

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

$$$\begin{matrix} F(n) = \sum\limits_{i=1}^n f(i), & G(n) = \sum\limits_{j=1}^n g(j). \end{matrix}$$$

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.

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

Full text and comments »

  • Vote: I like it
  • +285
  • Vote: I do not like it

By adamant, history, 17 months ago, In English

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.

Definitions and notation

Full text and comments »

  • Vote: I like it
  • +182
  • Vote: I do not like it

By adamant, history, 17 months ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +205
  • Vote: I do not like it