adamant's blog

By adamant, history, 2 years ago, In English

Hi everyone!

Today I'd like to write about Fibonacci numbers. Ever heard of them? Fibonacci sequence is defined as $$$F_n = F_{n-1} + F_{n-2}$$$.

It got me interested, what would the recurrence be like if it looked like $$$F_n = \alpha F_{n-p} + \beta F_{n-q}$$$ for $$$p \neq q$$$?


Timus — Fibonacci Sequence. The sequence $$$F$$$ satisfies the condition $$$F_n = F_{n-1} + F_{n-2}$$$. You're given $$$F_i$$$ and $$$F_j$$$, compute $$$F_n$$$.


Using $$$L(x^n) = F_n$$$ functional, we can say that we essentially need to solve the following system of equations:

$$$1 \equiv \alpha x^{-p} + \beta x^{-q} \pmod{x^2-x-1}.$$$

To get the actual solution from it, we should first understand what exactly is the remainder of $$$x^n$$$ modulo $$$x^2-x-1$$$. The remainder of $$$P(x)$$$ modulo $$$(x-a)(x-b)$$$ is generally determined by $$$P(a)$$$ and $$$P(b)$$$:

$$$ P(x) \equiv r \mod(x-a)(x-b) \iff \begin{cases}P(a) = r,\\ P(b)=r.\end{cases} $$$

Therefore, our equation above is, equivalent to the following:

$$$ \begin{cases} \alpha a^{-p} + \beta a^{-q} = 1,\\ \alpha b^{-p} + \beta b^{-q} = 1. \end{cases} $$$

The determinant of this system of equations is $$$a^{-p}b^{-q} - a^{-q}b^{-p}$$$. Solving the system, we get the solution

$$$ \begin{matrix} \alpha = \dfrac{b^{-q}-a^{-q}}{a^{-p}b^{-q} - a^{-q}b^{-p}}, & \beta = \dfrac{a^{-p}-b^{-p}}{a^{-p}b^{-q} - a^{-q}b^{-p}}. \end{matrix} $$$

Multiplying numerators and denominators by $$$a^q b^q$$$ for $$$\alpha$$$ and $$$a^p b^p$$$ for $$$\beta$$$, we get a nicer form:

$$$ \boxed{\begin{matrix} \alpha = \dfrac{a^q-b^q}{a^{q-p} - b^{q-p}}, & \beta = \dfrac{a^p-b^p}{a^{p-q} - b^{p-q}}. \end{matrix}} $$$

This is a solution for a second degree recurrence with the characteristic polynomial $$$(x-a)(x-b)$$$.

Note that for Fibonacci numbers in particular, due to Binet's formula, it holds that

$$$F_n = \frac{a^n-b^n}{a-b}.$$$

Substituting it back into $$$\alpha$$$ and $$$\beta$$$, we get

$$$ \boxed{F_n = \frac{F_q}{F_{q-p}} F_{n-p} + \frac{F_p}{F_{p-q}} F_{n-q}} $$$

which is a neat symmetric formula.

P. S. you can also derive it from Fibonacci matrix representation, but this way is much more fun, right?

UPD: I further simplified the explanation, should be much easier to follow it now.

Note that the generic solution only covers the case of $$$(x-a)(x-b)$$$ when $$$a \neq b$$$. When the characteristic polynomial is $$$(x-a)^2$$$, the remainder of $$$P(x)$$$ modulo $$$(x-a)^2$$$ is determined by $$$P(a)$$$ and $$$P'(a)$$$:

$$$ P(x) \equiv r \mod{(x-a)^2} \iff \begin{cases}P(a)=r,\\P'(a)=0.\end{cases} $$$

Therefore, we have a system of equations

$$$ \begin{cases} \alpha a^{-p} &+& \beta a^{-q} &=& 1,\\ \alpha p a^{-p-1} &+& \beta q a^{-q-1} &=& 0. \end{cases} $$$

For this system, the determinant is $$$\frac{q-p}{a^{p+q+1}}$$$ and the solution is

$$$ \boxed{\begin{matrix} \alpha = \dfrac{qa^p}{q-p},&\beta = \dfrac{pa^q}{p-q} \end{matrix}} $$$

Another interesting way to get this solution is via L'Hôpital's rule:

$$$ \lim\limits_{x \to 0}\frac{a^q-(a+x)^q}{a^{q-b}-(a+x)^{q-p}} = \lim\limits_{x \to 0}\frac{q(a+x)^{q-1}}{(q-p)(a+x)^{q-p-1}} = \frac{qa^p}{q-p}. $$$

Let's consider the more generic case of the characteristic polynomial $$$(x-\lambda_1)(x-\lambda_2)\dots (x-\lambda_k)$$$.


102129D - Basis Change. The sequence $$$F$$$ satisfies $$$F_n=\sum\limits_{i=1}^k a_i F_{n-i}$$$. Find $$$c_1,\dots,c_n$$$ such that $$$F_n = \sum\limits_{i=1}^k c_i F_{n-b_i}$$$.


We need to find $$$\alpha_1, \dots, \alpha_k$$$ such that $$$F_n = \alpha_1 F_{n-c_1} + \dots + \alpha_k F_{n-c_k}$$$. It boils down to the system of equations

$$$ \begin{cases} \alpha_1 \lambda_1^{-c_1}+\dots+\alpha_k \lambda_1^{-c_1} = 1,\\ \alpha_1 \lambda_2^{-c_2}+\dots+\alpha_k \lambda_2^{-c_k} = 1,\\ \dots\\ \alpha_1 \lambda_k^{-c_k}+\dots+\alpha_k \lambda_k^{-c_k} = 1.\\ \end{cases} $$$

This system of equations has a following matrix:

$$$ A=\begin{bmatrix} \lambda_1^{-c_1} & \lambda_1^{-c_2} & \dots & \lambda_1^{-c_k} \\ \lambda_2^{-c_1} & \lambda_2^{-c_2} & \dots & \lambda_2^{-c_k} \\ \vdots & \vdots & \ddots & \vdots \\ \lambda_k^{-c_1} & \lambda_k^{-c_2} & \dots & \lambda_k^{-c_k} \end{bmatrix} $$$

Matrices of this kind are called alternant matrices. Let's denote its determinant as $$$D_{\lambda_1, \dots, \lambda_k}(c_1, \dots, c_k)$$$, then the solution is

$$$ \alpha_i = \dfrac{D_{\lambda_1, \dots, \lambda_k}(c_1, \dots, c_{i-1}, \color{red}{0}, c_{i+1}, \dots, c_k)}{D_{\lambda_1, \dots, \lambda_k}(c_1, \dots, c_{i-1}, \color{blue}{c_i}, c_{i+1}, \dots, c_k)}. $$$

Unfortunately, on practice in makes more sense to find $$$\alpha_i$$$ with the Gaussian elimination rather than with these direct formulas.

Full text and comments »

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

By adamant, history, 2 years ago, In English

Hi everyone!

It's been quite some time since I wrote two previous articles in the cycle:

Part 1: Introduction
Part 2: Properties and interpretation
Part 3: In competitive programming

This time I finally decided to publish something on how one can actually use continued fractions in competitive programming problems.

Few months ago, I joined CP-Algorithms as a collaborator. The website also underwent a major design update recently, so I decided it would be great to use this opportunity and publish my new article there, so here it is:

CP-Algorithms — Continued fractions

It took me quite a while to write and I made sure to not only describe common competitive programming challenges related to continued fractions, but also to describe the whole concept from scratch. That being said, article is supposed to be self-contained.

Main covered topics:

  1. Notion of continued fractions, convergents, semiconvergents, complete quotients.
  2. Recurrence to compute convergents, notion of continuant.
  3. Connection of continued fractions with the Stern-Brocot tree and the Calkin-Wilf tree.
  4. Convergence rate with continued fractions.
  5. Linear fractional transformations, quadratic irrationalities.
  6. Geometric interpretation of continued fractions and convergents.

I really hope that I managed to simplify the general story-telling compared to previous 2 articles.

Here are the major problems that are dealt with in the article:

  • Given $$$a_1, \dots, a_n$$$, quickly compute $$$[a_l; a_{l+1}, \dots, a_r]$$$ in queries.
  • Which number of $$$A=[a_0; a_1, \dots, a_n]$$$ and $$$B=[b_0; b_1, \dots, b_m]$$$ is smaller? How to emulate $$$A-\varepsilon$$$ and $$$A+\varepsilon$$$?
  • Given $$$A=[a_0; a_1, \dots, a_n]$$$ and $$$B=[b_0; b_1, \dots, b_m]$$$, compute the continued fraction representations of $$$A+B$$$ and $$$A \cdot B$$$.
  • Given $$$\frac{0}{1} \leq \frac{p_0}{q_0} < \frac{p_1}{q_1} \leq \frac{1}{0}$$$, find $$$\frac{p}{q}$$$ such that $$$(q,p)$$$ is lexicographically smallest and $$$\frac{p_0}{q_0} < \frac{p}{q} < \frac{p_1}{q_1}$$$.
  • Given $$$x$$$ and $$$k$$$, $$$x$$$ is not a perfect square. Let $$$\sqrt x = [a_0; a_1, \dots]$$$, find $$$\frac{p_k}{q_k}=[a_0; a_1, \dots, a_k]$$$ for $$$0 \leq k \leq 10^9$$$.
  • Given $$$r$$$ and $$$m$$$, find the minimum value of $$$q r \pmod m$$$ on $$$1 \leq q \leq n$$$.
  • Given $$$r$$$ and $$$m$$$, find $$$\frac{p}{q}$$$ such that $$$p, q \leq \sqrt{m}$$$ and $$$p q^{-1} \equiv r \pmod m$$$.
  • Given $$$p$$$, $$$q$$$ and $$$b$$$, construct the convex hull of lattice points below the line $$$y = \frac{px+b}{q}$$$ on $$$0 \leq x \leq n$$$.
  • Given $$$A$$$, $$$B$$$ and $$$C$$$, find the maximum value of $$$Ax+By$$$ on $$$x, y \geq 0$$$ and $$$Ax + By \leq C$$$.
  • Given $$$p$$$, $$$q$$$ and $$$b$$$, compute the following sum:
$$$\sum\limits_{x=1}^n \lfloor \frac{px+b}{q} \rfloor.$$$

So far, here is the list of problems that are explained in the article:

And an additional list of practice problems where continued fractions could be useful:

There are likely much more problems where continued fractions are used, please mention them in the comments if you know any!

Finally, since CP-Algorithms is supposed to be a wiki-like project (that is, to grow and get better as time goes by), please feel free to comment on any issues that you might find while reading the article, ask questions or suggest any improvements. You can do so in the comments below or in the issues section of the CP-Algorithms GitHub repo. You can also suggest changes via pull request functionality.

Full text and comments »

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

By adamant, history, 2 years ago, In English

Hi everyone!

There are already dozens of blogs on linear recurrences, why not make another one? In this article, my main goal is to highlight the possible approaches to solving linear recurrence relations, their applications and implications. I will try to derive the results with different approaches independently from each other, but will also highlight similarities between them after they're derived.

Definitions

Def. 1. An order $$$d$$$ homogeneous linear recurrence with constant coefficients (or linear recurrence) is an equation of the form

$$$ F_n = \sum\limits_{k=1}^d a_k F_{n-k}. $$$

Def. 2. In the equation above, the coefficients $$$a_1, \dots, a_d \in R$$$ are called the recurrence parameters,

Def. 3. and a sequence $$$F_0, F_1, \dots \in R$$$ is called an order $$$d$$$ linear recurrence sequence.


The most common task with linear recurrences is, given initial coefficients $$$F_0, F_1, \dots, F_{d-1}$$$, to find the value of $$$F_n$$$.
Example 1. A famous Fibonacci sequence $$$F_n = F_{n-1} + F_{n-2}$$$ is an order 2 linear recurrence sequence.

Example 2. Let $$$F_n = n^2$$$. One can prove that $$$F_n = 3 F_{n-1} - 3 F_{n-2} + F_{n-3}$$$.

Example 3. Moreover, for $$$F_n = P(n)$$$, where $$$P(n)$$$ is a degree $$$d$$$ polynomial, it holds that

$$$ F_n = \sum\limits_{k=1}^{d+1} (-1)^{k+1}\binom{d+1}{k} F_{n-k}. $$$

If this fact is not obvious to you, do not worry as it will be explained further below.


Finally, before proceeding to next sections, we'll need one more definition.
Def. 4. A polynomial
$$$ A(x) = x^d - \sum\limits_{k=1}^d a_k x^{d-k} $$$

is called the characteristic polynomial of the linear recurrence defined by $$$a_1, \dots, a_d$$$.

Example 4. For Fibonacci sequence, the characteristic polynomial is $$$A(x) = x^2-x-1$$$.

Full text and comments »

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

By adamant, history, 2 years ago, In English

Hi everyone!

Today I'd like to write about some polynomials which are invariant under the rotation and relabeling in euclidean spaces. Model problems work with points in the 3D space, however both ideas, to some extent, might be generalized for higher number of dimensions. They might be useful to solve some geometric problems under the right conditions. I used some ideas around them in two problems that I set earlier.

Congruence check in random points

You're given two set of lines in 3D space. The second set of lines was obtained from the first one by the rotation and relabeling. You're guaranteed that the first set of lines was generated uniformly at random on the sphere, find the corresponding label permutation.

Actual problem: 102354F - Cosmic Crossroads.

Solution

Let $$$P_4(x, y, z) = \sum\limits_{l=1}^n \left((x-x_l)^2+(y-y_l)^2 + (z-z_l)^2\right)^2$$$. It is a fourth degree polynomial, which geometric meaning is the sum of distances from $$$(x, y, z)$$$ to all points in the set, each distance raised to power $$$4$$$. Distance is preserved under rotation, hence this expression is invariant under rotation transform. On the other hand it may be rewritten as

$$$P_4(x, y, z) = \sum\limits_{i=0}^4 \sum\limits_{j=0}^4 \sum\limits_{k=0}^4 A_{ijk} x^i y^j z^k,$$$

where $$$A_{ijk}$$$ is obtained as the sum over all points $$$(x_l,y_l,z_l)$$$ from the initial set. To find the permutation, it is enough to calculate $$$P_4$$$ for all points in both sets and them match points with the same index after they were sorted by the corresponding $$$P_4$$$ value.

It is tempting to try the same trick with $$$P_2(x, y, z)$$$, but it is the same for all the points in the set for this specific problem:

$$$ \begin{align} P_2(x, y, z) =& \sum\limits_{l=1}^n [(x-x_l)^2+(y-y_l)^2+(z-z_l)^2]\\ =& n \cdot (x^2+y^2+z^2) - 2x \sum\limits_{l=1}^n x_l - 2y \sum\limits_{l=1}^n y_l - 2z \sum\limits_{l=1}^n z_l + \sum\limits_{l=1}^n [x_l^2+y_l^2+z_l^2] \\ =& n \left[\left(x-\bar x\right)^2 + \left(y-\bar y\right)^2 + \left(z-\bar z\right)^2\right] - n(\bar x^2+\bar y^2+\bar z^2) + \sum\limits_{l=1}^n (x_l^2 + y_l^2 + z_l^2), \end{align} $$$

where $$$\bar x$$$, $$$\bar y$$$ and $$$\bar z$$$ are the mean values of $$$x_l$$$, $$$y_l$$$ and $$$z_l$$$ correspondingly. As you can see, non-constant part here is simply the squared distance from $$$(x, y, z)$$$ to the center of mass of the points in the set. Thus, $$$P_2(x, y, z)$$$ is the same for all points having the same distance from the center of mass, so it is of no use in 102354F - Cosmic Crossroads, as all the points have this distance equal to $$$1$$$ in the input.

Burunduk1 taught me this trick after the Petrozavodsk camp round which featured the model problem.

Sum of squared distances to the axis passing through the origin

You're given a set of points $$$r_k=(x_k, y_k, z_k)$$$. A torque needed to rotate the system of points around the axis $$$r=(x, y, z)$$$ is proportional to the sum of squared distances to the axis across all points. You need to find the minimum amount of points that have to be added to the set, so that the torque needed to rotate it around any axis passing through the origin is exactly the same.

Actual problem: Hackerrank — The Axis of Awesome

Solution

The squared distance from the point $$$r_k$$$ to the axis $$$r$$$ is expressed as

$$$\dfrac{|r_k \times r|^2}{r \cdot r} = \dfrac{(y_k z - z_k y)^2+(x_k z - z_k x)^2+(x_k y - y_k x)^2}{x^2+y^2+z^2}.$$$

The numerator here is a quadratic form, hence can be rewritten as

$$$|r_k \times r|^2 = \begin{pmatrix}x & y & z\end{pmatrix} \begin{pmatrix} y_k^2 + z_k^2 & -x_k y_k & -x_k z_k \\ -x_k y_k & x_k^2 + z_k^2 & -y_k z_k \\ -x_k z_k & -y_k z_k & x_k^2 + y_k^2 \end{pmatrix} \begin{pmatrix}x \\ y \\ z\end{pmatrix}.$$$

Correspondingly, the sum of squared distances for $$$k=1..n$$$ is defined by the quadratic form

$$$I = \sum\limits_{k=1}^n\begin{pmatrix} y_k^2 + z_k^2 & -x_k y_k & -x_k z_k \\ -x_k y_k & x_k^2 + z_k^2 & -y_k z_k \\ -x_k z_k & -y_k z_k & x_k^2 + y_k^2 \end{pmatrix},$$$

known in analytic mechanics as the inertia tensor. As any other tensor, its coordinate form is invariant under rotation.

Inertia tensor is a positive semidefinite quadratic form, hence there is an orthonormal basis in which it is diagonal:

$$$I = \begin{pmatrix}I_1 & 0 & 0 \\ 0 & I_2 & 0 \\ 0 & 0 & I_3\end{pmatrix}.$$$

Here $$$I_1$$$, $$$I_2$$$ and $$$I_3$$$ are the eigenvalues of $$$I$$$, also called the principal moments of inertia (corresponding eigenvectors are called the principal axes of inertia). From this representation we deduce that the condition from the statement is held if and only if $$$I_1 = I_2 = I_3$$$.

Adding a single point on a principal axis would only increase principal moments on the other axes. For example, adding $$$(x, 0, 0)$$$ would increase $$$I_2$$$ and $$$I_3$$$ by $$$x^2$$$. Knowing this, one can prove that the answer to the problem is exactly $$$3-m$$$ where $$$m$$$ is the multiplicity of the smallest eigenvalue of $$$I$$$.

Applying it to the first problem

Now, another interesting observation about inertia tensor is that both principal inertia moments and principal inertia axes would be preserved under rotation. It means that in the first problem, another possible way to find the corresponding rotation and the permutation of points is to find principal inertia axes for both sets of points and then find a rotation that matches corresponding principal inertia axes in the first and the second sets of points.

Unfortunately, this method still requires that principal inertia moments are all distinct (which generally holds for random sets of points), otherwise there would be an infinite amount of eigendecompositions of $$$I$$$.

Full text and comments »

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

By adamant, history, 2 years ago, In English

Hi everyone!

Today I'd like to write another blog about polynomials. Consider the following problem:

You're given $$$P(x) = a_0 + a_1 x + \dots + a_{n-1} x^{n-1}$$$, you need to compute $$$P(x+a) = b_0 + b_1 x + \dots + b_{n-1} x^{n-1}$$$.

There is a well-known solution to this, which involves some direct manipulation with coefficients. However, I usually prefer approach that is more similar to synthetic geometry when instead of low-level coordinate work, we work on a higher level of abstraction. Of course, we can't get rid of direct coefficient manipulation completely, as we still need to do e.g. polynomial multiplications.

But we can restrict direct manipulation with coefficients to some minimal number of black-boxed operations and then strive to only use these operations in our work. With this goal in mind, we will develop an appropriate framework for it.

Thanks to clyring for inspiring me to write about it with this comment. You can check it for another nice application of calculating $$$g(D) f(x)$$$ for a specific series $$$g(D)$$$ over the differentiation operator:

While this article mostly works with $$$e^{aD} f(x)$$$ to find $$$f(x+a)$$$, there you have to calculate

$$$\left(\frac{D}{1-e^{-D}}\right)p(x)$$$

to find a polynomial $$$f(x)$$$ such that $$$f(x) = p(0)+p(1)+\dots+p(x)$$$ for a given polynomial $$$p(x)$$$.

Key results

Let $$$[\cdot]$$$ and $$$\{ \cdot \}$$$ be a linear operators in the space of formal power series such that $$$[x^k] = \frac{x^k}{k!}$$$ and $$$\{x^k\} = k! x^k$$$.

The transforms $$$[\cdot]$$$ and $$$\{\cdot \}$$$ are called the Borel transform and the Laplace transform correspondingly.

As we also work with negative coefficients here, we define $$$\frac{1}{k!}=0$$$ for $$$k < 0$$$, hence $$$[x^k]=0$$$ for such $$$k$$$.

In this notion,

$$$f(x+a) = e^{aD} f(x) = [e^{ax^{-1}}\{f(x)\}],$$$

where $$$D=\frac{d}{d x}$$$ is the differentiation operator. Thus, $$$\{f(x+a)\}$$$ is a part with non-negative coefficients of the cross-correlation of $$$e^{ax}$$$ and $$$\{f(x)\}$$$ as formal power series. More generally, for arbitrary formal power series $$$g(D)$$$, it holds that

$$$g(D) f(x) = [g(x^{-1})\{f(x)\}],$$$

that is $$$\{g(D) f(x)\}$$$ is exactly the non-negative part of the cross-correlation of $$$g(x)$$$ and $$$\{f(x)\}$$$.

Detailed explanation is below.

Full text and comments »

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

By adamant, history, 2 years ago, In English

Hi everyone!

Today I want to write about the inversions in permutations. The blog is mostly inspired by the problem С from Day 3 of 2022 winter Petrozavodsk programming camp. I will also try to shed some light on the relation between inversions and $$$q$$$-analogs.

Key results

Let $$$F(x)=a_0+a_1x+a_2x^2+\dots$$$, then $$$F(e^x)$$$ is the exponential generating function of

$$$b_i = \sum\limits_{k=0}^\infty a_k k^i.$$$

In other words, it is a moment-generating function of the parameter by which $$$F(x)$$$ enumerates objects of class $$$F$$$.

Motivational example:

The generating function of permutations of size $$$n$$$, enumerated by the number of inversions is

$$$F_n(x) = \prod\limits_{k=1}^n \frac{1-x^k}{1-x}.$$$

The moment-generating function for the number of inversions in a permutation of size $$$n$$$ is

$$$G_n(x) = \prod\limits_{k=1}^n \frac{1-e^{kx}}{1-e^x}.$$$

Full text and comments »

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

By adamant, history, 2 years ago, In English

Hi everyone!

I'm currently trying to write an article about $$$\lambda$$$-optimization in dynamic programming, commonly known as "aliens trick". While writing it, I stumbled upon a fact which, I believe, is a somewhat common knowledge, but is rarely written out and proved explicitly. This fact is that we sometimes can repeatedly use ternary search when we need to optimize a multi-dimensional function.

Thanks to

  • mango_lassi for a useful discussion on this and for counter-example on integer ternary search!
  • Neodym for useful comments and remarks about the article structure.

Full text and comments »

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

By adamant, history, 2 years ago, In English

Hi everyone!

Today I'd like to write yet another blog about polynomials. Specifically, I will cover the relationship between polynomial interpolation and Chinese remainder theorem, and I will also highlight how it is useful when one needs an explicit meaningful solution for partial fraction decomposition.

Full text and comments »

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

By adamant, history, 2 years ago, In English

Hi everyone!

This time I'd like to write about what's widely known as "Aliens trick" (as it got popularized after 2016 IOI problem called Aliens). There are already some articles about it here and there, and I'd like to summarize them, while also adding insights into the connection between this trick and generic Lagrange multipliers and Lagrangian duality which often occurs in e.g. linear programming problems.

Familiarity with a previous blog about ternary search or, at the very least, definitions and propositions from it is expected.

Great thanks to mango_lassi and 300iq for useful discussions and some key insights on this.

Note that although explanation here might be quite verbose and hard to comprehend at first, the algorithm itself is stunningly simple.

Another point that I'd like to highlight for those already familiar with "Aliens trick" is that typical solutions using it require binary search on lambdas to reach specified constraint by minimizing its value for specific $$$\lambda$$$. However, this part is actually unnecessary and you don't even have to calculate the value of constraint function at all within your search.

It further simplifies the algorithm and extends applicability of aliens trick to the cases when it is hard to minimize constraint function while simultaneously minimizing target function for the given $$$\lambda$$$.

Tldr.

Problem. Let $$$f : X \to \mathbb R$$$ and $$$g : X \to \mathbb R^c$$$. You need to solve the constrained optimization problem

$$$\begin{gather}f(x) \to \min,\\ g(x) = 0.\end{gather}$$$

Auxiliary function. Let $$$t(\lambda) = \inf_x [f(x) - \lambda \cdot g(x)]$$$. Finding $$$t(\lambda)$$$ is unconstrained problem and is usually much simpler.

Equivalently, $$$t(\lambda) = \inf_y [h(y) - \lambda \cdot y]$$$ where $$$h(y)$$$ is the minimum possible $$$f(x)$$$ subject to $$$g(x)=y$$$.

As a point-wise minimum of linear functions, $$$t(\lambda)$$$ is concave, therefore its maximum can be found with ternary search.

Key observation. By definition, $$$t(\lambda) \leq h(0)$$$ for any $$$\lambda$$$, thus $$$\max_\lambda t(\lambda)$$$ provides a lower bound for $$$h(0)$$$. When $$$h(y)$$$ is convex, inequality turns into equation, that is $$$\max_\lambda t(\lambda) = h(0) = f(x^*)$$$ where $$$x^*$$$ is the solution to the minimization problem.

Solution. Assume that $$$t(\lambda)$$$ is computable for any $$$\lambda$$$ and $$$h(y)$$$ is convex. Then find $$$\max_\lambda t(\lambda)$$$ with the ternary search on $$$t(\lambda)$$$ over possible values of $$$\lambda$$$. This maximum is equal to the minimum $$$f(x)$$$ subject to $$$g(x)=0$$$.

If $$$g(x)$$$ and $$$f(x)$$$ are integer functions, $$$\lambda_i$$$ corresponds to $$$h(y_i) - h(y_i-1)$$$ and can be found among integers.


Boring and somewhat rigorous explanation is below, problem examples are belower.

Full text and comments »

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

By adamant, history, 3 years ago, In English

Hi everyone!

Some time ago Monogon wrote an article about Edmonds blossom algorithm to find the maximum matching in an arbitrary graph. Since the problem has a very nice algebraic approach, I wanted to share it as well. I'll start with something very short and elaborate later on.

Library Checker — Matching on General Graph. Given a simple undirected graph on $$$N \leq 500$$$ vertices, find the maximum matching.


tl;dr. The Tutte matrix of the graph $$$G=(V, E)$$$ is

\begin{equation} T(x_{12}, \dots, x_{(n-1)n}) = \begin{pmatrix} 0 & x_{12} e_{12} & x_{13} e_{13} & \dots & x_{1n} e_{1n} \newline -x_{12} e_{12} & 0 & x_{23} e_{23} & \dots & x_{2n} e_{2n} \newline -x_{13} e_{13} & -x_{23} e_{23} & 0 & \dots & x_{3n} e_{3n} \newline \vdots & \vdots & \vdots & \ddots & \vdots \newline -x_{1n} e_{1n} & -x_{2n} e_{2n} & -x_{3n} e_{3n} & \dots & 0 \end{pmatrix} \end{equation}

Here $$$e_{ij}=1$$$ if $$$(i,j)\in E$$$ and $$$e_{ij}=0$$$ otherwise, $$$x_{ij}$$$ are formal variables. Key facts:

  1. Graph has a perfect matching if and only if $$$\det T \neq 0$$$ when considered as polynomial of $$$x_{ij}$$$.
  2. Rank of $$$T$$$ is the number of vertices in the maximum matching.
  3. Maximal linearly independent subset of rows corresponds to the subset of vertices on which it is a perfect matching.
  4. If graph has a perfect matching, $$$(T^{-1})_{ij} \neq 0$$$ iff there exists a perfect matching which includes the edge $$$(i,j)$$$.
  5. After such $$$(i,j)$$$ is found, to fix it in the matching one can eliminate $$$i$$$-th and $$$j$$$-th rows and columns of $$$T^{-1}$$$ and find next edge.

Randomization comes when we substitute $$$x_{ij}$$$ with random values. It can be proven that conditions above still hold with high probability. This provides us with $$$O(n^3)$$$ algorithm to find maximum matching in general graph. For details, dive below.

Full text and comments »

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

By adamant, history, 3 years ago, In English

Hi everyone!

Recently aryanc403 brought up a topic of subset convolution and some operations related to it.

This inspired me to write this blog entry as existing explanations on how it works seemed unintuitive for me. I believe that having viable interpretations of how things work is of extreme importance as it greatly simplifies understanding and allows us to reproduce some results without lust learning them by heart.

Also this approach allows us to easily and intuitively generalize subset convolution to sum over $$$i \cup j = k$$$ and $$$|i \cap j|=l$$$, while in competitive programming we usually only do it for $$$|i \cap j|=0$$$. Enjoy the reading!

Full text and comments »

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

By adamant, history, 3 years ago, In English

Hi everyone!

Five days have passed since my previous post which was generally well received, so I'll continue doing posts like this for time being.

Abstract algebra is among my favorite subjects. One particular thing I find impressive is the associativity of binary operations. One of harder problems from my contests revolves around this property as you need to construct an operation with a given number of non-associative triples. This time I want to talk about how one can check this property for both groups and arbitrary magmas.

First part of my post is about Light's associativity test and how it can be used to deterministically check whether an operation defines a group in $$$O(n^2 \log n)$$$. Second part of the post is about Rajagopalan and Schulman probabilistic identity testing which allows to test associativity in $$$O(n^2 \log n \log \delta^{-1})$$$ where $$$\delta$$$ is error tolerance. Finally, the third part of my post is dedicated to the proof of Rajagopalan–Schulman method and bears some insights into identity verification in general and higher-dimensional linear algebra.

For convenience, these three parts are separated by horizontal rule.

Full text and comments »

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

By adamant, history, 3 years ago, In English

Hi everyone!

Long time no see. 3 years ago I announced a Telegram channel. Unfortunately, for the last ~1.5 years I had a total lack of inspiration for new blog posts. Well, now I have a glimpse of it once again, so I want to continue writing about interesting stuff. Here's some example:

Full text and comments »

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

By adamant, history, 4 years ago, In English

Hi everyone!

Let's continue with learning continued fractions. We began with studying the case of finite continued fractions and now it's time to work a bit with an infinite case. It turns out that while rational numbers have unique representation as a finite continued fraction, any irrational number has unique representation as an infinite continued fraction.

Part 1: Introduction
Part 2: Properties and interpretation

Full text and comments »

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

By adamant, 4 years ago, In English

Hi everyone!

After writing this article I've decided to write another one being comprehensive introduction into continued fractions for competitive programmers. I'm not really familiar with the topic, so I hope writing this entry will be sufficient way to familiarize myself with it :)

Part 1: Introduction
Part 2: Properties and interpretation

Full text and comments »

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

By adamant, 4 years ago, In English

Hi everyone!

It's been a while since I posted anything. Today I'd like to talk about problem I from Oleksandr Kulkov Contest 2. Well, on some similar problem. Problem goes as follows: There is a rational number $$$x=\frac{p}{q}$$$, and you know that $$$1 \leq p, q \leq C$$$. You want to recover $$$p$$$ and $$$q$$$ but you only know number $$$r$$$ such that $$$r \equiv pq^{-1} \pmod{m}$$$ where $$$m > C^2$$$. In original problem $$$m$$$ was not fixed, instead you were allowed to query remainders $$$r_1,\dots,r_k$$$ of $$$x$$$ modulo several numbers $$$m_1,\dots,m_k$$$, which implied Chinese remainder theorem.

Full text and comments »

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

By adamant, history, 4 years ago, In English

Hi everyone!

This summer I gave another contest in summer Petrozavodsk programming camp and (although a bit lately) I want to share it with codeforces community by adding it to codeforces gym: 2018-2019 Summer Petrozavodsk Camp, Oleksandr Kulkov Contest 2. To make it more fun I scheduled it on Sunday, 5 january, 12:00 (UTC+3). Feel free to participate during scheduled time or, well, whenever you're up to. Good luck and have fun :)

Problems might be discussed here afterwards, I even may write some editorials for particular problems (per request, as I don't have them prepared beforehand this time).

UPD: 17h reminder before the start of the contest

UPD2: It wasn't an easy task to do, but I managed to add ghost participants to the contest! Enjoy!

Full text and comments »

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

By adamant, history, 5 years ago, In English

Hi there!

During preparation of Oleksandr Kulkov Contest 1 I started writing some template for polynomial algebra (because 3 problems in contest in one or another way required some polynomial operations). And with great pleasure I'd like to report that it resulted in this article on cp-algorithms.com (English translation for e-maxx) and this mini-library containing all mentioned operations and algorithms (except for Half-GCD algorithm). I won't say the code is super-optimized, but at least it's public, provides some baseline and is open for contribution if anyone would like to enhance it!

Article also provides some algorithms I didn't mention before. Namely:

  • Interpolation: Now the described algorithm is and not as it was before.
  • Resultant: Given polynomials A(x) and B(x) compute product of Ai) across all μi being roots of B(x).
  • Half-GCD: How to compute GCD and resultants in (just key ideas).

Feel free to read the article to know more and/or use provided code :)

tl;dr. article on operations with polynomials and implementation of mentioned algorithms.

Full text and comments »

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

By adamant, history, 5 years ago, In English

Okay, so compare these two submissions: 51053654 and 51053605

The only difference is that first one made via GNU C++17 and the second one via MS C++ 2017. Code is same, but first gets RE 16 and second one gets AC.

WTF, GNU C++??

Full text and comments »

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

By adamant, history, 5 years ago, In English

Hi everyone!

I gave a contest in winter Petrozavodsk programming camp and now I'd like to share it with codeforces by making it a contest in codeforces gym: 2018-2019 Winter Petrozavodsk Camp, Oleksandr Kulkov Contest 1. It was my first experience giving a contest to the camp and I'm pretty much excited about it!

In the camp only 7 out of 11 problems were solved, so there should be something in the contest for everyone. To make the contest more interesting I suggest you to participate in it as live contest on Saturday, 9 March, 12:00 (UTC+3), which may be changed in case of overlap with some other contest or if it's inconvenient for many participants. After this I suggest to gather here and discuss problems (if anyone's going to participate, of course). I will also post editorial which may (or may not) contain some neat stuff.

Uhm, good luck and have fun :)

P.S. It appears you already may see problems if you have coach mode enabled, I'd ask you to not do this unless you're not going to participate in contest!

UPD: Gentle reminder that it's less than 24 hours before the contest and it's hopefully not going to be rescheduled this time.

UPD 2: Thanks everyone for participating in the contest! Here are editorials: link

UPD 3: Google drive link got broken, so I uploaded the editorial to the contest directly.

Full text and comments »

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

By adamant, history, 5 years ago, In English

Hi there!

Consider the following problem: You're given set of n items with weights a1, ..., an. How many ways are there to select k items (order of choosing matters) with total weight of m (let's denote it as bm)? There are two main variants of the problem:

  • You may take any item arbitrary number of times. In this case bm = [xm](xa1 + ... + xan)k.
  • You may take each item exactly once. In this case bm = m![xmyk](1 + yxa1)...(1 + yxan)

First case is quite explicit and allows you to calculate answer in like as .

But what about the second? If you define P(x) = xa1 + ... + xan and Qk(x) = b0 + b1x + b2x2 + ..., you may say for example that Q1(x) = P(x), Q2(x) = P2(x) - P(x2) or Q3(x) = P3(x) - 3P(x)P(x2) + 2P(x3) which allows to calculate Qk(x) for small k quickly. But does anybody know any fast way to calculate Qk(x)? Newton's identities seem to allow something like if I'm not mistaken. Can anybody suggest any faster algorithm?

Full text and comments »

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

By adamant, history, 5 years ago, In English

Hi everyone!

As you may know, I'm an attention whore seeker. For this (well, not only this) reason year and almost a half ago I've created public page on vk.com: Зайчатки разума. Name is some old Russian semi-linguistic meme without adequate English translation, thus I decided to use 'Mindbun' as presumably closest to literal translation as English name. There was announce on codeforces, which didn't get any particularly positive or negative reaction. Or any reaction at all :)

On that page I mostly post maths things interesting to me and information of any similar activities by me on other places (like, here). It serves as some kind of public notebook to me. Why won't I just post stuff on codeforces, as before? Well, my tastes may be very specific and I'm greatly afraid that I will bother community by posting dozens of short posts on topics which only partially relevant to competitive programming and strongly imbalanced (on mentioned page there is like half of content is about polynomials and/or complex numbers). Thus I decided to throw my thoughts on some other channel and leave only 'big' content for codeforces.

And it was pretty successful as for me. VK page has 506 followers currently and I really enjoy making that stuff! You can see compilation of my older posts and newer ones (Russian, sorry!). So now I decided that it's good time for i18n. Thus I'm going to crosspost English versions of original VK public page in special telegram channel. Welcome! Also since I really like to chat with people, I also created Mindbun-related chat for anyone interested in it :)

And to give you some example of what's it like, I'll just provide you first post from the channel :)

P.S. Channel has not any content yet. I'll start by translating some newer posts from VK page, and will post any future entries there. I'd like to translate all the previous stuff, but there's vast of it and I really can't afford it right now, and I feel shy about some of my older posts :(

P.P.S. I would really appreciate your feedback on the following question: how should I inform on updates in Mindbun here? There are several variants I'm considering right now.

  • Post only big stuff on codeforces and keep notes to Mindbun only
  • Make some kind of digest with updates once a... Week? Month? Year? Random moment of time?..
  • Any other formats I haven't considered yet?

Full text and comments »

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

By adamant, history, 5 years ago, In English

Hi everyone! This one will be long and contain a lot of off-topic, prepare yourself (or skip down to solution of mentioned problem)!

Intro

In this blog post I would like to talk about some problem that somehow was on my mind for several years and yet only now I have some more or less complete understanding of how to deal with it. The problem is as follows:

You're given string S and q queries. In each query you have to count amount of distinct substrings of S[l, r].

Full text and comments »

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

By adamant, history, 6 years ago, In English

Hi there! Imagine you're participating in codechef long challenge and you see a problem from chemthan asking you to calculate some sums of powers like 1p + 2p + ... + np for all p from 0 to k. You immediately understand what's going on here and take Faulhaber's formula from your wide pants, do ya? Just take a look at it!

Beautiful, right? Wrong! This formula is dumb and it's hard to understand and remember! Why would you ever think about Bernoulli's number on any contest which lasts less than a week? And what the hell are those Bernoulli numbers?! Here is what you should do:

Let Sp = 1p + ... + np. Consider its exponential generating function (EGF):

Now you can simply find S0, ..., Sk by finding inverse series for and multiplying it with . Enjoy your power sums without Stirling and/or Bernoulli numbers!

Exercise: Solve this problem in .

P.S. Yes, you basically perform the same calculations as in Faulhaber's formula, but now you hopefully understand what you're doing.

Full text and comments »

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

By adamant, history, 6 years ago, In English

Hi everyone!

Perhaps you heard about github project on translating e-maxx. The thing is that project is actually more than just translating it. You see, there are bunch of algorithms and approaches which either do not have proper elaborations or have but they're written in some weird uncommon languages like, you know, russian or chinese. And there are some sites which just don't fit for this purpose for some reasons.

Years ago when I started doing competitive programming e-maxx.ru was the main resource to learn things. Things changed a bit now. E-maxx is Russian only and it wasn't updated for years. And now I hope that e-maxx-eng will manage to fill this gap of common resource for everyone to learn new things and keep updated on recent competitive programming tricks and new algorithms.

So I encourage everyone to collaborate in making e-maxx-eng comprehensive guide into competitive programming, and not only on hacktoberfests :). And to begin with I would like to share with you my article on convex hull trick and Li Chao tree I wrote for this resource. Enjoy!

If you were too lazy to read it thoroughly: There is a link to CHT and Li Chao tree article just above this sentence!

Full text and comments »

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