Codeforces and Polygon may be unavailable from May 23, 4:00 (UTC) to May 23, 8:00 (UTC) due to technical maintenance. ×

adamant's blog

By adamant, history, 13 hours 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
  • +101
  • Vote: I do not like it

By adamant, history, 7 days 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, 2 weeks 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
  • +251
  • Vote: I do not like it

By adamant, history, 3 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, 4 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, 5 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, 6 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, 7 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, 10 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, 10 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, 11 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, 11 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, 11 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, 11 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, 11 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, 11 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

By adamant, history, 12 months ago, In English

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.

Full text and comments »

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

By adamant, history, 12 months ago, In English

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:

$$$ x^2 + y^2 = z. $$$

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

$$$ x+ iy = (1+i)^{k_0} p_{1}^{k_{1}/2} \dots p_n^{k_n/2} (x_{n+1}+iy_{n+1})^{k_{n+1}} \dots (x_m + iy_m)^{k_m}, $$$

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

Full text and comments »

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

By adamant, history, 13 months ago, In English

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.

Full text and comments »

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

By adamant, history, 13 months ago, In English

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.

Full text and comments »

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

By adamant, history, 13 months ago, In English

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:

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:

code

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?

Full text and comments »

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

By adamant, history, 13 months ago, In English

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

Full text and comments »

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

By adamant, history, 13 months ago, In English

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:

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

Full text and comments »

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

By adamant, history, 13 months ago, In English

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:

  1. Composition of functions is associative and has identities
  2. There is a set with exactly one element
  3. There is a set with no elements
  4. A function is determined by its effect on elements
  5. Given sets $$$X$$$ and $$$Y$$$, one can form their cartesian product $$$X \times Y$$$
  6. Given sets $$$X$$$ and $$$Y$$$, one can form the set of functions from $$$X$$$ to $$$Y$$$
  7. Given $$$f : X \to Y$$$ and $$$y \in Y$$$, one can form the inverse image $$$f^{-1}(y)$$$
  8. The subsets of a set $$$X$$$ correspond to the functions from $$$X$$$ to $$$\{0, 1\}$$$
  9. The natural numbers form a set
  10. Every surjection has a right inverse

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.

Full text and comments »

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

By adamant, history, 14 months ago, In English

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

$$$ c_k = \sum\limits_{i \circ j = k} a_i b_j, $$$

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.

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.

Full text and comments »

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