The notes

Problem statement Prove that any $\overrightarrow{v} \in \mathbb{R}^3$ can be approximated to arbitrary precision by an integral linear combination of unit vectors from the origin to the vertices of a regular icosahedron. Idea icosahedron with denotation $S$ = Integral linear combination of $\{O’A, O’B, O’C, O’D, O’E\}$ is dense on $\mathbb{R}^2$ $\{ \{n\alpha\} = n\alpha - \lfloor n\alpha \rfloor \}, n\in\mathbb{N}$ is dense on $[0,1)$ $\{ m\alpha + n\beta \}, m,n \in \mathbb{N},\dfrac{a}{b}\in \mathbb{R}\setminus\mathbb{Q}$ is dense on $\mathbb{R}$...

Problem Statement Given a graph G with each vertex assigned with a binary state on/off. Each move consists of choosing a vertex, then change the state of itself and all of its neighbor(s). Prove that from the all-off starting position, it is possible to reach the all-on position. Idea Let $n$ be the number of vertex in $G$. Let $A$ be the adjacent matrix of $G$: $$ A_{ij} = \begin{cases} 1 &\text{if } i=j \text{ or }i\text{ and }j \text{ are adjacent in G} \\ 0 &\text{otherwise } \end{cases} $$...

Problem Statement Let $x_1,x_2,…,x_m$ be real numbers such that the set $$ A = \lbrace \sum_{i=1}^m cos(n\pi x_i) | n \in \mathbb{N} \rbrace $$ is finite. Prove that all the $x_i$ are rational numbers. Idea (borrow from the proof that $\lbrace n\alpha \rbrace = n\alpha - \lfloor n\alpha \rfloor$ is dense on $[0,1]$) Let $k$ be an integer. Consider the tuple $$ (\lbrace \dfrac{t x_1}{2} \rbrace,\lbrace \dfrac{t x_2}{2} \rbrace,…,\lbrace \dfrac{t x_m}{2} \rbrace)$$...

Problem Statement Given a permutation p of [1..n], find a sequence to sort the permutation using two stacks, with possibly interleaving push/pop operations or determine it’s impossible. Constraint: n ~ 2e5 Example: [5 2 4 1 6 3] Sequence: push 1 [5] [] push 2 [5] [2] push 1 [5 4] [2] push 1 [5 4 1] [2] pop 1 [5 4] [2] pop 2 [5 4] [] push 2 [5 4] [6] ....

Problem Statement Given n integers a[1..n]. Calculate sum of t-th powers, $\sum_{i=1}^{n}a_i^{t}$, modulo 998244353 for t in [1..k] Constraint: n ~ 1e5, k ~ 1e5 Hint According to Wikipedia, we have the generating function for sum of power: $$\sum_{k=1}^{\infty} (-1)^{k-1}p_k \dfrac{t^k}{k} = \ln (1+e_1 t + e_2 t^2 + e_3 t^3 + …)$$ where $p_k$ is the t-th power sum: $$ p_k = \sum_{i=1}^n x_i^k $$ and $e_k$ is the elementary symmetric polynomial (the sum of all distinct products of k distinct variables):...