Motivation Humanity's research into the $\mathbf{P}$ versus $\mathbf{NP}$ problem has never ceased. Unfortunately, the deeper we investigate the problem, the more formidable it appears. Along the way, complexity theorists have discovered three major barriers to proving strong complexity lower bounds: relativization, algebrization, and natural proofs. These barriers reveal fundamental limitations of several broad classes of proof techniques that have been successful elsewhere in complexity theory. The fail…
Problem Statement There 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 and B so that all of the following conditions are satisfied: Every cell belongs to exactly one of regions A and B. Both region…
Second-order Linear Differential Homogeneous Equations Consider operator $$
L = D^2 + pD + q \tag*{}
$$ where $D$ is differential operator For 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 particular, if $r_1, r_2 \in \mathbb C$, let $r_1 = \alpha + i\beta$ and $r_2 = \alpha - i\beta$. Through Euler…
Convolution Consider 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 Matrix We 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} & \cdots & \cdots & t_{-(n - 1)} \\
t_1 & t_0 & t_{-1} & \ddots & & \vdots \\
t_2 & t_1 & \ddots & \ddots & \ddots & \vdots \\
\vdots & \ddots & \ddots & \ddots & t_{-1} & t_{-2} \\
\vdots & & \ddots & t_1 & t_0 & t_{-1} \\
t_{n - 1} & \cdots & \cdots & t_2 & t_1 & t_0
\end{bmatrix}, \tag*{}
$$…
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 a $0 \cdot \infty$ model? How can we irresponsibly assert this $0 \cdot \infty = 0$? Partition We call two inter…
Statement If 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 Proof We may assume without loss of generality that $\mathcal S \cap \mathcal T = \varnothing$. We represent the mappings as a bipartite graph as follows: Elements of $\mathcal S$ are taken as left vertices, and ele…
Statement Each of the six boxes $B_1$, $B_2$, $B_3$, $B_4$, $B_5$, $B_6$ initially contains one coin. The following operations are allowed Type 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}$ and $B_{k + 2}$. Determine if there exists a finite sequence of operations of the allowed types, such that th…
Overview Dantzig'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)$ are the decision variables. $\mathbf b = \left(b_1, \ldots, b_m\right)$ are the right-hand side values. $A$…
Problem Statement Alice 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 $c_{i,j}$ dollars. Alice can put any number of different types of locks on each chest (possibly, zero). Then,…
Problem Statement You 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 number for each scenario. Editorial Notice that the answer is at most $31$ and the number of operation required f…
