# Lời giải chuỗi contest thi thử HSG 2025 - Câu lạc bộ SQRT

[TOC]

## Ngày thi thứ nhất

### Câu 1 - Xếp khối gỗ (7 điểm)

> Tác giả: Nguyễn Hữu Nhật Quang
Solution: Mai Ngọc Phú

Nhận xét: thứ tự xếp các khối gỗ không quan trọng $\rightarrow$ ta chỉ quan tâm có $x \le n$ khối gỗ độ cao $a$ và $y \le m$ khối gỗ độ cao $b$.

Đặt $a' = \frac{a}{gcd (a, b)}, b'= \frac{b}{gcd (a, b)}$. Dễ thấy $a \times b' = b \times a'$. Do đó chúng ta có thể thay $a'$ khối gỗ độ cao $b$ thành $b'$ khối gỗ độ cao $a$.

Chiều cao một cột gỗ có thể tính theo công thức:
$$h = ax \times by $$
Với $0 \le x \le n$ và $0 \le y \le m$ dễ thấy được số lượng $h$ sinh ra là $(m+1)\times(n+1)$

Tuy nhiên ta cần tìm số giá trị $h$ khác nhau nên phải trừ đi số lượng $h$ trùng nhau

Ta có: $$h = ax \times by$$$$\leftrightarrow h=ax\times by-k\times a\times b' +k \times a'\times b$$$$\leftrightarrow h=a(x-kb')+b(y+ka')$$

- $k\in N$ , $0\le x-kb'$ , $y+ka'\le m$

Như vậy với $1$ giá trị $h$ có nghiệm $(x,y)$ với $n-b'+1 \le x \le n$ hoặc $0 \le y \le a'-1$ sẽ luôn có ít nhất một nghiệm $(x,y)$ với $0 \le x \le n-b'$ và $a'+1 \le y \le m$ $($ nếu $0 \le n-b'$ và $a'+1\le m$$)$

Suy ra số lượng $h$ trùng nhau là: $max((n-b'+1),0)\times max((m-a'+1),0)$

Kết quả cần tìm là: $(m+1)\times(n+1)-max((n-b'+1),0)\times max((m-a'+1),0) -1$
$($trừ thêm $1$ vì $x$, $y$ không đồng thời bằng $0)$

### Câu 2 - Vận chuyển gỗ (7 điểm)

> Tác giả: Nguyễn Hữu Nhật Quang

Dễ thấy, để vận chuyển toàn bộ gỗ từ ô $(i, j)$ sang ô $(u, v)$ thì tổng chi phí sẽ là $a_{ij} \times (|i - u| + |j - v|)$. Ta có thể tách thành $a_{ij} \times |i - u| + a_{ij} \times |j - v|$.

Đặt $R_{ij} = a_{ij} \times |i - u|, C_{ij} = a_{ij} \times |j - v|$. Hiển nhiên ta có:

$R_{i1} + R_{i2} + ... + R_{im} = (a_{i1} + a_{i2} + ... + a_{im}) \times |i - u|$ $(*)$

Tương tự với $C$.

Gọi $SR_i$ là tổng các số trên hàng $i$ và $SC_i$ là tổng các số trên cột $i$. Ta có thể viết lại $(*)$ thành:

$\sum^{j \le m}_{j = 1} R_{ij} = R_{i1} + R_{i2} + ... + R_{im} = SR_i \times |i - u|$

Tương tự:

$\sum^{i \le m}_{i = 1} C_{ij} = C_{1j} + C_{2j} + ... + C_{nj} = SC_j \times |j - v|$

Vậy tổng chi phí vận chuyển toàn bộ gỗ từ tất cả các ô đến một ô $(u, v)$ có thể được viết lại thành:

$\sum^{i \le n}_{i = 1} \sum^{j \le m}_{j = 1} R_{ij} + C_{ij} = \sum^{i \le n}_{i = 1} (\sum^{j \le m}_{j = 1} R_{ij}) + \sum^{j \le m}_{j = 1} (\sum^{i \le n}_{i = 1} C_{ij})$

$= \sum^{i \le n}_{i = 1} SR_i \times |i - u| + \sum^{j \le m}_{j = 1} SC_i \times |j - v|$ $(**)$

Chúng ta có thể dễ dàng tính được hai mảng $SR$ và $SC$. Nhận thấy rằng hai số hạng trong $(**)$ không liên quan gì đến nhau, ta có thể tách chúng ra để tính riêng.

Đặt $A_u = \sum^{i \le n}_{i = 1} SR_i \times |i - u|$. Bây giờ ta cần tính $A_{u + 1}$ từ $A_u$. Nhận thấy rằng, với $i \le u$, khi chuyển từ $A_u$ sang $A_{u + 1}$ thì tổng chi phí tăng lên $SR_i$ (có thể hình dung như việc thay vì bạn chuyển các khối gỗ đến hàng $i$ thì bạn phải chuyển chúng đến hàng $i + 1$). Ngược lại, với $i > u$ thì tổng chi phí sẽ giảm đi $SR_i$.

Từ đây, ta viết được công thức tính $A_{u + 1}$ từ $A_u$ như sau:

$A_{u + 1} = A_u + (SR_1 + SR_2 + ... + SR_u) - (SR_{u + 1} - SR_{u + 2} + ... + SR_n)$

Đến đây, ta có thể dễ dàng tính được mọi $A_i$ sử dụng mảng tổng tiền tố. Tương tự với mảng $SC$ và chi phí vận chuyển cho các cột.

Độ phức tạp: $O(mn)$.

### Câu 3 - Đếm phép nhân (6 điểm)

> Tác giả: Nguyễn Hữu Nhật Quang

Gọi $f(i, j)$ là số cách để chọn các số từ $a_1$ đến $a_i$ tạo ra tích là $j$ với $j \le \sqrt{x}$.

Gọi $g(i, k)$ là tổng số cách để chọn các số từ $a_1$ đến $a_i$ tạo ra tích là $j$ với $j > \sqrt{x}$ mà $\lfloor \frac {x}{j} \rfloor = k$.

Ban đầu, $f(0, 1) = 0$. Xét phần tử $a_i$. Thao tác chuyển nhãn được thực hiện như sau:
- Với mỗi $j \times a_i \le \sqrt{x}$: $f(i, j \times a_i)$ được cộng thêm $f(i - 1, j)$.
- Với mỗi $j \le \sqrt{x}$ và $j \times a_i > \sqrt{x}$: $g(i, \lfloor \frac {x}{j \times a_i} \rfloor)$ được cộng thêm $f(i - 1, j)$.
- Với mỗi $k < \sqrt{x}$ và $k \ge a_i$: $g(i, \lfloor \frac {k}{a_i} \rfloor)$ được cộng thêm $g(i - 1, k)$.

Độ phức tạp: $O (n \times \sqrt{x})$.

## Ngày thi thứ hai

### Câu 1 - Pickleball (4 điểm)

> Tác giả: Đặng Huy Hậu

> Trong lúc thi mình thấy các bạn có hai cách làm, trong đó cách 1 là cách làm TLE và cách 2 là cách làm chuẩn, mình xin trình bày cả hai cách trên:

**Cách 1 (TLE):** Đẩy vị trí của Alice/Bob sang trái/phải liên tục đến khi thỏa mãn điều kiện lượt thứ $i$. Mình không thể ước lượng được độ phức tạp cho cách làm này nhưng chắc chắn cách làm này không đủ tối ưu.

**Cách 2:** Sử dụng công thức toán: Giả sử gọi $k=(r-l)\ mod\ i$ thì:
- Nếu $k=0$, tức là chênh lệch vị trí đã chia hết cho $i$ thì không cần đẩy nữa.
- Nếu $k\ne 0$ thì cần đẩy Alice/Bob sang trái/phải $i-k$ đơn vị.

Tổng quát hóa, trong lượt thứ $i$, ta đẩy Alice/Bob sang trái/phải $[i-(r-l)\ mod\ i]\ mod\ i$ đơn vị.

Độ phức tạp cho cách làm này là $O(k)$ với mỗi trường hợp thử nghiệm và đủ để qua bài này.

> *Fun fact: Mình đã thử để $k\le 10^6$ nhưng do cài đặt dở nên bị TLE luôn, thực tế mình có thể tối ưu thời gian hơn nhưng mình đã quyết định giảm $k$ xuống $10^5$.*

### Câu 2 - Lại là một bài toán về trị tuyệt đối (4 điểm)

> Tác giả: Đặng Huy Hậu

#### Subtask 1: $n\le 5000,a_i\le 5000$

Nhận xét: Các vị trí $x$ tối ưu có thể chọn luôn nằm trong đoạn $[min(a),max(a)]$.

Từ nhận xét trên, và vì giới hạn của subtask 1 đủ nhỏ nên ta có thể thử nghiệm cày trâu tất cả vị trí $x$ trong đoạn, mỗi lần thực hiện trong $O(n)$. Độ phức tạp: $O(n\times (max(a)-min(a)))$.

Lưu ý 1: Một cách làm tối ưu hơn để tìm $S$ với giá trị $x$ tương ứng là sắp xếp lại dãy $a$. Khi đó:
- Giá trị $max(|a_i-x|)=max(|a_1-x|,|a_n-x|)$.
- Giá trị $min(|a_i-x|)=min(|a_{l-1}-x|,|a_l-x|)$ với $l$ là vị trí đầu tiên thỏa mãn $a_l\ge x$ (vị trí này có thể tìm được bằng cú pháp `lower_bound` trong `C++` hoặc sử dụng chặt nhị phân, cả hai đều có độ phức tạp $O(log(n))$).

Như vậy ta có thể giảm độ phức tạp thuật toán về $O(log(n)\times (max(a)-min(a)))$.

Lưu ý 2: Ta có thể cải tiến cách làm này hơn nữa bằng cách sử dụng hai con trỏ. Nhận xét là vị trí $l$ được định nghĩa ở trên sẽ luôn tăng dần khi $x$ tăng dần. Vì thế ta không cần chặt nhị phân mà có thể tạo con trỏ $l$ để dịch chuyển sang phải liên tục đến khi thỏa mãn.

Độ phức tạp giờ chỉ còn $O(max(a)-min(a))$.

*Mình không nghĩ ra được trò này trước ngày thi nên không chế thêm subtask, đáng lẽ sẽ có nhiều subtask hơn.*

#### Subtask 2: Không có giới hạn gì thêm

Không mất tính tổng quát, giả sử dãy $a$ đã được sắp xếp theo thứ tự tăng dần.

Xét giá trị $A=max(|a_i-x|)$, ta thấy giá trị $A$ luôn giảm dần (nghịch biến) trong đoạn $[a_1,\lfloor\frac{a_1+a_n}2\rfloor]$ và luôn tăng dần (đồng biến) trong đoạn $[\lceil\frac{a_1+a_n}2\rceil,a_n]$. Về đoạn nghịch biến, khi tăng $x$ lên $1$ đơn vị thì $A$ cũng giảm $1$ đơn vị. Về đoạn đồng biến, khi tăng $x$ lên $1$ đơn vị thì $A$ cũng tăng $1$ đơn vị.

Xét giá trị $B=min(|a_i-x|)$, ta thấy khi tăng $x$ lên một đơn vị thì giá trị mới $B'$ sẽ tăng/giảm không quá $1$ đơn vị. Nói cách khác, $|B'-B|\le 1$.

Từ hai nhận xét trên, ta có thể kết luận như sau:
- Về đoạn $[a_1,\lfloor\frac{a_1+a_n}2\rfloor]$, ta có thể chứng minh giá trị nhỏ nhất của $S=A-B$ đạt được khi $x=\lfloor\frac{a_1+a_n}2\rfloor$. Giả sử ta giảm $x$ xuống $1$ đơn vị thì $A$ tăng $1$ đơn vị, để giá trị $S$ mới giảm xuống thì $B$ cần tăng lên ít nhất $2$ đơn vị, mà giá trị mới $B'$ luôn thỏa mãn $|B'-B|\le 1$ nên điều đó không bao giờ xảy ra.
- Lập luận tương tự, ta chứng minh được với đoạn $[\lceil\frac{a_1+a_n}2\rceil,a_n]$, giá trị lớn nhất của $S$ đạt được khi $x=\lceil\frac{a_1+a_n}2\rceil$.

Như vậy, ta chỉ cần sắp xếp lại dãy và xét hai giá trị $x$ là $\lfloor\frac{a_1+a_n}2\rfloor$ và $\lceil\frac{a_1+a_n}2\rceil$ trong $O(n)$ hoặc $O(log(n))$.

Độ phức tạp: $O(n\times log(n))$ do cần sắp xếp lại dãy $a$.

*Fun fact: Bài này nếu sử dụng chặt tam phân sẽ chỉ được 98/100, lý do là hàm này không lồi hoàn toàn (nó vẫn có dạng giảm rồi tăng nhưng không thuộc dạng giảm chặt rồi tăng chặt).*

### Câu 3 - Trò chơi con mực (4 điểm)

> Tác giả: Đặng Huy Hậu

#### Subtask 1: $n\le 20$

Với giới hạn $n$ nhỏ, ta hoàn toàn có thể quay lui xét tất cả phương án chọn cấu hình. Vì có $2^n-1$ cách chọn khác nhau, mỗi phương án có thể xét trong $O(n)$ nên độ phức tạp cho cách làm này là $O(2^n\times n)$.

Chú ý cần đọc kỹ đề để không xét thỏa mãn sai.

#### Subtask 2: $a_i\le 3$

Trong subtask này, chỉ có tối đa $3$ loại cấu hình khác nhau nên mọi phương án chọn cấu hình đều thỏa mãn. Đáp án cho subtask này luôn là $2^n-1$.

#### Subtask 3: Không có giới hạn gì thêm

Khi kiểm tra phương án thỏa mãn hay không, ta xét các cấu hình từ trái sang phải, với mỗi cấu hình đang xét ta chỉ quan tâm thêm $3$ cấu hình ngay trước cấu hình đó. Khi xét cấu hình tiếp theo, ta loại cấu hình trước cùng và thêm cấu hình trước đó vào dãy cần xét. Nên ta có thuật toán quy hoạch động cho bài toán này như sau:

Gọi $dp[i][j][k][l]$ là số phương án chọn thỏa mãn khi xét $i$ cấu hình đầu tiên, và 3 cấu hình cuối cùng trong phương án đó tương ứng với $j,k,l$ (lưu ý có thể có trường hợp $j,k,l=0$ tương ứng với việc không có cấu hình tại vị trí đó). Ban đầu $dp[0][0][0][0]=1$, các giá trị còn lại đều bằng $0$.

Công thức:
- Trường hợp không chọn cấu hình tại vị trí $i$: $dp[i][j][k][l]:+=dp[i-1][j][k][l]$.
- Trường hợp chọn cấu hình $x\ (1\le x\le 4)$ tại vị trí $i$: Nếu $j,k,l,x$ không thỏa mãn điều kiện $j,k,l\ne 0$ và $j,k,l,x$ đôi một phân biệt thì $dp[i][k][l][x]:+=dp[i-1][j][k][l]$.

Độ phức tạp: $O(n)$ (không tính hằng số).

### Câu 4 - Một đời liêm khiết (4 điểm)

Tóm tắt đề bài nếu các bạn không hiểu: Ta cần chọn hai số tự nhiên $x$ và $y$ sao cho với mọi $i$ từ $1$ đến $n$, $a_ix+b_iy\le s_i$ và $x+y$ lớn nhất có thể.

#### Subtask 1,2,3: $n\le 2025; a_i,b_i,s_i\le 6942$

> *Fun fact: Vì mình ~~lười sinh test~~ sinh test khá yếu cho 3 subtask đầu nên đa số các bạn cài được subtask 1 đều qua được gần hết test 3 subtask đầu.*

Nhận xét: Bỏ qua các vị trí $i$ sao cho $a_i=b_i=0$, ta nhận thấy giá trị $x,y$ luôn thỏa mãn $x,y\le max(s_i)$ nên ta chỉ cần xét tối đa $(max(s_i)+1)^2$ cách chọn $x,y$ khác nhau.

##### Subtask 1: $n\le 69;a_i,b_i,s_i\le 420$

Ta có thể xét mọi phương án chọn $x,y$ và kiểm tra trong $O(n)$ mỗi phương án. Độ phức tạp: $O(n\times max(s_i)^2)$.

##### Subtask 2: $n\le 420;a_i,b_i,s_i\le 2025$

Nhận xét: Với giá trị $x$ bất kỳ, nếu giá trị $y$ được chọn thỏa mãn điều kiện thì giá trị $y-1$ cũng thỏa mãn. Vì thế ta có thể chặt nhị phân giá trị $y$ khi xét giá trị $x$ tương ứng.

Độ phức tạp: $O(n\times max(s_i)\times log(max(s_i)))$.

##### Subtask 3: $n\le 2025;a_i,b_i,s_i\le 6942$

Nhận xét: Gọi $f(x)$ là giá trị $y$ lớn nhất thỏa mãn cặp số $x,y$ thỏa mãn điều kiện đề bài thì $f(x)$ luôn giảm dần khi $x$ tăng (nghịch biến). Vì thế ta có thể áp dụng hai con trỏ cho subtask này. Ban đầu đặt $y=max(s_i)$, với mỗi giá trị $x$ cần xét từ $0$ đến $max(s_i)$, ta giảm $y$ liên tục đến khi thỏa mãn điều kiện.

Độ phức tạp: $O(n\times max(s_i))$.

#### Subtask 4: Không có giới hạn gì thêm

~~Ta tìm miền nghiệm của $n$ bất phương trình $a_ix+b_iy\le s_i$ bằng convex hull trick sau đó cày trâu vị trí tương ứng. Độ phức tạp: $O(n\times log(n))$.~~

Nhận xét: Khi tồn tại một phương án chọn $x,y$ sao cho $x+y=k$ và thỏa mãn yêu cầu đề bài thì cũng tồn tại phương án chọn thỏa mãn sao cho $x+y=k-1$. Vì thế ta có thể chặt nhị phân giá trị $k$ cần tìm.

Với một giá trị $mid$ đang xét, giả sử tồn tại $x\ (0\le x\le mid)$ sao cho cặp số $(x,y=mid-x)$ thỏa mãn đề bài. Biến đổi điều kiện đề bài:

$a_ix+b_iy\le s_i$
$\leftrightarrow a_ix+b_i(mid-x)\le s_i$
$\leftrightarrow a_ix+b_imid-b_ix\le s_i$
$\leftrightarrow (a_i-b_i)x\le s_i-b_imid$

Như vậy ta chỉ cần xác định xem có tồn tại giá trị tự nhiên $x$ trong đoạn $[0,mid]$ sao cho thỏa mãn $n$ điều kiện $(a_i-b_i)x\le s_i-b_imid$. Ban đầu ta có đoạn các giá trị $x$ thỏa mãn là đoạn $[l,r]$ với $l=0,r=mid$. Xét 3 trường hợp:

- $a_i-b_i=0$: Khi đó bất phương trình trở thành $s_i-b_imid\ge 0$. Nếu bất phương trình này không thỏa mãn thì giá trị $mid$ không thỏa mãn luôn và kết thúc việc xét các bất phương trình tiếp theo.
- $a_i-b_i>0$: Bất phương trình trở thành $x\le \frac{s_i-b_imid}{a_i-b_i}$. Cập nhật $r:=min(r,\lfloor \frac{s_i-b_imid}{a_i-b_i} \rfloor)$.
- $a_i-b_i<0$: Bất phương trình trở thành $x\ge \frac{s_i-b_imid}{b_i-a_i}$. Cập nhật $l:=max(l,\lceil \frac{s_i-b_imid}{a_i-b_i} \rceil)$.

Cuối cùng, ta chỉ cần kiểm tra nếu $l\le r$ thì tồn tại giá trị $x$ thỏa mãn điều kiện.

Lưu ý cần cài đặt cẩn thận (mình đã cài sai vài lần mới cho được cách cài đặt chuẩn).

Độ phức tạp: $O(n\times log(max(s_i))).$

> *Bài này một số bạn có cách làm chặt tam phân nữa nhưng mình sẽ không đề cập ở đây ~~vì mình không biết làm~~.*

### Câu 5 - Kẻ về nhì (4 điểm)

> Tác giả: Đặng Huy Hậu

#### Subtask 1: $10\le l\le r\le 10^6$

Ta có thể xác định chữ số lớn thứ nhì của $x$ trong $O(log_{10}(x))$.

Lưu ý: Ta không thể cày trâu với tất cả $t$ trường hợp thử nghiệm nên cần cải tiến bằng prefix sum. Ta tạo một mảng lưu tất cả giá trị $f(x)$ với $f(x)$ là chữ số lớn thứ nhì của $x$ sau đó tạo mảng prefix sum của mảng trên. Như vậy mỗi trường hợp thử nghiệm ta có thể lấy kết quả trong $O(1)$.

#### Subtask 2: $t\le 69,r-l\le 10^6$

Vì giá trị $l,r$ có thể rất lớn nên ta không thể dùng prefix sum như subtask 1 được nữa. Với giới hạn của đề bài, ta buộc phải giải quyết mọi trường hợp thử nghiệm trong $O(r-l)$.

Nhận xét: Xét các số chỉ khác nhau ở hàng đơn vị, lấy hai số trong tập đó, gọi là $x_1$ và $x_2\ (x_1<x_2)$. Khi đó $f(x_1)\le f(x_2)$. Như vậy ta có thể áp dụng hai con trỏ cho subtask này.

Ta tính trước giá trị của $f(x)$ với chữ số hàng đơn vị là tối đa, sau đó giảm $x$ dần để xác định $f(x)$ trong $O(1)$ đến khi chữ số hàng đơn vị đạt tối thiểu. Để làm được điều này, ta cần tạo mảng $cnt$ với $cnt_i$ là số lượng chữ số $i$ trong $x$ và một con trỏ $g$ tương ứng với giá trị của $f(x)$. Có thể tạo thêm một giá trị $c$ để đếm số lượng chữ số $\le g$ trong $x$.

Khi giảm $x$, ta chỉ cần cập nhật hai giá trị trong mảng $cnt$ (lưu ý cần cập nhật cả $c$ nếu có), sau đó giảm $g$ dần đến khi xác định được giá trị $f(x)=g$.

Sau khi chữ số đơn vị đạt tối thiểu, ta cập nhật lại từ đầu để xét các giá trị tiếp theo. Nói cách khác, cách làm này giống như việc tính nhanh giá trị $f(x)$ với $10$ giá trị liên tiếp đến khi xét hết đoạn.

Độ phức tạp: $O(r-l)$ với mỗi trường hợp thử nghiệm.

#### Subtask 3: Không có giới hạn gì thêm

Đến đây thì bài toán trở thành một bài dp digit (quy hoạch động chữ số) điển hình.

Ta tạo một mảng $dp[i][j][k]$ là tổng $f(x)$ với mọi phương án thêm $i$ chữ số từ $0$ đến $9$, các chữ số trước đó thỏa mãn hai chữ số lớn nhất là $j$ và $k\ (j\le k)$.

Có 2 cách làm cho bài này với mảng $dp$ trên:
- Cách 1: Xử lý trước mảng $dp$ và lấy kết quả với mỗi trường hợp thử nghiệm trong $O(s(x))$ ($s(x)$ là tổng chữ số của $x$) (cách làm này hơi phức tạp trong cách chuyển state).
- Cách 2: Cập nhật mảng $dp$ liên tục bằng đệ quy có nhớ. Nói cách khác, ta vừa lấy kết quả vừa cập nhật các giá trị cần thiết trong mảng $dp$. Với mỗi trường hợp thử nghiệm, ta gọi hàm tối đa $s(x)$ lần nên độ phức tạp cũng chỉ là $O(s(x))$ (cách làm này dễ cài đặt hơn *theo cảm nhận của mình*).

Về cách cài đặt dp digit, các bạn có thể tham khảo thêm trên các bài viết trên mạng.

Độ phức tạp: $O(\sum (s(l)+s(r)))$.

## Ngày thi thứ ba

### Câu 1 - Cặp số (7 điểm)

> Tác giả: Hà Phước Vũ

Ta có thể thấy rằng ta chỉ cần quan tâm tới các thừa số $2$ xuất hiện trong các phần tử $a_i$. Giả sử $e_i$ là số tự nhiên lớn nhất thoả mãn $2^{e_i}$ là ước của $a_i$, nhiệm vụ của ta là đếm số cặp $(i, j)$ thoả mãn $e_i+e_j \ge k$.

Gọi $cnt[x]$ là số lượng phần tử $i$ có $e_i = x$. Khi đó, ta có thể duyệt các cặp giá trị $(i, j)$ của $e$ và tính được kết quả như sau:
- $i = j$: Số cách chọn sẽ là $C^2_{cnt_i}$.
- $i \ne j$: Số cách chọn sẽ là $cnt_i\times cnt_j$.

Với cách trên, độ phức tạp sẽ là $O(30^2)$ cho mỗi lần tính. Để tối ưu hơn, ta có thể sử dụng mảng cộng dồn dựa vào tính chất $i+j \ge k$. Khi đó, độ phức tạp sẽ chỉ còn là $O(30)$.

Với mỗi truy vấn, ta chỉ việc cập nhật lại mảng $e$ và $cnt$ rồi tính lại kết quả như trên.

Độ phức tạp của ý tưởng trên là:
- Thời gian: $O(n + q\times 30)$.
- Bộ nhớ: $O(n + 30)$.

### Câu 2 - Skibidi Toilet (7 điểm)

> Tác giả: Hà Phước Vũ

Gọi $dp[i][j]$ là số màn chơi gồm $i$ quái vật với quái vật thứ $i$ là loại $j$. Dễ dàng thấy công thức truy hồi của ta sẽ có dạng sau:
- $dp[i][j] = dp[i'][j']$ với $i-i'+1 \le a_j$ và $j' \neq j$ (Đoạn $[i', i]$ chỉ gồm quái vật loại $j$).

Tuy nhiên, ta nhận thấy rằng với mỗi vị trí $i'$ thoả mãn, giá trị của $dp[i][j]$ sẽ chỉ không phụ thuộc vào những giá trị $dp[i'][j]$. Khi đó, ta có thể lấy tổng của $dp[i']$ trừ cho $dp[i'][j]$.

Với tư tưởng trên, ta sẽ gọi $pre[i][j]$ là tổng những giá trị $dp[i'][j]$ mà $1 \le i' \le i$ và $opt[i]$ là tổng những giá trị $dp[i'][j']$ mà $1 \le i' \le i; 1 \le j' \le k$, ta có thể tính $dp[i][j]$ từ $opt[i]$ và $pre[i][j]$. Cụ thể hơn, giả sử như đoạn $[l, r]$ là đoạn chứa những vị trí $i'$ thoả mãn, ta có thể tính được giá trị của $dp[i][j]$ như sau:
- $dp[i][j] = (opt[r]-opt[l-1])-(pre[r]-pre[l-1])$.

Phần tìm đoạn $[l, r]$ sẽ là bài tập của đọc giả. Ngoài ra, bạn cần lưu ý trường hợp $i \le a_j$ vì khi đó ta sẽ cần phải tăng giá trị $dp[i][j]$ lên $1$.

Sau khi tính xong, kết quả cần tìm sẽ là $opt[n]-opt[n-1]$.

Độ phức tạp của ý tưởng trên là:
- Thời gian: $O(n\times k)$.
- Bộ nhớ: $O(n\times k)$.

### Câu 3 - Một bài toán thú vị liên quan đến ... (6 điểm)

> Tác giả: Hà Phước Vũ

Trước hết, ta sẽ gọi $f(i)$ là số Square-Free của $i$. Nếu bạn không biết thì đó sẽ là số nguyên dương $x$ nhỏ nhất sao cho $i\times x$ là số chính phương.

Gọi $cnt[l][r]$ là số lượng vị trí $i$ mà $l < i < r$ thoả mãn $a_l\times a_i\times a_r$ là số chính phương. Khi đó, ta có thể duyệt $r$ từ mỗi vị trí $l$ $(1 \le l \le n)$ và sử dụng đếm phân phối để tính trong độ phức tạp là $O(n^2)$. Cụ thể hơn, những vị trí $i$ sẽ thoả mãn nếu $f(i) = \frac{a_l\times a_r}{gcd(a_l, a_r)^2}$.

Gọi $dp[l][r]$ là số bộ ba chính phương trong đoạn $[l, r]$. Theo quy tắc bao hàm loại trừ, ta sẽ có công thức truy hồi sau:
- $dp[l][r] = dp[l+1][r]+dp[l][r-1]-dp[l+1][r-1]+cnt[l][r]$.

Để tính chính xác $dp[l][r]$, ta sẽ duyệt các cặp $(l, r)$ theo tính tăng dần của độ dài của chúng hay là $r-l+1$. Với mỗi truy vấn, ta chỉ việc in ra kết quả với độ phức tạp là $O(1)$.

Về phần đếm phân phối, ta có thể sử dụng mảng tĩnh để đếm thay vì dùng các cấu trúc dữ liệu như `map` để độ phức tạp không dính $log$. Lưu ý rằng ta chỉ quan tâm tới những giá trị $f(i) \le 10^6$.

Độ phức tạp của ý tưởng trên là:
- Thời gian: $O(n^2 + q)$.
- Bộ nhớ: $O(n^2)$.

## Ngày thi thứ tư

### Câu 1 - Kim đồng hồ (5 điểm)

> Tác giả: Nguyễn Hữu Nhật Quang

Ta có thể dễ dàng tính được giờ và phút tại thời điểm $z$ phút sau. Ban đầu, đặt $T = x \times 60 + y$ là số phút từ thời điểm hiện tại đến thời điểm 12 giờ 00 gần nhất. Từ đó ta xác định được giờ và phút hiển thị lúc $z$ phút sau:
- Giờ: $H = \lfloor \frac{T + z}{60} \rfloor \mod 12$.
- Phút: $M = (T + z) \mod 60$.

Từ đó, ta có thể tính được góc của kim giờ và kim phút theo phương thẳng đứng:
- Kim giờ: $\alpha = H \times 30 + M \times 0.5$.
- Kim phút: $\beta = M \times 6$.

Từ đó ta tính được góc giữa hai kim là $\min (\alpha - \beta, 360-(\alpha-\beta))$.

### Câu 2 - Đảo ngược xâu (5 điểm)

> Tác giả: Nguyễn Hữu Nhật Quang

Với bài này, bạn chỉ cần làm đúng những gì đề bài bảo :penguin: đây chỉ là một bài kiểm tra khả năng cài đặt của các bạn.

### Câu 3 - Nhân số nguyên (4 điểm)

> Tác giả: Nguyễn Hữu Nhật Quang

**Lời giải 1:** Quy hoạch động bitmask

Dễ thấy ta chỉ quan tâm $k$ phần tử lớn nhất và $k$ phần tử nhỏ nhất của dãy. Lập một dãy mới gồm các phần tử này (có độ dài không quá $2k$).

Gọi $dp[i][mask]$ là tổng lớn nhất **được cộng thêm vào dãy** nếu xét đến phần tử thứ $i$ và đã sử dụng các phép nhân là các bit được bật trong $mask$. Với mỗi cặp $(i, mask)$, ta có thể duyệt các tổ hợp phép nhân có thể (là submask của phần bù của $mask$).

Độ phức tạp: $O(3^k \times k)$.

**Lời giải 2:** Xét trường hợp

Dễ thấy thứ tự thực hiện các phép nhân không quan trọng do phép nhân có tính giao hoán.

Hiển nhiên rằng, chúng ta sẽ nhân tất cả các $b_i$ dương vào số lớn nhất của dãy (nếu nó là một số dương). Câu chuyện còn lại là xử lý các $b_i$ âm (và bằng 0) như thế nào. Với các thao tác nhân được liệt kê dưới đây, ta ngầm hiểu rằng chỉ thực hiện thao tác nếu tích sau khi nhân lớn hơn số ban đầu.

Không mất tính tổng quát, giả sử có $x$ số $b_i < 0$ lần lượt là $b_1 \le b_2 \le ... \le b_x$; đồng thời $a_1 \le a_2 \le ... \le a_n$. Đặt $P = b_0 \times b_1 \times ... \times b_x$. Xét các trường hợp sau:
1. $x$ lẻ:
- Trường hợp 1: Nhân $P$ vào $a_1$.
- Trường hợp 2: Nhân $b_x$ vào $a_1$; nhân $\frac{P}{b_x}$ vào $a_n$.
2. $x$ chẵn:
- Trường hợp 1: Nhân $P$ vào $a_n$.
- Trường hợp 2: Nhân $b_x$ vào $a_2$; nhân $\frac{P}{b_x}$ vào $a_1$.

Với $b_i = 0$, nếu sau khi nhân mà trong dãy vẫn còn phần tử có giá trị âm, có thể dùng các số này để loại bỏ các phần tử đó.

### Câu 4 - Trang trí Tết (3 điểm)

> Tác giả: Nguyễn Hữu Nhật Quang

Chúng ta sẽ sử dụng kỹ thuật cửa sổ trượt (sliding window) để giải quyết mỗi trường hợp thử nghiệm trong $O(n)$.

Câu hỏi đặt ra là: Làm thế nào để "trượt" từ đoạn $[l, r]$ sang $[l + 1, r + 1]$ trong $O(1)$ ?

Hiển nhiên chúng ta sẽ đếm tần suất xuất hiện của mỗi màu đèn và chọn ra $k$ màu đèn có số lần xuất hiện nhiều nhất. Tuy nhiên chúng ta cần tìm ra cách tính tổng của $k$ màu đèn này một cách hiệu quả. Hay nói cách khác, chũng ta cần một "cấu trúc dữ liệu" có khả năng sau:
- Tăng một phần tử lên 1.
- Giảm một phần từ đi 1.
- Tính tổng $k$ phần tử lớn nhất.

Do tính chất không quan trọng thứ tự, chúng ta có thể duy trì một dãy $x$ là bảng tần số đã sắp xếp theo thứ tự giảm dần. Với mỗi thao tác, ta xử lý như sau:
- Tăng một phần tử có giá trị $c$ (đã biết) lên 1 $\rightarrow$ tăng phần tử đầu tiên có giá trị $c$ trong dãy $x$ lên 1.
- Giảm một phần tử có giá trị $c$ đi 1 $\rightarrow$ giảm phần tử cuối cùng có giá trị $c$ đi 1.

Chúng ta có thể lưu một mảng hỗ trợ $first[j]$ lưu vị trí phần tử đầu tiên có giá trị $j$ trong dãy $x$.

Do số lượng thao tác thay đổi là đủ nhỏ, ta có thể xem mỗi thao tác đóng góp vào tổng $k$ phần tử lớn nhất như thế nào để có thể cập nhật lại kết quả ngay sau mỗi thao tác.

Đến đây bài toán được giải quyết.

### Câu 5 - Tổng lớn nhất (3 điểm)

Đầu tiên, chúng ta cần giải quyết bài toán với $k = 1$ trước.

Gọi $f(i, j)$ là tổng lớn nhất có thể tạo được nếu bắt buộc chọn phần tử $a_i$ và:
- Số $b_1$ chưa được sử dụng (sau khi xét phần tử $i$) nếu $j = 0$.
- Số $b_1$ sẽ được sử dụng cho phần tử $a_{i + 1}$ nếu $j = 1$.
- Số $b_1$ đã được sử dụng trước đó (và sẽ không được sử dụng nữa) nếu $j = 2$.

$f(i, j)$ sẽ là max của các trường hợp sau:
- $\max (0, f(i - 1, j)) + a_i \times mul_j$, với $mul_j = b_1$ nếu $j = 1$, ngược lại $mul_j = 0$: chọn phần tử $a_i$ với đúng "mask" là $j$.
- $\max (f(i, k))$ với $0 \le k < j$: phần tử $a_i$ đã được chọn với một "mask" khác - việc chuyển "mask" là để chuẩn bị cho phần tử $a_{i + 1}$.

Lưu ý rằng, chúng ta chỉ quan tâm việc thực hiện phép nhân nếu đoạn mà nó thực hiện nằm trong phần tổng lớn nhất (mà chúng ta sẽ chọn cuối cùng). Những phép nhân phía ngoài sẽ không ảnh hưởng đến tổng cuối cùng nên chúng ta không cần thiết phải quan tâm.

Từ $k = 1$, không khó để chuyển bài toán thành $k \le 6$, chỉ đơn giản là $j$ là một số trong đoạn $[0, 3^k - 1]$ và được viết trong hệ tam phân.

Độ phức tạp: $O(n \times 3^k \times k)$.

## Ngày thi thứ năm
> Tác giả: Nguyễn Hữu Phúc (nhphuc).

### Câu 1 - Kaoruko và chỉ số cute (5 điểm)
Với các subtask 1 và 2 ta đơn giản chỉ cần cài đặt tìm giai thừa với độ phức tạp $O(n)$.

Với subtask 3, chúng ta sử dụng tới kĩ thuật mảng hằng, cụ thể:

- Ta tính trước giai thừa modulo của các vị trí $0,\ B,\ B + B,\ B + B + B,\ ...$ sau đó thêm các giá trị này vào code dưới dạng một mảng.

- Sau đó, ta đơn giản tính các giá trị $n!$ trong $O(B)$.

Độ phức tạp $O(B)$ với $B$ tuỳ trường hợp, ở đây tác giả khuyên dùng $B = 10^6$.

### Câu 2 - Kaoruko và chiếc bàn cá hề (4 điểm)

Với bài tập này, các bạn chỉ cần đọc rõ đề: output chỉ yêu cầu thể tích chiếc bàn. Độ phức tạp $O(1)$.

### Câu 3 - Kaoruko và tệp hồ sơ (4 điểm)

Nhận xét quan trọng: Vì với số lớn thứ $i$ trong mảng chỉ có nhiều nhất $n - i$ số lớn hơn $i$ nên ta thấy rằng giá trị lớn nhất trong mảng sau thao tác mã hoá lần hai đúng bằng giá trị lớn nhất trong mảng trước thao tác.

Từ nhận xét trên, ta có nhận xét thứ hai: vị trí của giá trị lớn nhất đầu tiên trong mảng $a$ sau lần mã hoá thứ hai cũng chính là vị trí của giá trị lớn nhất trước thao tác. Độ phức tạp $O(n)$.

### Câu 4 - Kaoruko và mua sắm (4 điểm)

Ta dựng một cây Segment Tree với mỗi một đỉnh là một mảng quy hoạch động (gọi tắt là $dp$) với ý nghĩa:

- $dp_{id,\ l,\ r}$: số cách tạo ra phần từ $l$ đến $r$ trong VOI25P4 với các phần hàng được quản lí bởi đỉnh $id$.

Dễ dàng nhận thấy, độ phức tạp của việc gộp hai đỉnh là $O(7^3)$, tuy vậy với việc các hằng số của việc này sẽ rất nhỏ nên trung bình sẽ không vượt quá $O(50)$.

Từ đó, ta dễ dàng thực hiện các cập nhật và truy vấn. Độ phức tạp $O(50n\times log\times n + 50q\times log\times n).$

### Câu 5 - Kaoruko và dự trữ bánh ngọt (3 điểm)

Dựng mảng quy hoạch động (gọi tắt là $dp$) với ý nghĩa:

- $dp_{l,\ r,\ p,\ d}$: đã đặt $d$ chiếc bánh ngọt, chiếc bánh ngọt thứ $d$ đặt ở tủ bảo quản $p$ và mọi tủ bảo quản từ $l$ đến $r$ đều đã có ít nhất một chiếc bánh ngọt.

Từ đó, ta có công thức chuyển trạng thái:

- $dp_{l,\ r,\ p,\ d} = dp_{l,\ r,\ p - 1,\ d - 1} + dp_{l,\ r,\ p + 1,\ d - 1}$.

- Nếu $p = l$, $dp_{l,\ r,\ p,\ d}\ += dp_{l + 1,\ r,\ l + 1,\ d - 1}$.

- Nếu $p = r$, $dp_{l,\ r,\ p,\ d}\ += dp_{l,\ r - 1,\ r - 1,\ d - 1}$.

Đáp án sẽ là $\sum dp_{1,\ n,\ i,\ k}\ \forall\ 1\leq i\leq n$. Độ phức tạp $O(n^3\times k)$ (lưu ý rằng hằng số thực tế rất nhỏ).

## Ngày thi thứ sáu

### Câu 1 - Lật bit (5 điểm)

> Tác giả: Nguyễn Hữu Nhật Quang

Ta có thể nhận ra rằng để tối ưu hoá dãy nhị phân thì nên lật những bit $0$ thành $1$ đầu tiên vì $1$ là giá trị lớn hơn , ta sẽ duyệt qua toàn bộ dãy và tại mỗi vị trí có bit $0$ nếu còn thao tác lật bit đó thành $1$ cho đến khi hết thao tác hoặc hết dãy, nếu thao tác còn dư và lẻ thì ta sẽ lật bit cuối cùng của dãy.

### Câu 2 - Điền bảng (5 điểm)

> Tác giả: Nguyễn Hữu Nhật Quang

Nhận xét rằng có thể cố định không thay đổi hàng 1 của bảng.

Ta thực hiện đệ quy quay lui theo thứ tự các ô như sau: $(2, 1) \rightarrow (3, 1) \rightarrow ... \rightarrow (n, 1) \rightarrow (2, 2) \rightarrow ... \rightarrow (n, n)$. Với mỗi vòng đệ quy, cần đặt một số nhánh cận cần thiết để có thể break đệ quy sớm khi bảng không đúng yêu cầu (ví dụ: break khi không đúng tính chất hoán vị hàng và cột).

### Câu 3 - Giải mã (4 điểm)

> Tác giả: Chu Chính Hoàng

Gọi $dp[i][u][v]$ là số dãy thỏa mãn điều kiện đề bài từ $1\rightarrow i$ và $a_{i-1}=u,a_i=v$, Trường hợp cơ sở sẽ là $dp[2][u][v]=1$ nếu $u+v=a_1$ hoặc $a_1=-1$.
Với mỗi $3\le i\le n$ nếu $a_i=-1$ thì ta chỉ cập nhất $dp[i+1][u][v]+=dp[i][u][v]$ ngược lại ta sẽ cập nhật $dp[i+1][v][a_{i+1}-u-v]+=dp[i][u][v]$.
Kết quả cuối cùng là tổng $dp[n-1][u][v]$ thỏa mãn $u+v=a_n$ hoặc $a_n=-1$

### Câu 4 - Hoán vị (3 điểm)

> Tác giả: Lê Kiến Thành

Đáp án là tích của những số không xuất hiện trong tập trừ đi 1. Ví dụ: $n = 5$ và $S = [1, 3]$. Đáp án sẽ là $(2-1)*(4-1)*(5-1) = 12$.

Tại sao? Ta sẽ xây dựng mảng pos - vị trí của phần tử theo thứ tự tăng dần giá trị của phần tử tại vì trí đó - bằng cách duyệt từ trái sang phải, và ở mỗi bước, ta sẽ chèn số ở vị trí hiện tại vào mảng pos. Nếu vị trí ~i~ thuộc $S$, thì chắc chắn ta sẽ chèn nó vào cuối mảng pos, tức là số hiện tại lớn nhất permutation, ngược lại ta sẽ chèn nó vào $i-1$ vị trí còn lại.

### Câu 5 - Tặng quà (3 điểm)

> Tác giả: Huỳnh Anh Nhật

Đây là bài toán chia kẹo euler điển hình vậy nên đáp án của mỗi truy vấn là
$C(n-1, k-1) = \binom{n-1}{k-1} = \frac{(n-1)!}{(k-1)!(n-k)!}$
Vì $m$ cố định và $m \leq 10^9 + 7$ nên $m$ không có quá $10$ ước số nguyên tố khác nhau nên có thể sử dụng định lí Thặng dư Trung Hoa để giải.

## Ngày thi thứ bảy

### Câu 1 - Chạy đua (5 điểm)

> Tác giả: Chu Chính Hoàng

Để hoàn thành một vòng đua khi ta gặp lại người mà đã vượt qua ở vòng đua trước.
Từ đó ta tạo một tập hợp lưu những người đã bị vượt qua, nếu gặp một người đã tồn tại trong tập hợp thì xóa mọi số trong tập hợp đó.
Số lần qua vạch đích sẽ là số lần xóa tập hợp.

### Câu 2 - Nhà ăn đặc biệt (5 điểm)

> Tác giả: Chu Chính Hoàng
Solution: Mai Ngọc Phú

Gọi $f[i]$ là số lượng dãy bàn liên tiếp độ dài $i$ có $p \le u-1$
Gọi $g[i]$ là số lượng dãy bàn liên tiếp độ dài $i$ có $p \le v$
Như vậy, với mỗi đoạn $i$ ta chỉ cần in ra $g[i]$ - $f[i]$ .

Để tính được $f[i]$ mình duyệt cố định $l$ ($1\le l \le n$) và tìm $r$ lớn nhất sao cho $p$ của đoạn $a[l...r] \le u-1$ .

Lưu ý: Để xác định $r$ bạn có thể sử dụng kĩ thuật 2 con trỏ, với $l$ bạn xác định được $r$ thì với $l'=l+1$, $r'$ chắc chắn >= $r$ nên ĐPT sẽ là $O(2n)$

Với mỗi $l$ ($1\le l \le n$):
$p$ của $a[l] \le u-1$ $\Rightarrow$ $f[1]+=1$
$p$ của $a[l...(l+1)] \le u-1$ $\Rightarrow$ $f[2]+=1$
.
.
.
$p$ của $a[l...r] \le u-1$ $\Rightarrow$ $f[r-l+1]+=1$

Tương tự ta cũng tính được $g[i]$.

### Câu 3 - Pickleball (4 điểm)

> Tác giả: Chu Chính Hoàng
Solution: Mai Ngọc Phú

Dựng một [DAG](https://en.wikipedia.org/wiki/Directed_acyclic_graph) bằng cách nối đỉnh $a_i$ với $a_i +b_i$.
Gọi $dp_i$ là số sân lớn nhất xây được khi ban đầu có $i$ sân, ban đầu $dp_i=i$.
Sau đó xét các đỉnh của DAG từ lớn đến nhỏ và cập nhật $dp_u=max(dp_u,dp_v)$ khi có cách nối từ $u$ đến $v$.

### Câu 4 - Tổng chữ số (3 điểm)

> Tác giả: Chu Chính Hoàng

Ta chỉ xét các trường hợp $n\le 162$ vì khi $n>162$ thì đáp số luôn là $k$.
Gọi $dp[i][s]$ là số lượng số có $i$ chữ số có tổng chữ số nhỏ hơn $s$
Trường hợp cơ sở $dp[0][i]=1$
Với $1\le i\le 10^5$ và $0\le j\le n$ thì $dp[i][j]=dp[i][j-1]+dp[i-1][j]$
Nếu $j>9$ thì $dp[i][j]=dp[i][j]-dp[i-1][j-10]$
Để truy vết đáp án thì ta duyệt từ số lớn nhất nếu như $dp[i-1][n-j-1]\le k$ suy ra số thứ $i$ là $j$, và cập nhật lại $k=k-dp[i-1][n-j-1]$.

### Câu 5 - Công việc (3 điểm)

> Tác giả: Chu Chính Hoàng

Gọi $dp[v][i]$ là số lượng người lớn nhất khi ta gộp các con của $v$ và hoàn thành $i$ công việc.

## Ngày thi thứ tám
### Câu 1 - Solra và High and Low (5 điểm)

> Tác giả: Nguyễn Dĩ Thái

Ta có thể dễ dàng nhận ra chiến thuật tối ưu của Solra cho trò chơi này là luôn lấy nửa phần có số lượng bài lớn hơn. Vấn đề là công thức tính xác suất.

Gọi $x$ là số lượng lá bài có thể chiến thắng. Vì theo đề bài, nữ hoàng Cơ rút 1 lá, và Solra phải chọn trong bộ bài còn lại, ta có số bài còn lại có thể bốc là 51.

Công thức cho một ván đấu là: $\frac{x}{51}$

Áp dụng quy tắc nhân, ta nhân tất cả xác suất Solra thắng lại với nhau, sẽ cho ra xác suất Solra thắng N ván.

### Câu 2 - Hasami và đống giấy tờ (4 điểm)

> Tác giả : Nguyễn Dĩ Thái

Mục tiêu của ta là tìm thời gian ngắn nhất và dãy công việc tối ưu mà Hasami không vi phạm thời gian $K$, ta có thể nghĩ đến ngay đến việc dùng 2 con trỏ để duyệt qua toàn bộ dãy công việc để kiểm tra.

Gọi $X$ thời gian tổng của một đoạn tổng công việc liên tiếp nếu tổng không vượt quá $K$ sẽ kiểm tra có đoạn nào có tổng thời gian lớn nhất hay không và lưu lại các vị trí và tổng đó, nếu có nhiều đoạn có tổng thời gian bằng nhau thì ưu tiên chọn đoạn có độ dài nhỏ nhất (tức là $r - l + 1$) và nếu độ dài bằng nhau thì ta chọn đoạn có chỉ số $L$ nhỏ nhất và cuối cùng tổng thời gian ngắn nhất sẽ là tổng thời gian của tất cả công việc trừ đi thời gian của đoạn công việc tối ưu. Độ phức tạp sẽ là $O(n)$.

### Câu 3 - Isaac và việc điệp viên (4 điểm)

> Tác giả : Nguyễn Dĩ Thái

Bài này thì ta có thể nhận thấy rằng mục tiêu của trò chơi là làm sao cho người chơi đầu tiên ($Isaac$ hoặc $AI$) có thể chiến thắng bằng cách giảm số tầng nước về 0. Trạng thái thắng là khi người chơi có thể di chuyển tới một tầng mà đối thủ sẽ không thể thắng và thua thì mọi sự lựa chọn đều thua.Vậy thì ta sẽ có cách duyệt từng tầng với mỗi tầng $i$ sẽ kiểm tra nút bấm $a_j$ sao cho $i$ $-$ $a_j$ là một tầng mà đối thủ sẽ thua khi đó ta sẽ đánh dấu lại nữa là xong.

### Câu 4 - Akina và "đói và sợ" (4 điểm)
> Tác giả : Nguyễn Dĩ Thái

Gọi $d[i][j]$ là mảng lưu số bước đi ngắn nhất và tổng thanh hồi phục tại mỗi ô $(i , j)$. Mỗi phần tử $d[i][j]$ là $1$ cặp $(x , y)$ với $x$ là số bước ngắn nhất từ $(1, 1)$ đến ô $(i , j)$ và $y$ là tổng thanh hồi phục từ ô $(1 , 1)$ đến ô $(i , j)$
Nhận thấy ta có thể dùng $BFS$ dùng hàng đợi $queue$ để lưu trữ các ô cần duyệt, mỗi lần duyệt ta sẽ kiểm tra các ô lân cận, nếu có thể đi qua thì ta sẽ cập nhật số bước đi ngắn nhất $x$ và tổng thanh hồi phục $y$ và lưu ý nếu có nhiều đường đi ngắn nhất đi tới ô này thì chọn đường có tổng thanh phục hồi cao nhất và sau khi $BFS$ xong thì kết quả sẽ là in ra $d[n][m].first$ với $d[n][m].second$ là số bước đi ngắn nhất và tổng thanh hồi phục.

### Câu 5 - Sayaki và trò chơi Conway (3 điểm)

> Tác giả: Nguyễn Dĩ Thái

Với $M \le 2$, ta nhận ra không có cách nào để tạo một ô con 3x3, vì vậy, tất cả các trạng thái của khay đều là trạng thái bền vững. Vì trạng thái của một ô có "sống", hoặc "chết", ta có công thức: $2 ^ {NM}$

Với các trường hợp còn lại, ta sử dụng DP Bitmask, dựa trên việc ta chỉ xét ba cột một (hai cột tiền tố và một cột hiện tại). Gọi $DP[mask1][mask2]$ là số lượng trạng thái khi có cột tiền tố thứ nhất là $mask1$ và cột tiền tốt thứ hai là $mask2$. Chúng ta sẽ xét từng trạng thái cho cột thứ ba, gọi là $mask3$, sau đó chúng ta sẽ đẩy về phía bên trái. Đặt tất cả giá trị ban đầu của $DP$ là 1, vì với 2 hàng, chưa thể có ô 3x3 con, nên nhìn chung vẫn là trạng thái bền vững.

Sau đó, gọi $newDP[mask2][mask3]$ là trạng thái tiếp theo. Với mỗi $mask3$ hợp lệ, và khi check cả 3 cột $mask1$, $mask2$, $mask3$, đều ở trạng thái bền vững, ta có công thức:

$newDP[mask2][mask3] += DP[mask1][mask2]$

Việc tịnh tiến như này, lưu ý, bắt đầu từ cột thứ 3. Lưu ý thứ hai, bạn phải chuyển $newDP$ về cho $DP$ để tái sử dụng, đồng thời reset $newDP$ về 0.

Độ phức tạp: $O(N*2^M*2^M)$

## Ngày thi thứ chín

### Câu 1 - Tập nấu ăn (7 điểm)

> Tác giả: Nguyễn Văn Minh

Dễ dàng thấy rằng với mỗi món ăn thứ $i$, số khẩu phần có thể làm ra từ nguyên liệu $j$ sẽ là $c_{i, j} = \lfloor \frac{a_j}{b_{i, j}} \rfloor$. Từ bảng $c$ mà ta dựng lên vậy, ta có thể tính được số khẩu phần của món thứ $i$ sau khi bỏ đi $k$ nguyên liệu bất kỳ sẽ là phần tử lớn thứ $n-k$ của $c_i$.

Khi đó, ta sẽ gọi $ans_j$ là đáp án tối ưu với $k = j$ và sắp xếp các mảng $c_i$ theo thứ tự tăng dần. Khi đó, giá trị của $ans_j$ sẽ là giá trị nhỏ nhất của các phần tử ở cột $j+1$ của bảng $c$.

Độ phức tạp của ý tưởng trên là:
- Thời gian: $O(n\times m)$.
- Bộ nhớ: $O(n\times m)$ hoặc $O(n)$.

### Câu 2 - Tổng đường đi (7 điểm)

> Tác giả: Hà Phước Vũ

Trước khi giải bài toán gốc, ta sẽ giải quyết bài toán sau:
> Cho dãy $a$ gồm $n$ phần tử và với mỗi vị trí $i$, hãy tìm giá trị lớn nhất của tổng của một đoạn con bất kỳ của tiền tố thứ $i$ của dãy $a$.

Thay vì sử dụng Kadane, ta gọi $p_i = \sum_{j = 1}^i a_j$. Khi đó, kết quả cho vị trí $i$ sẽ là:
- $ans_i = p_i - min(p_0, p_1, ..., p_{i-1})$.

Để giải quyết tối ưu, ta chỉ sử dụng mảng cộng và min dồn.

Ta sẽ gọi $dp[v]$ là kết quả của cây con gốc $v$. Ta sẽ xét $2$ trường hợp sau:
- Trường hợp $1$: Đường đi tối ưu sẽ không chứa đỉnh $v$.
- Trường hợp $2$: Đường đi tối ưu sẽ chứa đỉnh $v$.

Với trường hợp $1$, ta chỉ việc lấy giá trị lớn nhất của $dp[u]$ với $u$ là đỉnh con trực tiếp của $v$. Còn với trường hợp $2$, ta sẽ xét tiếp $2$ trường hợp sau:
- Đường đi tối ưu sẽ xuất phát từ $v$ đến một đỉnh trong cây con.
- Đường đi tối ưu sẽ chỉ chứa $v$ và xuất phát từ $2$ đỉnh bất kỳ trong cây con.

Để giải quyết $2$ trường hợp này, ta chỉ việc tìm $2$ đường đi xuất phát từ $v$ đến một đỉnh trong cây con sao cho tổng của $2$ đường đi này là lớn nhất. Giả sử $2$ giá trị này là $f$ và $s$, kết quả cho $2$ trường hợp sẽ lần lượt là $f$ và $f+s-a_v$. Để tính $f$ và $s$, ta có thể sử dụng tư tưởng của bài toán ở trên.

Độ phức tạp của ý tưởng trên là:
- Thời gian: $O(n)$.
- Bộ nhớ: $O(n)$.

### Câu 3 - AND = OR (6 điểm)
> Tác giả: Hà Phước Vũ

Để đơn giản hơn, mình sẽ định nghĩa lại một chút:
- $f(l, r) = a_l \& a_{l+1}$ $\&$ $...$ $\&$ $a_r$ và $g(l, r) = b_l \& b_{l+1}$ $\&$ $...$ $\&$ $b_r$.
- $F(l_1, r_1, l_2, r_2)$ là số cặp $(u_1, v_1, u_2, v_2)$ thoả mãn $f(u_1, v_1) = g(u_2, v_2)$ với $l_i \le u_i \le v_i \le r_i$ $(1 \le i \le 2)$.

Khi đó, $S$ cần tính sẽ là biểu thức siêu dài sau:
- $S = \sum_{l_1 = n}^n \sum_{r_1 = l_1}^n \sum_{l_2 = 1}^m \sum_{r_2 = l_2}^m F(l_1, r_1, l_2, r_2)$.

Không quá khó để thấy, đây là dạng bài Contribution Sum cực kì phổ biến. Cụ thể hơn, ta sẽ tìm đáp án với tư tưởng khác với đề bài như sau:
- Xác định được số cặp $(u_1, v_1)$ có $f(u_1, v_1) = x$ và số cặp $(u_2, v_2)$ có $f(u_2, v_2) = x$.
- Với mỗi bộ bốn $(u_1, v_1, u_2, v_2)$ đó, ta sẽ xác định số cặp $(l_1, r_1)$ và $(l_2, r_2)$ thỏa mãn $l_1 \le u_1 \le v_1 \le r_1$ và $l_2 \le u_2 \le v_2 \le r_2$.

Ta có một nhận xét sau:
- $f(l-1, r) \le f(l, r)$: Với phép AND, số lượng bit $1$ của kết quả khi càng AND thêm nhiều số vào sẽ không bao giờ tăng bởi bit $1$ chỉ có thể tạo ra từ $2$ bit $1$.
- $g(l-1, r) \ge g(l, r)$: Với phép OR, số lượng bit $1$ của kết quả khi càng OR thêm nhiều số vào sẽ không bao giờ giảm bởi chỉ cần có $1$ bit $1$ trong $2$ bit đã tạo ra bit $1$, trong khi $2$ bit $0$ sẽ tạo ra bit $0$ và rõ ràng là không ảnh hưởng đến kết quả.

Từ đó, ta có một nhận xét **cực kì quan trọng** như sau:
- Với mỗi vị trí $r$ cố đỉnh, $f(l, r)$ và $g(l, r)$ sẽ thao đổi tối đa $\lceil log_2a_r \rceil$ lần khi $l$ giảm.

Khi đó, với mỗi vị trí $r$ cố định, ta sẽ sử dụng Chặt nhị phân để tìm kiểm những vị trí đặc biệt này. Giả sử ta tìm được vị trí $l$ mà $f(l, r) \neq f(l+1, r)$ thì ta biết được rằng các cặp $(l+1, r)$, $(l+2, r)$, ..., $(pre_l, r)$ sẽ cùng có giá trị $f(l, r)$ (với $pre_l$ là vị trí hàm này thay đổi trước đó).

Tính đến hiện tại, ta đã làm xong bước $1$ của tư tưởng giải quyết bài này. Gọi $cnt_a(u_1, v_1)$ cho mỗi cặp $f(u_1, v_1) = x$ là số cặp $(l_1, r_1)$ thỏa mãn $l_1 \le u_1 \le v_1 \le r_1$. Không quá khó để thấy, $cnt_a(u_1, v_1) = u_1 \times (n-v_1+1)$. Tuy nhiên với mỗi giá trị $x$, ta chỉ biết số cặp $(u_1, v_1)$ mà $f(u_1, v_1) = x$ dưới dạng là một đoạn với một vị trí cố định (xem lại phần bên trên). Rõ ràng hơn, ta chỉ biết các cặp $(l, r)$ đến $(pre_l, r)$ có giá trị hàm $f$ là $x$. Việc duyệt $u_1$ từ $l$ đến $pre_l$ với $r = v_1$ sẽ không hề hiệu quả và không khác gì cày trâu. Khi đó, ta sẽ có nhận xét như sau:
- $cnt_a(pre_l, r) = pre_l \times (n-r+1)$.
- $cnt_a(pre_l-1, r) = (pre_l-1) \times (n-r+1)$.
- $...$
- $cnt_a(l, r) = l \times (n-r+1)$.

Dễ dàng thấy nếu ta có thể đặt $(n-r+1)$ là nhân tử chung thì tổng tất cả giá trị $cnt_a$ trên sẽ là $\frac{(l+pre_l)\times (pre_l-l+1)\times (n-r+1)}{2}$. Khi đó, ta sẽ gọi $ans_a[x]$ là tổng số cặp $(u_1, v_1)$ của mọi cặp $(l_1, r_1)$ mà $f(u_1, v_1) = x$, $ans_a[x]$ có thể được tính dễ dàng từ những đoạn mà ta xác định được và công thức trên. Với $cnt_b(u_2, v_2)$ và $ans_b[x]$, ta sẽ làm tương tự.

Sau khi tính xong, $ans_a[x]\times ans_b[x]$ sẽ là số bộ bốn $(u_1, v_1, u_2, v_2)$ của tất cả các giá trị $F(l_1, r_1, l_2, r_2)$ với $f(u_1, v_1) = f(u_2, v_2) = x$.

Về phần Chặt nhị phân trên các vị trí thay đổi ban đầu, độ phức tạp trung bình cho mỗi vị trí $r$ sẽ là $O(log_2^2n\times log_2a_i)$ và có thể thấy độ phức tạp này là chưa đủ tốt. Ta sẽ có thêm $2$ nhận xét như sau:
- $a$ $\&$ $a = a$ và $a$ $|$ $a = a$.

Dễ dàng thấy rằng phép AND và OR thỏa mãn tính chất Idempotence, khi đó ta có thể sử dụng Sparse Table để truy vấn lấy tổng AND và OR trong $O(1)$ thay vì sử dụng Segment Tree trong $O(log_2n)$.

Độ phức tạp của ý tưởng trên là:
- Thời gian: $O(n\times log_2n\times log_2a_i)$.
- Bộ nhớ: $O(n\times log_2n)$.

## Ngày thi thứ mười

### Câu 1 - Chúc Tết (5 điểm)

> Tác giả: Nguyễn Hữu Nhật Quang
> Solution: Hoàng Dương

Với bài toán này, ta chỉ cần đếm số ký tự $c$ trong xâu ban đầu rồi nhân với $n$ là được. Lưu ý:
- Xâu nhập vào có dấu cách, nên cần `getline`.
- Kết quả có thể vượt quá $10^9$, nên cần dùng `long long`.

Độ phức tạp: $O$ $(n)$.

### Câu 2 - Tặng quà Tết (5 điểm)

> Tác giả: Nguyễn Hữu Nhật Quang
> Solution: Hoàng Dương

#### Subtask 1: $n \le 2000$.

Duyệt mọi cặp $1 \le i \le j \le n$ và cập nhật kết quả.

Độ phức tạp: $O$ ($n^2$).

#### Subtask 2: $n \le 2 \times 10^5$.

Trước hết, dễ thấy ta sẽ lấy $mod\ m$ mọi số $a[i]$. Ta cũng có thể sắp xếp lại mảng.

Với một giá trị $a[i]$, $a[j]$ có hai trường hợp:

- Nếu $0 \le a[j] \le m - 1 - a[i]$, thì $0 \le a[i] + a[j] \le m - 1$, không ảnh hưởng phép $mod$. Lúc này kết quả sẽ cập nhật vào số $a[j]$ lớn nhất thỏa mãn $a[j] \le m - 1 - a[i]$.
- Ngược lại, kết quả sẽ luôn nằm tại $a[n - 1] + a[n]$ $mod$ $m$.

Độ phức tạp: $O$ ($n \times log_{n}$).

### Câu 3 - Xem pháo hoa (4 điểm)

> Tác giả: Nguyễn Hữu Nhật Quang
> Solution: Hoàng Dương

Nhận xét: Kết quả là độc lập với từng giàn pháo hoa. Vì vậy, ở đây, mình sẽ xét từng giàn pháo hoa một.

Với mỗi giàn pháo hoa, ta sẽ duyệt vị trí đặt từ $1$ tới $n$.

Để tính toán nhanh độ phủ của một giàn pháo hoa, ta làm như sau:

- Gọi $f[i] = a[1] + a[2] + ... + a[i]$.
- Gọi $g[i] = a[1] \times 1 + a[2] \times 2 + \cdot \cdot \cdot + a[i] \times i$.

Xét một quả pháo hoa với hiệu ứng $b$ và đặt ở vị trí $pos$:

Xét bên trái: đặt $L$ là vị trí xa nhất mà một người có thể thấy pháo hoa (dựa vào độ phủ của nó).

Kết quả ở bên trái sẽ cộng thêm $(a[pos - L] + \cdot \cdot \cdot + a[pos - 1])$ $+$ $(a[pos - L] \times (pos - L) + \cdot \cdot \cdot + a[pos - 1] \times (pos - 1))$.

Tương tự với bên phải. Với mỗi pháo hoa, ta sẽ lấy giá trị tối ưu nhất.

Độ phức tạp: $O$ ($n \times k$).

### Câu 4 - Bài tập Tết (3 điểm)

> Tác giả: Nguyễn Hữu Nhật Quang
> Solution: Hoàng Dương

Tóm tắt đề bài: Gọi $f (i, j)$ là tổng của $k$ số lớn nhất trong đoạn con liên tiếp từ $a_i$ tới $a_j$ (nếu $j - i + 1 < k$ thì ta lấy tổng cả mảng). Hãy tính $\sum f (i, j)$ với mọi $1 \le i \le j \le n$.

#### Subtask 1: $n \le 200$.

Với subtask này, chúng ta có thể duyệt mọi đoạn con $(i, j)$, sau đó dùng một $vector$ để lưu đoạn con này lại, sắp xếp lại, lấy $k$ phần tử đầu tiên và cộng vào tổng.

Độ phức tạp: $O$ ($n^3 \times log (n)$).

#### Subtask 2: $n \le 2000$.

Với subtask này, thay vì duyệt lại các phần tử trong đoạn con từ $i$ đến $j$, ta có thể sử dụng một [hàng đợi ưu tiên (priority-queue)](https://viblo.asia/p/heap-va-priority-queue-cua-c-gAm5ymYX5db#_iii-priority_queue-trong-c-5). Ta sẽ liên tục đẩy phần tử nhỏ nhất ra khỏi priority-queue nếu có lớn hơn $k$ phần tử. Kết quả sẽ cộng thêm tổng của các phần tử trong priority-queue.

Độ phức tạp: $O$ ($n^2 \times log (n)$).

#### Subtask 3: $k = 1$.

> Từ đây ta quy ước: Phần tử $a_i$ được gọi là lớn hơn phần tử $a_j$ nếu một trong hai điều kiện sau đây thỏa mãn:
> - $a_i > a_j$.
> - $a_i = a_j$ và $i < j$.

Từ subtask này, ta sử dụng kỹ thuật **contribution-to-sum**, hay ta xem xét, mỗi phần tử $a_i$ được tính vào tổng bao nhiêu lần.

Ta sử dụng một **bảng thưa** để tìm phần tử bên trái và bên phải gần nhất mà lớn hơn $a_i$.

> Ta tìm $L$ lớn nhất, mà $max (L, i - 1) \ge a_i$. Lúc này, $L$ là phần tử bên trái gần nhất mà lớn hơn $a_i$. Tương tự, ta tìm $R$ nhỏ nhất, tuy nhiên $max (i + 1, R) > a_i$.

Từ đây, đoạn con có $a_i$ được tính vào kết quả như là phần tử lớn nhất, có thể có biên trái từ $i$ tới $L$, và có biên phải từ $i$ tới $R$.

Vì vậy, có $(R - i + 1) \times (i - L + 1)$ đoạn con, thỏa mãn $a_i$ là phần tử lớn nhất.

Kết quả sẽ cộng thêm $(R - i + 1) \times (i - L + 1) \times a_i$.

Độ phức tạp: $O$ ($n \times log (n)$).

#### Subtask 4 + 5: $k \le 10$.

Ta duyệt một biến $gap$ từ $1$ tới $k$, với ý nghĩa: ta đang tính $a_i$ đóng góp vào kết quả bao nhiêu lần, khi $a_i$ là phần tử **lớn thứ $gap$ trong danh sách**. Định nghĩa về thứ tự sắp xếp các phần tử như mình đã định nghĩa ở trên.

Dễ thấy: Nếu ở bên trái, ta đã lấy $x$ phần tử lớn hơn $a_i$, vậy ở bên phải, ta sẽ lấy $y$ phần tử lớn hơn $a_i$.

Đầu tiên, ta tạo hai danh sách $L$ và $R$, mỗi danh sách có tối đa $K$ phần tử, với ý nghĩa:

- $L_j$ là chỉ số thứ $j$ gần $i$ nhất, mà $a[L[j]] > a[i]$.
- $R_j$ là chỉ số thứ $j$ gần $i$ nhất, mà $a[R[j]] > a[i]$.

> Như định nghĩa, danh sách $L$ sẽ luôn có chỉ số $i$.

Hai dãy này vẫn xây dựng bằng tìm kiếm nhị phân như subtask $3$.

Sau đó, ta duyệt từng phần tử của danh sách $L$, gọi là $L[j]$. Lưu ý, hai danh sách $L$ và $R$ đều đánh số từ $0$.

Ta đã có $j + 1$ số $> a[i]$. Vì vậy, ta cần có chính xác $gap - j - 1$ số $> a[i]$ ở bên phải. Nói cách khác, số cách chọn các chỉ số ở bên phải là $R[k - (gap - j - 1)] - i$.

Ở bên trái, để có đúng $j + 1$ số $> a[i]$, số cách chọn là $L[j] - L[j + 1]$.

Vì vậy, kết quả sẽ cộng thêm $(R[k - (gap - j - 1)] - i) \times (L[j] - L[j + 1]) \times a_i$.

Độ phức tạp: $O$ ($n \times k \times log (n)$).

> Nhận xét chung: Với mình, đây là một bài không khó về mặt ý tưởng, nhưng cần cài đặt khéo léo để tránh nhầm lẫn.

### Câu 5 - Lì xì (3 điểm)

> Tác giả: Nguyễn Hữu Nhật Quang

**Nhận xét 1:** Giả sử các tờ tiền mà Sunlight bỏ vào bao lì xì có mệnh giá lần lượt là $s_1 \le s_2 \le ... \le s_k$ thì các điều kiện sau phải thỏa mãn:

$$1 \ge s_1$$

$$1 + s_1 \ge s_2$$

$$1 + s_1 + s_2 \ge s_3$$

$$...$$

$$1 + s_1 + s_2 + ... + s_{k - 1} \ge s_k$$

**Nhận xét 2 (Subtask 1):** Ta có một thuật toán để tìm ra số tờ tiền tối thiểu cần bỏ thêm vào như sau:
- Đầu tiên sắp xếp dãy $a_1, a_2, ..., a_k$ là dãy các tờ tiền ban đầu. Đặt $s = 0$ là tổng giá trị các tờ tiền tính đến thời điểm hiện tại.
- Duyệt với mọi $i$ từ 1 đến $k$:
- Nếu $s + 1 < a_i$: thêm một tờ tiền mệnh giá $s + 1$ vào bao lì xì. Đặt $s = 2s + 1$. Lặp lại thao tác này cho đến khi $s + 1 \ge a_i$.
- Bỏ tờ tiền $a_i$ vào bao lì xì. Đặt $s = s + a_i$. Tờ tiền này không tính là tờ tiền bỏ thêm.

**Nhận xét 3:** Cách bỏ thêm tiền tối ưu sẽ bỏ thêm không quá một tờ có mệnh giá thuộc mỗi đoạn $[2^{i - 1}, 2^i - 1]$. Nhận xét này được rút ra từ nhận xét 2. Suy rộng ra, nếu ban đầu có một tờ tiền có mệnh giá $x$ trong nhóm các tờ tiền bỏ vào bao lì xì thì không cần phải bỏ thêm bất cứ tờ tiền có mệnh giá $y$ nào mà $2^{i - 1} \le x \le y < 2^i$.

Từ đây, ta có thể rút ra lời giải cho bài toán.

Chia các tờ tiền thành $60$ nhóm, mỗi nhóm là một đoạn $[2^{i - 1}, 2^i - 1]$. Với mỗi nhóm, ta quản lý hai thông tin:
- $min_i$: giá trị tờ tiền nhỏ nhất trong nhóm.
- $sum_i$: tổng giá trị các tờ tiền trong nhóm.

Ta có thể dễ dàng quản lý các giá trị này bằng cách dựng cây Segment Tree hoặc BIT.

Với mỗi sự kiện loại 1, sau khi lấy ra đủ các cặp $(min, sum)$, ta thực hiện thuật toán tương tự như ở nhận xét 2:
- Đặt $s = 0$.
- Duyệt $i$ từ $1$ đến $log_2(max(a_i))$:
- Nếu $s + 1 < min_i$: thêm một tờ tiền mệnh giá $s + 1$. Đặt $s = s + 1$.
- Đặt $s = s + sum_i$.

Độ phức tạp: $O(n \times log_2(n) \times log_2(a_i))$.

## Lời cảm ơn

Câu lạc bộ SQRT xin gửi lời cảm ơn đến tất cả những thành viên có đóng góp cho bộ đề cũng như lời giải này, bao gồm:
- Bạn Nguyễn Hữu Nhật Quang, THPT Chuyên Lê Quý Đôn, Đà Nẵng.
- Bạn Đặng Huy Hậu, THPT Chuyên Thăng Long, Đà Lạt.
- Bạn Hà Phước Vũ, THPT Chuyên Lê Quý Đôn, Đà Nẵng.
- Bạn Nguyễn Văn Minh, THPT Chuyên Lê Quý Đôn, Đà Nẵng.
- Bạn Huỳnh Anh Nhật, THPT Chuyên Lê Quý Đôn, Bình Định.
- Bạn Lê Kiến Thành, THPT Chuyên Lê Quý Đôn, Bình Định.
- Bạn Nguyễn Dĩ Thái, THPT Chuyên Nguyễn Du, Đắk Lắk.
- Bạn Hoàng Minh Anh, THPT Chuyên Nguyễn Du, Đắk Lắk.
- Bạn Chu Chính Hoàng, THPT Chuyên tỉnh Hà Giang.
- Bạn Nguyễn Hữu Phúc, THPT Chuyên Lê Quý Đôn, Quảng Trị.
- Bạn Hoàng Dương, THPT Chuyên Nguyễn Huệ, Hà Nội.
- Bạn Bùi Minh Nhật, THCS Lê Hồng Phong, Đà Nẵng.
- Bạn Mai Ngọc Phú, THPT Chuyên Lê Khiết, Quảng Ngãi.
- Bạn Trương Minh Đức, THPT Chuyên Nguyễn Chí Thanh, Đắk Nông.

Chúng mình xin cảm ơn một bạn ẩn danh đã donate thêm 200 nghìn đồng vào quỹ thưởng của contest.

Cuối cùng, chúng mình xin cảm ơn tất cả các bạn đã tham gia contest của chúng mình.