Use this link in case of broken PDF: https://hackmd.io/@spyofgame/AISearch image 1. Descriptions image Actually, I did implement 27 different search algorithms. I remove most of them to ensure the PDF is no more than 15Mb Other than 7 required algorithms, I only keep Dijkstra to ensure correctness.

$$ \begin{array}{c} \Huge \texttt{Applied Mathematics and Statistics}\ \Huge \texttt{for Information Technology}\ \Huge \textbf{Quiz Week 2}\ \end{array} $$ $$ \begin{array}{c}

$\Huge \text{Table Of Content}$ [TOC] Real Score: Problem 1: $1.5 = 25%$ Problem 2: $4.9 = 70%$ Problem 3: $0.0 = 0%$ [Rank] Sum $= [101]$ $6.4$

link Tags: Trial Division, Sundaram Sieve, Erastothenes Sieve, Atkin Sieve, Wheel Sieve, Bitwise Sieve, Segment Bitwise Sieve, Segment Sieve, Sieve 1. Brute-forces Với mọi số nguyên $x$ trong đoạn $[0, n]$. Ta đếm số ước $d$ của $x$ trong đoạn $[0, x]$. Nếu $x$ có đúng $2$ ước thì $x$ là số nguyên tố Time: $O(1 + 2 + \dots + n) = O(n^2)$ Space: $O(n)$ Algo: Brute-forces Sieve

tags: Hash, Matrix Hash, Multi Hash, Multi Matrix Hash, DP, Template, Partial Sum, DP link Tags: Matrix Hash, Multi Matrix Hash, Partial Sum, DP Mục tiêu Phiên bản static offline Offset $1, 1$ - Ô đầu ở $(1, 1)$ kết thúc $(n, m)$

https://oj.vnoi.info/problem/bedao_m06_hard Tags: Math, Binary Search, Data Structure, Online Query Giải truy vấn 1: Nếu truy vấn 1 không đủ nhanh thì TLE trước cả truy vấn 2 nên mình cần tìm một cấu trúc dữ liệu đủ nhanh Ta có thể sử dụng các cấu trúc dữ liệu cây để tìm, chèn, xóa trong $O(\log\ n)$ hoặc nhanh hơn, ví dụ như trong C++ có std::set, std::map Giải truy vấn 2:

https://oj.vnoi.info/problem/bedao_m06_yugioh Hướng dẫn Để kiểm tra một số bất kì có phải là số nguyên tố không quá $X$ hay không, ta chỉ cần sàng các số nguyên tố trong đoạn $[1, X]$ và có thể kiểm tra trong $O(1)$ Yêu cầu đề bài là chuyển các số $a_i$ nguyên tố $\leq X$ lại gần nhau $\Rightarrow$ Có thể coi mảng $a[]$ như $n$ số nhị phân, với giá trị $1$ khi $a_i$ nguyên tố $\leq X$ và giá trị $0$ với các số còn lại. $\Rightarrow$ Gọi $k$ là số số $1$ trong dãy. Lúc này ta chỉ cần đưa $k$ số $1$ kề nhau với ít lần swap nhất

EDITORIAL_TEMPLATE === [Link](URL) ----- ### Hướng dẫn ----- ### Độ phức tạp ----- ### Code > **Time:** $O(n)$ > **Space:** $O(n)$ > **Algo:** ```cpp= ```

https://oj.vnoi.info/problem/olp_ct20_route Credit: @darkkcyan Hướng dẫn tính giá trị Ta định nghĩa $P$ là giá trị tích các số trên đường đi hiện tại $V$ là số số $0$ ở cuối $P$ $c_x$ là số thừa số $x$ trong $P$

https://oj.vnoi.info/problem/fc130_merge Contributor: @jalsol @volongskl2003 Hướng dẫn Xét các tập: $A = {1, 2, \dots, n}$ $B = {n + 1, n + 2, \dots, n + m}$ $C = {n + m + 1, n + m + 2, \dots, n + m + k}$

https://oj.vnoi.info/problem/fc130_suraj Hướng dẫn Vì chi phí càng tăng khi càng mở nhiều tab cho một cửa sổ, nên ta ưu tiên mở các cửa sổ có ít tab nhất trước. Để đẩy nhanh tiến độ, ta có thể tìm số $x$ lớn nhất mà $v = k \times \frac{x(x+1)}{2} \leq m$ sau đó ta mở $k$ cửa sổ với $x$ tab đầu tiên. Phần thừa còn lại ta sẽ dành để mở được $\lfloor \frac{m - v}{x + 1} \rfloor$ cửa sổ tại tab thứ $x + 1$ Dễ thấy $f(x) = k \times \frac{x(x+1)}{2}$ là hàm tăng đơn điệu nên ta có thể chặt nhị phân tìm $x$ lớn nhất thỏa $f(x) \leq m$

https://oj.vnoi.info/problem/fc130_place Gợi ý: Khoảng cách lớn nhất giữa $2$ số nguyên tố liên tiếp không quá $10^9$ là $g = 282$ Hướng dẫn Xét tập $S = {2, 3, \dots, B}$ và $T = {B + 1, B + 2, \dots, A}$$ Mình cần tìm số $x \in T$ lớn nhất sao cho $\nexists\ d \in S$ mà $d\ |\ x$

Link Hướng dẫn Vào thời điểm $x$, người thứ $k$ làm được $\left \lfloor \frac{x}{T_k} \right \rfloor$ hồ sơ. Nên ta có tổng cộng $f(x) = \overset{n}{\underset{k = 1}{\Large \Sigma}} \left \lfloor \frac{x}{T_k} \right \rfloor$ hồ sơ được làm Nhiệm vụ của ta là tìm số $x$ nhỏ nhất thỏa $f(x) \geq m$ Nhận thấy vì $T_k > 0\ \forall\ k = 1 \dots n$ nên ta có $f(x) \leq f(x + 1)\ \forall\ x \geq 0$. Hay dãy $f(x)$ tăng đơn điệu. Nếu $f(p) \geq m$ thì $f(q) \geq m\ \forall\ q \geq p$

Link Contributer: mr_sg Xét bài toán con Xét một dãy $X =$ "<<<...<<<>>>...>>>" Gọi $L$ là số lần xuất hiện "<" Gọi $R$ là số lần xuất hiện ">"

Link Hướng dẫn Xét tại vị trí $i$, gọi mực nước dâng tới $b_i$ Nếu như không tồn tại $j < i$ để $a_j > a_i$ hoặc không tồn tại $k > i$ để $a_k > a_i$, thì nước sẽ không đọng lại, nên $b_i$ Ngược lại mực nước không được dâng quá $L = max(a_1, a_2, \dots, a_i)$ và cũng không quá $R = max(a_i, \dots, a_{n-1}, a_n)$ $a_i$ nên $b_i = min(L, R)$ Xét tại vị trí $i$, mình nâng cột lên vị trí $X$, hỏi phần nước còn lại là bao nhiêu

https://oj.vnoi.info/problem/olp_kc20_fraction Co-author: Nguyễn Nam Bài toán con Xét bài toán kiểm tra xem phân số $\frac{X}{Y}$ có phải là số thập phân tuần hoàn vô hạn hay không Xét $\frac{A}{B} = \frac{X \div gcd(X, Y)}{Y \div gcd(X, Y)}$ là phân số tối giản của $\frac{X}{Y}$.

Link Hướng dẫn Tổng số hiệu của đàn bò ban đầu: $T = 1 + 2 + \dots + (n-1) + n$ $T = n + (n - 1) + \dots + 2 + 1$ $\Leftrightarrow 2T = (1 + n) + (2 + (n-1)) + \dots + ((n - 1) + 2) + (n + 1) = (n + 1) \times n$

URL Hướng dẫn Với mỗi vị trí $[L]$ tìm vị trí $[R]$ nhỏ nhất thỏa mãn số lượng kí tự 'A', 'V' và 'C' trong đoạn $[L, R]$ đều không ít hơn $k$ Vì lúc này $[L, R]$ là một đoạn cố định tương tự như mình xóa $[1, L)$ và $(R, N]$ mà không mất chi phí, nên giờ mình sẽ xóa phần bên trong, sao cho số lượng 'A', 'V' và 'C' đều có đúng $k$. Gọi $C(L, R, X)$ là số lượng kí tự có giá trị $X$ trên đoạn $[L, R]$. Chi phí sửa đổi của đoạn $[L, R]$ là $(C(L, R,$ 'A' $) + C(L, R,$ 'C'$) + C(L, R,$ 'V'$) - 3k)$. Vậy bài này có độ phức tạp là $O(n)$ thời gian và bộ nhớ

URL Hướng dẫn Gọi hàm $f(l, r)$ là chi phí để sơn một đoạn $[l, r]$ Gọi hàm $[x = y]$ trả về $1$ khi $x = y$ và trả về $0$ khi $x \neq y$ Ta có $f(0, n) = \overset{n}{\underset{x = 0}{\Large \Sigma}} max\Large(\normalsize k\ \ \Large|\ \ \normalsize \frac{x}{2^k} \in Z \wedge\ \normalsize \frac{x}{2^{k+1}} \notin Z \Large) \normalsize = \overset{n}{\underset{x = 0}{\Large \Sigma}} \overset{log_2(x)}{\underset{k = 1}{\Large \Sigma}} \Large[\normalsize \frac{x}{2^k} \in \mathbb{Z} \Large] \normalsize = \overset{log_2(n)}{\underset{k = 1}{\Large \Sigma}} \overset{n}{\underset{x = 0}{\Large \Sigma}} \Large[\normalsize x = 2^k\Large] \normalsize = \overset{log_2(n)}{\underset{k = 1}{\Large \Sigma}} \Large \lfloor \normalsize \frac{n}{2^k} \Large \rfloor$ Ta có kết quả của bài toán $f(l, r) = f(0, r) - f(0, l - 1)$

Link Hướng dẫn Có $b_{1,j} = a_1 ⊕ a_j$ Mà $b_{i,j}$ $= a_i ⊕ a_j$ $= a_i ⊕ a_j ⊕ 0$