RBTREE'S HOME

征服世界的将是这样一些人：开始的时候，他们试图找到梦想中的乐园，最终，当他们无法找到时，就亲自创造了它。

ARC 219 E Equal Distribution

0 comments Problem-solving notes Puzzle
Problem StatementThere is a shortcake in the shape of a $2H \times 2W$ grid. The cell at the $i$-th row from the top and the $j$-th column from the left is denoted as cell $(i, j)$ . Cell $(i, j)$ has one strawberry on it if $S_{i, j} =$ o, and nothing if $S_{i, j} =$ x. It is guaranteed that exactly $2HW$ cells have strawberries.Divide each cell of this shortcake into regions A an...

Second-order Differential Equation

0 comments Study Notes Mathematics
Second-order Linear Differential Homogeneous EquationsConsider operator$$ L = D^2 + pD + q \tag*{} $$where $D$ is differential operatorFor the case where $P(x)$ and $Q(x)$ are constant functions:Let $r_1$ and $r_2$ denote the two roots of the polynomial $\lambda^2 + p\lambda + q$.Case 1: $r_1 \neq r_2$It is evident that$$ \ker(L) = \operatorname{span}\{e^{r_1x}, e^{r_2x}\}. \tag*{} $$In particu...

Discrete Fourier Transform and Fast Fourier Transform

0 comments Study Notes Polynomial FFT
ConvolutionConsider two polynomials $F(x) = \sum_kf_kx^k$, $G(x) = \sum_kg_kx^k$ and their product $H(x) = (F \cdot G)(x) = \sum_kh_kx^k$, where$$ h_k = \sum_{i + j = k}f_ig_j. \tag*{} $$Toeplitz MatrixWe can describe convolution using the language of linear algebra.Embed the Toeplitz matrix into a circulant matrix $C$:$$ C_{ij} = t_{i - j} = \begin{bmatrix} t_0 & t_{-1} & t_{-2} & ...

Riemann Integral

0 comments Study Notes Mathematics
When I was taught integration, my teacher told me that when we divide the area into strips with sufficiently small widths, the error will decrease to zero. However, there was still some confusion in my mind: when the widths of each strip decrease to infinitesimally small, the total area will approach the actual area under the original function, but since we have infinitely many strips, isn't it...

Schröder Bernstein Theorem

0 comments Study Notes Mathematics Set Theory
StatementIf there exists an injective function $f: \mathcal S \to \mathcal T$ and an injective function $g: \mathcal T \to \mathcal S$, then there exists a bijective function $h: \mathcal S \to \mathcal T$. In other words, $\mathcal S$ and $\mathcal T$ have the same cardinality.Gyula Kőnig's ProofWe may assume without loss of generality that $\mathcal S \cap \mathcal T = \varnothing$.We represe...

IMO 2010 P5

0 comments Problem-solving notes Mathematics
StatementEach of the six boxes $B_1$, $B_2$, $B_3$, $B_4$, $B_5$, $B_6$ initially contains one coin. The following operations are allowedType 1) Choose a non-empty box $B_j$, $1 \leq j \leq 5$ remove one coin from $B_j$ and add two coins to $B_{j + 1}$;Type 2) Choose a non-empty box $B_k$, $1 \leq k \leq 4$, remove one coin from $B_k$ and swap the contents (maybe empty) of the boxes $B_{k + 1}$...

Dantzig's Simplex Method

0 comments Study Notes Mathematics Matrix Linear Programming
OverviewDantzig's simplex method is used to solve the following linear programming problem.Minimize $z = \mathbf c^{\mathrm T} \mathbf x$Subject to $A\mathbf x \leq \mathbf b$ and $\mathbf x \geq 0$where $\mathbf c = \left(c_1, \ldots, c_n\right)$ are the coefficients of the objective function.$\left(\cdot\right)^{\mathrm T}$ is the matrix transpose.$\mathbf x = \left(x_1, \ldots, x_n\right)$ a...

CF1519F Chests and Keys

0 comments Problem-solving notes Dynamic Programming Flow
Problem StatementAlice and Bob play a game. Alice has got $n$ treasure chests (the $i$-th of which contains $a_i$ coins) and $m$ keys (the $j$-th of which she can sell Bob for $b_j$ coins).Firstly, Alice puts some locks on the chests. There are $m$ types of locks, the locks of the $j$-th type can only be opened with the $j$-th key. To put a lock of type $j$ on the $i$-th chest, Alice has to pay...

CF2147E Maximum OR Popcount

0 comments Problem-solving notes Greedy
Problem StatementYou are given an array of $n$ non-negative integers.You want to answer given $q$ independent scenarios. In the $i$-th scenario, you are allowed to perform the following operation at most $b_i$ times:Choose an element of the array and increase it by $1$.Your goal is to maximize the number of bits that are equal to $1$ in the bitwise OR of all numbers in the array. Find this numb...

Boids Algorithm

0 comments Study Notes No tags
OverviewLet us watch a demo first. Go to https://boids.rbtr.ee/ to see further.As you can see, the Boids algorithm is a method to simulate the movements of social creatures.AlgorithmThe Boids algorithm is quite simple.Each individual only needs to follow three rules.Separation. To avoid collision, a force is applied between individuals that are too close. The closer they are, the stronger the...