Boộ đề thi hsg quốc gia tin học

Đề thi ngày 1: PDF.

Link nộp bài: VOI2020. Các bạn cần vào group: VNOI - Vietnam Olympiad in Informatics ở codeforces trước nếu không vào được link contest.

Với các bài, nếu đề quá dài mình sẽ tóm tắt lại đại ý trước khi đi vào lời giải. Mình sẽ chủ yếu đi vào lời giải cho sub cuối cùng, nhưng sẽ nói sơ qua các cách vét điểm.

Bài 1: BONUS

Lời giải

Với \(k\) khá nhỏ, ta hoàn toàn có thể backtrack cách chọn, độ phức tạp: \(O(5^k)\). Cách code có thể đơn giản như sau:

//hàm calc(l, r, k) trả về giá trị tối ưu khi ta xử lý đoạn con [l, r] và còn lại k lượt chọn. Kết quả là calc(1, n, k) //hàm cost(x, y) trả về giá trị khi chọn cặp 2 lá bài x và y, đơn giản nó là abs(a[x] - a[y]) long long calc(int l, int r, int k) { if (l > r) { if (k == 0) return 0; //vì đề yêu cầu chọn ĐÚNG k cặp, nên nếu vẫn còn cách chọn thì trạng thái này không thỏa mãn //do đó ta return 1 giá trị cực bé để không bao giờ lấy kết quả này. return -INF; } long long best = -INF; if (l + 1 <= r) { //thực hiện cách chuyển 1: best = calc(l + 2, r, k - 1) + cost(l, l + 1); //thực hiện cách chuyển 2: best = calc(l, r - 2, k - 1) + cost(r, r - 1); //thực hiện cách chuyển 3: best = calc(l + 1, r - 1, k - 1) + cost(l, r); } //thực hiện cách chuyển 4: best = max(best, calc(l + 1, r, k)); //thực hiện cách chuyển 5: best = max(best, calc(l, r - 1, k)); return best; }

Cách code trên là 1 cách code backtrack, tất nhiên vẫn còn rất nhiều cách backtrack khác nhưng mình dùng cách này để dễ dàng tối ưu hơn.

Với subtask này mình cũng không biết trâu kiểu gì nữa.

Ở đây ta cải tiến thẳng từ thuật toán ở sub1. Ta nhận thấy hàm calc(l, r, k) sẽ cho ra kết quả như nhau nếu ta truyền vào cùng 1 bộ tham số. Do đó, với mỗi bộ (l, r, k), ta chỉ cần tính 1 lần duy nhất, các lần sau cứ lấy kết quả đã tính, cách này chính là đệ quy có nhớ. Bây giờ với thuật toán trên ta chỉ cần thêm có nhớ vào là AC. Độ phức tạp: \(O(n^2\times k)\), vì ta có số bộ (l, r, k) là \(O(n^2\times k)\), mỗi lần chuyển trạng thái có thể xem là \(O(1)\).

Code tham khảo: BONUS.cpp

Bài 2: BUS

Bài này anh Nghĩa có viết một solution rất đẹp bằng chia để trị, các bạn có thể xem ở: đây. Nhưng mình sẽ viết solution bằng chia căn, xem như là 1 cách tiếp cận khác. Lưu ý rằng dù theo cách tiếp cận nào, bài này là một bài rất khó để cài thuật chuẩn. Bài này có rất nhiều cách làm tham, trong giờ thi, chiến thuật tốt nhất là cài hết thuật tham xong merge các thuật đó lại với nhau, gần như không thể sinh test giết được.

Tóm tắt đề bài:

Cho 2 tập cạnh vô hướng, có trọng số: \(A\) và \(B\). Ta cần chọn ra một tập con các cạnh thuộc \(A\) và tập con các cạnh thuộc \(B\), sao cho:

1. Tổng trọng số của cạnh có trọng số lớn nhất trong mỗi tập con là nhỏ nhất.
2. Sử dụng các cạnh được chọn, ta có thể đi từ đỉnh 1 tới đỉnh \(n\).

Lời giải:

Trong tất cả các subtask: sort các cạnh mỗi loại theo trọng số tăng dần.

Ta đơn giản thì cần lần lượt thêm cạnh vào cho tới khi có đường đi từ 1 tới \(n\). Dùng disjoin-set có thể dễ dàng làm điều này. Ta cũng có thể dùng chặt nhị phân, dijkstra, …

Một nhận xét là khi ta dùng càng nhiều các cạnh loại \(B\), thì ta dùng càng ít các cạnh loại \(A\) (và ngược lại). Tới đây ta có thể dùng 2 con trỏ: Duy trì 1 con trỏ ở các cạnh loại \(A\), duyệt giới hạn các cạnh loại \(B\), sau đó kiểm tra có thể đi được từ 1 tới \(n\) hay không bằng BFS/DFS, rồi dựa vào đó mà cập nhật con trỏ trên các cạnh loại \(A\). Ta thực hiện đúng \(O(n)\) lần BFS/DFS nên độ phức tạp là \(O(n\times (n + m))\)

Do chỉ dùng 1 cạnh loại \(B\), ta nghĩ tới việc duyệt qua các cạnh (u, v) trong tập \(B\), sau đó kiểm tra xem nếu dùng cạnh này thì ta phải dùng cạnh loại \(A\) lớn nhất là bao nhiêu. Để làm được điều đó, ta cần tính ra 2 mảng: \(d1[u] =\) cạnh loại \(A\) lớn nhất cần dùng để đi từ đỉnh 1 tới đỉnh \(u\), \(dn[u]=\) cạnh loại \(A\) lớn nhất cần dùng để đi từ đỉnh \(u\) tới đỉnh \(n\). Việc tính 2 mảng trên có rất nhiều cách, 1 cách đơn giản là dùng Dijkstra.

Sau khi tính được 2 mảng trên, ta đơn giản duyệt qua các cạnh (u, v) thuộc \(B\), cập nhật kết quả với \(max(d1[u], dn[v]) + w(u, v)\), với \(w(u, v)\) là trọng số cạnh (u, v), nên nhớ là cạnh vô hướng nên ta kiểm tra luôn (v, u) nữa.

Đây là subtask cuối cùng, việc giải subtask này dựa vào cải tiến thuật toán từ sub2 bằng chia căn (cách này rất khó để code, mình chỉ nêu sơ về ý tưởng):

Ta chia tập các cạnh thuộc \(A, B\) thành các block có độ dài là căn. Sau đó tính mảng \(Fa[i] =\) block nhỏ nhất thuộc \(B\) để khi dùng các block không quá \(i\) thuộc \(A\) và các block không quá \(Fa[i]\) thì có đường đi từ 1 tới \(n\). Việc tính mảng \(Fa\) tương tự như cách làm ở sub2.

Sau khi có mảng \(Fa\), với mỗi block \(i\) ở \(A\), ta cần thực hiện một việc là với mỗi cạnh thuộc block \(i\) ở \(A\), ta cần tính chính xác xem cần dùng các cạnh nào thuộc \(B\), nếu tính trâu thì độ phức tạp quá lớn, nhưng nhờ mảng \(Fa\), ta đã biết số lượng cạnh cần thử không quá lớn (ta chỉ thử các cạnh thuộc block \(Fa[i]\)), chỉ cần thử \(O(\sqrt{m})\) cạnh. Ta lại tiếp tục dùng cách tương tự sub2 để tính tiếp. Với cách này, độ phức tạp để kiểm tra mỗi block là \(O(\sqrt{m} \times n)\), vì ta cần 2 con trỏ \(\sqrt{m}\) cạnh, và thực hiện BFS/DFS để kiểm tra. Ta lại có \(O(\sqrt{m})\) block nữa, do đó thuật này sẽ thành \(O(m\times n)\). Để tối ưu, ta cần tối ưu phần DFS. Ta nhận thấy khi thực hiện mỗi block, ta chỉ quan tâm tới \(O(\sqrt{m})\) đỉnh, vậy nên ta có thể nén các đỉnh này lại, độ phức tạp chỉ còn \(O(\sqrt{m})\) mỗi lần DFS. Chung quy thì độ phức tạp của nó là \(O(\sqrt{m} \times \sqrt{m}) = O(m)\) cho phần này.

Độ phức tạp: \(O(\sqrt{m} \times n)\) để tính mảng \(Fa\), \(O(m)\) cho phần kiểm tra còn lại.

Code tham khảo: BUS.cpp

Nhận xét:

Bài này quá khó để dùng thuật chuẩn, chiến thuật tốt nhất cho bài này trong phòng thi chính là dùng các thuật tham như chặt tam phân. Chứ việc cày offline bài này trong phòng thi không khác gì tự hủy cả. Bài này lúc cài thuật chia căn thì mình cũng sai rất nhiều. May mà có test để debug :v.

Các subtask cho bài này cũng rất khó, vì các subtask không bao nhau, ví dụ như sub 2 và 3 không liên quan gì nhau cả, nên có vét cũng phải cài rất mệt.

Bài 3: STARS

Tóm tắt đề bài:

Đa giác chuẩn là đa giác với các đỉnh nằm trong tọa độ grid, không tự cắt và có các cạnh song song với trục tọa độ. Cho \(n\) đa giác chuẩn, mỗi ngày, ta xoay \(n\) đa giác đi 90 độ, hỏi ngày thứ \(d\) thì tổng phần diện tích bị phủ bởi ít nhất 1 đa giác là bao nhiêu.

Lời giải:

Trước khi làm bài này, các bạn nên AC bài AREA trước. Với bài này, ta phải tinh ý nhận ra là với tập điểm cho trước, chỉ dựng được 1 hình đa giác chuẩn duy nhất, nên cái gọi là “diện tích lớn nhất” trong đề là trap. Và việc xoay hình cũng không ảnh hưởng gì tới bài toán.

Ừa thì nó là Area đó :v. Nhưng giới hạn nhỏ nên không cần segment tree, chỉ cần sweep line xong đếm trâu.

Y chang sub1, chỉ là thêm cái xoay hình thôi. Mà như đã nói, bài này cái xoay hình chỉ là phần nhỏ, không ảnh hưởng gì tới thuật toán.

Subtask này mình không nghĩ ra riêng thuật gì để giải cả, và nhiều người mình biết đều bảo thế. Khả năng cao đây là trap.

Tới đây thì ta cứ xoay hình, sau khi xoay xong thì cần dựng đa giác lên, việc dựng đa giác rất đơn giản: Với những tọa độ có cùng tọa độ \(x\), ta sort tăng dần theo tọa độ \(y\), sau đó những điểm ở vị trí lẻ (sau khi sort), sẽ nối với các đỉnh vị trí chẵn (ví dụ: 1-2, 3-4, 5-6, …). Tương tự với các điểm cùng \(y\). Sau đó những cạnh được nối sẽ tạo thành các cạnh của đa giác.

Vấn đề tiếp theo là để làm như bài Area, ta cần biết được cạnh của đa giác là cạnh thêm vào anh cạnh trừ đi, ví dụ với đa giác dưới đây thì cạnh AB là cạnh thêm vào, cạnh CD và EF lại là cạnh xóa đi:

Vậy làm sao ta có thể xác định được đâu là cạnh thêm vào, đâu là cạnh xóa đi? Ta có thể thực hiện duyệt qua từ đỉnh ở trái dưới, sau đó lần lượt men theo các cạnh mà đi hết đa giác, nếu 1 lúc nào đó ta đi hướng lên trên thì cạnh đó là cạnh +1, ngược lại, nếu đi xuống thì là -1. Sau đó thì chỉ cần xử lý trên segment tree như bài AREA là được.

Code tham khảo: STARS.cpp

Nhận xét:

Đây là một bài khó, đã thế đề còn chứa rất nhiều thông tin nhiễu, trap. Nếu để bị đánh lừa, mất thời gian suy nghĩ về những cái trap thì sẽ rất khó khăn.

Nhận xét ngày 1:

Ngoài bài 1 có vẻ rất dễ ra thì bài 2 và 3 đều yêu cầu một khối lượng code rất lớn. Code offline rất dễ nhầm. Bài 2 có thuật toán rất khó nghĩ, bài 3 thì dễ nghĩ ra thuật toán hơn nếu đã biết bài AREA, nhưng lại yêu cầu việc cài khá lằng nhằng, lại nhiều thông tin nhiễu.

Solution ngày 1: blog

Đề thi ngày 2: PDF

Link nộp bài: VOI2020. Các bạn cần vào group: VNOI - Vietnam Olympiad in Informatics ở codeforces trước nếu không vào được link contest.

Với các bài, nếu đề quá dài mình sẽ tóm tắt lại đại ý trước khi đi vào lời giải. Mình sẽ chủ yếu đi vào lời giải cho sub cuối cùng, nhưng sẽ nói sơ qua các cách vét điểm. Nếu các bạn có thắc mắc gì thì có thể comment vào post này hoặc nhắn tin cho mình.

Bài 4: LIGHT

• Tag: Greedy, 2D prefix sum

Tóm tắt đề bài

Có một ma trận \(m \times n\), mỗi ô mang giá trị từ 0 tới 2. Ta có \(k\) nút bấm có dạng \((r_i, c_i), (x_i, y_i)\). Khi bấm một nút thì toàn bộ các ô nằm trong ma trận con của nút đó được tăng giá trị lên 1 (trong modulo 3, nghĩa là 2 thì sẽ chuyển về 0). Nhiệm vụ của bạn là tìm số lần bấm ít nhất để toàn bộ ma trận có giá trị là 1, hoặc toàn bộ có giá trị là 2. Một điều kiện rất quan trọng là \((r_i, c_i)\) khác nhau với mọi $i$.

Lời giải

Một số nhận xét trước khi làm bài:

1. Thứ tự bấm các nút không quan trọng.
2. Số lần bấm 1 nút không quá 2 lần.

Subtask này nhiều cách để trâu lắm, dự trên nhận xét 2 ở trên, có thể sinh \(3^k\) cách bấm rồi kiểm tra.

Hãy xem xét cách biến đổi toàn bộ bảng về một giá trị \(t\). Ta sẽ cố gắng biến đổi ô \((1, 1)\) về \(t\), sau đó là ô \((1, 2), (1, 3), ..., (1, n)\), sau đó tiếp tục tới hàng thứ 2, 3, …

Xét ô \((1, 1)\), rõ ràng duy nhất chỉ có nhiều nhất một nút bấm ảnh hưởng tới nó, vậy nếu ô \((1, 1)\) mà khác giá trị \(t\), rõ ràng ta cần phải bấm (và ta biết chính xác là cần phải bấm bao nhiêu lần), còn nếu không có nút bấm thì rõ ràng không thể biến toàn bộ bảng về giá trị \(t\). Điều này thực hiện được là nhờ điều kiện tất cả \((r_i, c_i)\) của mọi truy vấn là phân biệt (nếu không có điều kiện đó thì mình cũng không biết bài này làm thế nào).

Sau khi bấm xong ở ô \((1, 1)\) thì ta xem như là xóa nó đi, tương tự sang ô \((1, 2)\) cũng chỉ có nhiều nhất 1 nút bấm ảnh hưởng tới nó. Tiếp tục quy nạp thì ta sẽ xét được hết bảng.

Do giới hạn nhỏ, nên mỗi lần bấm nút ta có thể thực hiện duyệt qua toàn bộ ô được ảnh hưởng bởi nút bấm đó và điều chỉnh lại giá trị.

Ở subtask này thì việc duyệt qua toàn bộ ô bị ảnh hưởng là không khả thi, và hiển nhiên là ta cần phải optimize chỗ này, ta xem xét kĩ hơn ở những việc cần làm:

1. Cập nhật toàn bộ ô trong một hình chữ nhật lên một giá trị \(t\)
2. Tính giá trị tại một ô.

Tới đây thì nhiều bạn dùng cây Fenwick tree 2D để thực hiện các truy vấn này, độ phức tạp là \(O(m \times n \times log(m) \times log(n))\).

Nhưng nếu để ý hơn thì ta nhận thấy là ở các truy vấn lấy giá trị tại một ô, các ô được lấy “tăng dần” (ta lấy ô \((1, 1)\) rồi tới ô \((1, 2), (1, 3), \dots\), do đó ta chỉ cần một mảng prefix sum 2D là đủ, và dùng thêm trick này.

Độ phức tạp là \(O(m \times n)\)

Code tham khảo: LIGHT.cpp

Bài 5: BUILDING

Tóm tắt đề bài:

Có một số hình chữ nhật trong mặt phẳng tọa độ \(Oxy\), các hình chữ nhật có thể chạm vào nhau nhưng không đè lên nhau. Ta tạo một đồ thị vô hướng, với các đỉnh là các hình chữ nhật, 2 đỉnh có cạnh nối khi và chỉ khi 2 hình chữ nhật tương ứng chạm nhau. Trong đồ thị mới có thể có một số cầu, khi xóa cây cầu đó đi thì một thành phần liên thông sẽ bị tách ra làm 2, gọi số lượng đỉnh 2 bên lần lượt là \(A\) và \(B\), ta cần tìm giá trị \(\|A-B\|\) nhỏ nhất.

Lời giải:

Bài này phần khó nhất là việc dựng đồ thị lên, còn việc tìm \(\|A-B\|\) nhỏ nhất là bài khá cơ bản rồi. Các bạn có thể làm bài REFORM ở group VNOI - Vietnam Olympiad in Informatics để rõ hơn cái kỹ thuật này. Nên ở mỗi subtask mình sẽ chú ý vào việc dự đồ thị hơn.

Các nhận xét trước khi làm bài:

1. Đồ thị trong bài là đồ thị phẳng, nên số lượng cạnh không quá \(3\times n\), đọc thêm về đồ thị phẳng ở đây
2. Một điểm thì có nhiều nhất 4 hình chữ nhật chứa có.

Ở subtask này ta có thể duyệt qua mọi cặp hình chữ nhật rồi xem nó có kề nhau hay không.

Ở subtask này, do tọa độ không hề lớn, nên với mỗi tọa độ ta có thể biết được những hình chữ nhật nào chứa điểm này, từ đó dựng cạnh. Ta có thể áp dụng kỹ thuật tổng 2D giống bài 4, nhưng ở đây thay vì tổng thì là một set các điểm.

Ta xét một bài toán đơn giản hơn: có \(n\) đoạn thẳng trên trục \(Ox\), hãy in ra các cặp đoạn thẳng có điểm chung.

Bài toán trên thì có thể giải đơn giản bằng sweep line và set (đừng sợ chữ “sweep line”, nó thật ra chỉ là duyệt qua các tọa độ tăng dần thôi :v):

1. Tách các đoạn thẳng làm 2 đầu, tạm gọi là đầu mở và đóng.
2. Duyệt các tọa độ tăng dần, nếu ta gặp đầu mở, ta ném nó vào set. Nếu ta gặp đầu đóng, rõ ràng đầu này sẽ có điểm chung với toàn bộ các đầu mở đang nằm trong set, vậy nên ta in các cặp đó ra, và xóa đầu đóng tương ứng.

Quay về bài toán gốc, thì thật sự nó cũng giống như bài toán mình vừa nói, mỗi hình chữ nhật bạn có thể xem nó như là 4 đoạn thẳng, tổng cộng có \(n \times 4\) đoạn thẳng. Ta xét các đoạn thẳng có cùng tọa độ \(x\) (hoặc \(y\)) rồi tìm những cặp đoạn thẳng có điểm chung. Ta không sợ số cặp có điểm chung lớn, vì số cạnh thật sự của đồ thị không vượt quá \(3 \times n\)

Độ phức tạp của việc dựng đồ thị là \(O(nlogn)\) (mất log cho phần sort các tọa độ tăng dần), độ phức tạp của phần tìm \(\|A-B\|\) là \(O(n)\).

Code tham khảo: BUILDING.cpp

Bài 6: EQUAKE

Tóm tắt đề bài:

Có một cây gồm \(n\) nút, có trọng số, trên mỗi nút \(u\) có \(p_u\) nhân viên, và có một xe có thể chở \(c\) nhân viên trong 1 chuyến, \(c\) là số cố định cho toàn bộ nút. Để chuyển \(x\) nhân viên từ nút \(i\) tới nút \(j\) (kề nhau) thì tốn chi phí là \(\lceil \frac{x}{c} \rceil \times d(i, j)\), với \(d(i, j)\) là trọng số cạnh nối giữa \(i, j\). Tính tổng chi phí bé nhất để di chuyển nhân viên sao cho lượng nhân viên chênh lệch giữa toàn bộ các nút là nhỏ nhất.

Lời giải:

Tạm gọi \(S\) là tổng số nhân viên trên toàn bộ nút, \(m = S \% n\) Nhận xét:

1. Nếu \(m=0\) thì ở kết quả, toàn bộ nút có lượng nhân viên bằng nhau.
2. Ngược lại thì có \(m\) nút có số lượng nhân viên là \(HI = \lfloor \frac{S}{n} \rfloor + 1\), các nút còn lại có số lượng nhân viên là \(LOW = \lfloor \frac{S}{n} \rfloor\)

Với \(n=3\) thì chỉ là xét linh tinh xem mỗi nút có bao nhiêu nhân viên thôi :v

Cho đơn giản thì ta xem cây nối với nhau theo \(1-2-3-4-...-n\)

Xét trường hợp \(m=0\) (mọi nút có cùng lượng nhân viên ở kết quả cuối cùng). Xem như ta đứng ở nút 1, và ta bị thiếu nhân viên, rõ ràng ta cần phải lấy nhân viên ở nút 2. Ngược lại nếu ta dư nhân viên thì ta cần đẩy lượng nhân viên đó sang nút 2. Tương tự khi ta xét tới nút 2, lúc này nút 1 chắc chắn đã đủ nhân viên rồi, ta xét tương tự thì cũng sẽ biết được nút 2 cần lấy hay đưa nhân viên tới nút 3, …

Nhưng nếu \(m \neq 0\), thì ta còn phải xác định được nút nào cần có nhiều nhân viên hơn nút còn lại. Tới đây thì ta dùng quy hoạch động:

• Gọi \(F(u, i)\) là tổng chi phí bé nhất để di chuyển nhân viên sao cho trong các nút từ 1 tới \(u\) đã có \(i\) nút có \(HI\) nhân viên. Lúc này kết quả là \(F(n, m)\).
• Việc chuyển trạng thái thì cũng khá đơn giản, ở nút \(u\) ta chỉ có 2 option là:
  1. Hoặc nút \(u + 1\) có \(HI\) nhân viên: chuyển qua trạng thái \(F(u + 1, i + 1)\)
  2. Hoặc nút \(u + 1\) có \(LOW\) nhân viên: chuyển qua trạng thái \(F(u + 1, i)\).

Việc tính chi phí chuyển thì do ta biết đượng số lượng nhân viên cần thiết của trạng thái \(F(u, i)\) (chính bằng \(u * LOW + i\)), nên ta biết được là ở đó đang dư hay thiếu nhân viên, từ đó biết là tối chi phí di chuyển như thế nào.

Độ phức tạp là \(O(n \times m) = O(n^2)\)

Subtask này thì từ subtask 2 ta có thể chuyển nó thành DP trên cây (mọi người hay gọi là Knapsack on tree). \(F(u, i)\) là tổng chi phí bé nhất để di chuyển nhân viên sao cho trong các nút ở cây con gốc \(u\) thì có \(i\) nút có \(HI\) nhân viên. Tạm xem gốc của cây là 1 thì kết quả là \(F(1, m)\).

Việc tính \(F\) thì nó đơn thuần là knapsack rồi, nhưng khó ở chỗ là nếu làm không khéo thì chỗ DP nó sẽ là \(O(n^3)\), các bạn có thểm tham khảo link này để tham khảo cách làm \(O(n^2)\).

Bài này còn một cái yêu cầu là truy vết nữa, thật sự lúc code bài này mình code chưa tới 30p là xong phần tính kết quả rồi, còn phần truy vết mình làm mãi luôn tại mình ngu :v. Các bạn nên làm bài PTREE trước để xem cách truy vết knapsack trên cây nhé.

Code tham khảo: EQUAKE.cpp

Nhận xét ngày 2:

So với ngày 1 thì mình thấy ngày 2 có phần dễ nghĩ ra thuật hơn, ví như bài 5 mình thấy khi đọc vào rõ ràng là biết ta cần phải dựng đồ thị lên rồi làm cầu các thứ. Còn bài 6 đọc vào là biết phải làm knapsack trên cây rồi. Nhưng đề ngày 2 khó ở chỗ là khá nặng phần cài đặt cũng như cần nhiều kiến thức “lạ” (lạ ở đây là ít gặp ở VOI), như DP trên cây, sweep line (bài 5). Chung quy mình thấy ngày 1 khó hơn ngày 2.

Có một sự thật là lúc làm VNOI Online 2020, tụi mình đã định cho một bài DP knapsack trên cây, cũng dùng cái kỹ thuật giảm xuống \(O(n^2)\) luôn, nói chung cài đặt y chang bài 6, nhưng bọn mình để nó ở bài 4. Rồi sau đó vì 1 số lý do mà không dùng bài đó nữa. Tiếc thật sự :v.

Xin chào, hôm nay mình hơi chán nên ngồi viết blog, lần này là một bài toán thao tác khá là nổi tiếng trên cấu trúc dữ liệu segment tree, Fenwick tree nhưng vẫn chưa có nhiều nguồn nói về nó bằng tiếng Việt. Cái tên gọi “cập nhật bậc thang”/”update bậc thang” là mình thường nghe những người xung quanh nói thôi chứ cũng không có tên gọi nào chính thức cho nó.

Tuy đây là một thao tác khá nổi tiếng, nhưng để học nó cần trước một số kiến thức cơ bản sau đây:

• Segment tree (kết hợp lazy), Fenwick tree.

Các bạn có thể học Segment tree ở đây và Fenwick tree ở đây trước khi đọc thêm bài này.

Bài toán 1

Cho một mảng các số nguyên \(a\) có \(n\) phần tử (ban đầu các phần tử khởi tạo bằng 0). Có \(q\) truy vấn có dạng:

• \(u\) \(v\): tăng \(a[u]\) lên 1, tăng \(a[u + 1]\) lên 2, tăng \(a[u + 2]\) lên 3, …, tăng \(a[v]\) lên \((v - u + 1)\) Sau khi thực hiện \(q\) truy vấn, ta cần in ra mảng \(a\).

Cách giải

Nếu như truy vấn chỉ đơn giản là tăng các phần tử trong đoạn lên một hằng số thì ta có thể dễ dàng thực hiện bằng cách:

• Với mỗi truy vấn \((u, v)\), ta thực hiện \(a[u]\) += \(x; a[v + 1]\) -= \(x\).
• Sau khi thực hiện xong các truy vấn, ta gán \(a[i]\) += \(a[i - 1]\) là xong.

Ở trên là một trick mà ai cũng biết, nếu không biết thì cũng có thể làm bằng segment tree hoặc Fenwick tree.

Nhưng với bài toán này, các phần tử được tăng lên theo cấp số cộng (công sai là 1), chứ không phải là hằng số.

Xét truy vấn \((u, v)\), việc cập nhật được thực hiện như sau:

• \(a[u]\) += \(1\)
• \(a[u + 1]\) += \(2\)
• \(a[u + 2]\) += \(3\)
• …
• \(a[v]\) += \((v - u + 1)\)

Cộng \(0 = (u - 1) - (u - 1)\) vào vế phải của tất cả các phép biến đổi trên.

• \(a[u]\) += \((1 + (u - 1)) - (u - 1) \Leftrightarrow a[u]\) += \(u - (u - 1)\)
• \(a[u + 1]\) += \((2 + (u - 1)) - (u - 1) \Leftrightarrow a[u + 1]\) += \((u + 1) - (u - 1)\)
• \(a[u + 2]\) + = \((3 + (u - 1)) - (u - 1) \Leftrightarrow a[u + 2]\) += \((u + 2) - (u - 1)\)
• …
• \(a[v]\) += \(((v - u + 1) + (u - 1)) - (u - 1) \Leftrightarrow a[v]\) += \(v - (u - 1)\)

Tới đây ta có thể nhận thấy điều sau: Mỗi truy vấn \((u, v)\) tương ứng với 2 loại truy vấn khác:

1. Giảm (trừ) tất cả các phần tử trong đoạn \([u, v]\) đi một lượng \((u - 1)\).
2. Với mỗi phần tử \(i\) trong đoạn \([u, v]\), tăng \(a[i]\) lên \(i\).

Rõ ràng thứ tự thực hiện của các truy vấn mới là không quan trọng, bạn có thể thực hiện hàng loạt các truy vấn 1 trước, rồi sau đó mới thực hiện truy vấn 2 (hoặc ngược lại). Bây giờ ta thấy truy vấn 1 chính là truy vấn cơ bản mà mình đã nói ở phần trên (tăng cả đoạn lên một hằng số). Vậy vấn đề còn lại là giải quyết truy vấn 2.

Việc xử lý truy vấn 2 có thể làm giống code sau:

Để rõ hơn thì các bạn có thể xem pseudo code sau đây.

Với mọi truy vấn 2 [u, v]: Với mọi i nằm trong đoạn [u, v] a[i] += i In ra mảng a

Với truy vấn 2, phần tử \(i\) luôn được tăng lên một lượng cố định là \(i\). Vậy thì thay vì ta thực hiện tăng lên một lượng cố định mỗi truy vấn, ta chỉ cần ĐẾM số lần phần tử \(i\) được tăng, sau đó lấy \(i * cnt[i]\) chính là lượng mà phần tử \(i\) cần tăng:

Với mọi truy vấn 2 [u, v]: Với mọi i nằm trong đoạn [u, v]: cnt[i] += 1 Với i trong đoạn [1, n]: a[i] += i * cnt[i]; In ra mảng a

Hai code mình vừa trình bày đều có độ phức tạp như nhau, nhưng ở code 2, thì việc tăng cả tất cả các phần tử của mảng \(cnt\) lên 1 thì nó cũng giống với truy vấn cơ bản ban đầu (tăng cả đoạn lên một hằng số), nên ta có thể tăng tốc nó lên được. Cuối cùng thì ta có một cái code na ná thế này <(“)

for (moi truy van [u, v]) { //Tách ra làm 2 truy vấn. //Truy vấn 1: giảm đoạn [u, v] đi (u - 1) b[u] -= u - 1; b[v + 1] += u - 1; //Truy vấn 2: a[i] += i -> cnt[i] += 1 cnt[u] += 1; cnt[v + 1] -= 1; } for (int i = 1; i <= n; ++i) { b[i] += b[i - 1]; cnt[i] += cnt[i - 1]; a[i] = b[i] + i * cnt[i]; }

Tới đây thì ta xong bài toán cơ bản đầu tiên. Độ phức tạp \(O(n)\)

Bài toán 2

Cho một mảng các số nguyên \(a\) có \(n\) phần tử (ban đầu các phần tử khởi tạo bằng 0). Có \(q\) truy vấn thuộc 1 trong 2 dạng:

• \(1\) \(u\) \(v\): tăng \(a[u]\) lên 1, tăng \(a[u + 1]\) lên 2, tăng \(a[u + 2]\) lên 3, …, tăng \(a[v]\) lên \((v - u + 1)\)
• \(2\) \(i\): in ra giá trị \(a[i]\)

Bài toán này thì cũng giống với bài toán ban đầu, chỉ khác là có thêm truy vấn yêu cầu in ra giá trị \(a[i]\). Rõ ràng để biết được giá trị \(a[i]\) thì ta cần biết được 2 giá trị là \(b[i]\) và \(cnt[i]\), thì bài toán có thể phát biểu lại như sau: Có 3 loại truy vấn:

• Giảm giá trị các phần tử trong đoạn \([u, v]\) của mảng \(b\) đi \((u-1)\)
• Tăng giá trị các phần tử trong đoạn \([u, v]\) của mảng \(cnt\) lên 1
• Tính giá trị \(b[i] + i * cnt[i]\).

Các truy vấn này các bạn có thể giải quyết bằng 2 cây Fenwick, một cây để quản lý \(b\), một cây để quản lý \(cnt\), vậy là xong (hoặc làm bằng cây segment cũng được). Độ phức tạp \(O(nlogn)\).

Bài toán 3

Cho một mảng các số nguyên \(a\) có \(n\) phần tử (ban đầu các phần tử khởi tạo bằng 0). Có \(q\) truy vấn thuộc 1 trong 2 dạng:

• \(1\) \(u\) \(v\): tăng \(a[u]\) lên 1, tăng \(a[u + 1]\) lên 2, tăng \(a[u + 2]\) lên 3, …, tăng \(a[v]\) lên \((v - u + 1)\)
• \(2\) \(u\) \(v\): in ra tổng \(\sum_{i=u}^{v} a[i]\)

Mình lười rồi nên dành cho bạn đọc vậy <(“). Hint là các bạn có thể dùng lazy để tính \(i*cnt[i]\).

Các bạn có thể nộp bài ở đây: Polynomial Queries - CSES 1736

Xin chào, hôm nay mình tiếp tục chán nên tiếp tục viết blog. Lần này tiếp tục viết về cấu trúc dữ liệu, trong bài này mình sẽ nói về một truy vấn thường gặp ghi dùng segment tree, nó có tên gọi là chặt nhị phân trên segment tree, tiếng anh thì có tên là “Binary search over/on segment tree”, hoặc là “walk on segment tree”. Do hôm qua định chỉ một bạn dùng cái này nhưng mình google không tìm được tutorial nói về nó nên mình viết luôn. Mấy cái tên thì là mình nghe mọi người gọi nên gọi theo thôi :v. Cũng có thuật toán chặt nhị phân trên Fenwick tree nhưng có thể mình sẽ nói ở blog khác.

Tuy đây là một thao tác khá thường gặp, nhưng để học nó cần trước kiến thức cơ bản về segment tree và chặt nhị phân. Các bạn có thể học Segment tree ở đây.

Bài toán 1

Cho một mảng các số nguyên \(a\) có \(n\) phần tử. Có \(q\) truy vấn có dạng:

• \(k\): tìm \(i\) nhỏ nhất sao cho \(a[i] \le k\)

Cách giải

Ta nhận thấy do \(a[i] \le k\) và \(i\) nhỏ nhất, cho nên \(a[j] > k\) với mọi \(1 \le j < i\).

Do đó, \(min(a[1], a[2], ..., a[i]) = a[i]\).

Đặt \(f[i] = min(a[1], a[2], ..., a[i])\).

Nhận xét 1: Việc tìm \(i\) nhỏ nhất sao cho \(a[i] \le k\) cũng tương ứng với việc tìm \(i\) nhỏ nhất sao cho \(f[i] \le k\).

Nhận xét 2: \(f[i - 1] \ge f[i]\). Nói cách khác, \(f\) là mảng không tăng.

Vậy bài toán có thể phát biểu lại như sau:

Cho một mảng các số nguyên \(f\) đã “sắp xếp” giảm dần, có \(q\) truy vấn có dạng:

• \(k\): tìm \(i\) nhỏ nhất sao cho \(f[i] \le k\).

Rõ ràng bài toán này chỉ là bài toán chặt nhị phân cơ bản, vì mảng \(f\) đã được “sắp xếp”. Tới đây ta có thể trả lời các truy vấn trong độ phức tạp \(O(logn)\). Code thì nó sẽ giống giống thế này:

int query(int k) { int l = 1, r = n, pos = -1; while (l <= r) { int mid = (l + r) / 2; if (f[mid] <= k) pos = mid, r = mid - 1; else l = mid + 1; } return pos; }

Bài toán 2

Cho một mảng các số nguyên \(a\) có \(n\) phần tử. Có \(q\) truy vấn có dạng:

• \(i\) \(x\): gán \(a[i] = x\).
• \(k\): tìm \(i\) nhỏ nhất sao cho \(a[i] \le k\)

Bài toán này giống bài toán 1, nhưng có thêm truy vấn cập nhật phần tử, điều này làm cho mảng \(f\) bị thay đổi. Ta có thể sửa lại yêu cầu bài toán một chút, là có 3 loại truy vấn:

• \(i\) \(x\): gán \(a[i] = x\).
• \(k\): tìm \(i\) nhỏ nhất sao cho \(a[i] \le k\)
• \(i\): tính \(min(a[1], a[2], ..., a[i])\).

Rõ ràng truy vấn 1 và 3 có thể thực hiện bằng segment tree với độ phức tạp \(O(logn)\), vậy thì tới đây bài toán quay về bài toán 1, chỉ có điều khi ta cần tính \(f[i]\) thì ta phải gọi hàm trên segment tree để lấy min, độ phức tạp cho việc trả lời truy vấn 2 là \(O(log^2n)\):

int query(int k) { int l = 1, r = n, pos = -1; while (l <= r) { int mid = (l + r) / 2; if (getMin(1, mid) <= k) pos = mid, r = mid - 1; else l = mid + 1; } return pos; }

Nhưng nếu chỉ dừng ở đây thì đã không cần blog này rồi <(“). Ta nhìn một chút vào cấu trúc cây segment tree (quản lý min) dưới dây:

Giả sử ta cần tìm vị trí đầu tiên có giá trị không vượt quá \(2\). Ta đứng từ gốc, xét 2 con trái phải lần lượt có giá trị là 3 và 2:

Do ta đang cần tìm giá trị không vượt quá 2, nên ta chắc chắn kết quả không nằm trong cây con bên trái (vì min của cây con này là 3, suy ra mọi phần tử được quản lý bởi cây con này đều lớn hơn 2). Và do cây con phải có giá trị là 2, suy ra kết quả chắc chắn nằm cây con này, ta đệ quy xuống cây con bên trái:

Tương tự, cây con này có 2 cây con trái và phải, cả 2 đều có giá trị là 2, nghĩa là luôn tồn tại ít nhất một số có giá trị bằng 2 trong cả 2 cây con này, từ đó suy ra cả 2 cây con đều có thể chứa kết quả ta cần tìm. Nhưng do ta muốn tìm vị trí có \(i\) bé nhất, nên ta sẽ ưu tiên đi vào cây con bên trái (cây con này quản lý các vị trí nhỏ hơn các vị trí của cây con phải).

Lập luận tương tự thì ta sẽ biết được kết quả nằm ở cây con trái, lúc này cây chỉ quản lý duy nhất một phần tử nên ta có thể kết luận luôn vị trí cần tìm.

Đoạn code mẫu cho việc tìm vị trí đầu tiên không vượt quá số \(k\) có thể code như sau, lưu ý, trong code này mình xem mảng \(st\) là mảng lưu giá trị của segment tree, 3 tham số \(root, l, r\) thể hiện cho việc nút \(root\) quản lý một đoạn từ \([l, r]\):

int query(int root, int l, int r, int k) { if (st[root] > k) return -1; //nếu cả đoạn [l, r] đều lớn hơn k thì không thỏa mãn if (l == r) return l; //khi đoạn có 1 phần tử thì đó là kết quả int mid = (l + r) / 2; if (st[root * 2] <= k) //nếu min cây con trái không vượt quá k return query(root * 2, l, mid, k); //ngược lại thì kết quả nằm ở bên cây con phải return query(root * 2 + 1, mid + 1, r, k) } //cout << query(1, 1, n, k);

Hàm trên có độ phức tạp là \(O(logn)\), bởi vì mỗi lần đệ quy chỉ gọi ra một hàm khác (từ một nút chỉ đi qua một nút khác), và số lần gọi đệ quy chính bằng độ cao của segment tree. Tới đây ta đã xong bài toán 2.

Lưu ý là, với các bài toán mà truy vấn cập nhật là một đoạn (thay vì một phần tử như bài toán 2), thì việc cài đặt hàm \(query\) ở trên vẫn không đổi, chỉ có thêm vào lazy trước khi xét 2 cây con trái phải, mình xin giành cho bạn đọc vậy.

Bài toán 3:

Cho một mảng các số nguyên \(a\) có \(n\) phần tử. Có \(q\) truy vấn có dạng:

• \(i\) \(x\): gán \(a[i] = x\).
• \(L\) \(k\): tìm \(i\) nhỏ nhất sao cho \(L \le i\) và \(a[i] \le k\)

Bài toán này khó hơn bài toán 2 một chút, đó là có thêm một cận dưới của $i$ (thay vì tìm \(i\) bé nhất, thì ta cần tìm \(i\) bé nhất nhưng lớn hơn một số nào đó), ta có thể thay đổi code một tí như sau:

int query(int root, int l, int r, int lowerbound, int k) { if (st[root] > k) return -1; //nếu cả đoạn [l, r] đều lớn hơn k thì không thỏa mãn if (r < lowerbound) return -1; //ta chỉ xét những vị trí không nhỏ hơn lowerbound if (l == r) return l; //khi đoạn có 1 phần tử thì đó là kết quả int mid = (l + r) / 2; int res = -1; if (st[root * 2] <= k) //nếu min cây con trái không vượt quá k res = query(root * 2, l, mid, lowerbound, k); //nếu cây con trái không tìm được kết quả <=> min nằm ngoài lowerbound //thì ta sẽ tìm kết quả ở cây con phải if (res == -1) res = query(root * 2, mid + 1, r, lowerbound, k); return res; } //cout << query(1, 1, n, l, k);

Code này có một chút lạ, khác so với code ở bài toán 2 một chút, ở bài toán 2, thì mỗi lần đệ quy chỉ thăm duy nhất một con trái hoặc phải, nhưng ở code mới này thì một lần đệ quy có thể phải thăm cả 2 con, lý do là vì có thể một cây con nó có min không vượt quá \(k\), nhưng vị trí đạt min nó có thể nhỏ hơn lowerbound, vì thế ta phải tìm ở cây con khác.

Để đánh giá độ phức tạp code trên thì hơi rườm rà một chút, nhưng nó vẫn là \(O(logn)\). Đại ý là ta có thể chứng minh số lần mà \(r < lowerbound\) sẽ không quá \(O(logn)\).

Đề thi ngày 1: PDF.

Các bạn có thể xem video lời giải của VNOI ở đây.

Nguồn đề mình lấy của bạn Trí Phan ở trong Discord của VNOI.

Bài 1: NOEL

Tóm tắt

Cho một hoán vị \(a\) gồm \(n\) phần tử. Cần chọn ra \(b\) là dãy con của \(a\) gồm \(2 \times m\) số sao cho \(\lvert b[i] - b[i + m] \rvert \le D, \forall 1 \le i \le m\) và \(m\) lớn nhất.

Lưu ý: \(1 \le D \le 5\)

Lời giải

Do \(n\) nhỏ nên ta có thể sinh nhị phân ra toàn bộ dãy con của \(a\), sau đó kiểm tra điều kiện đề bài. Độ phức tạp là \(O(2^n * n)\).

Việc chọn ra dãy \(b\) độ dài \(2 \times m\) cũng giống như là việc chọn ra 2 dãy con \(c\), \(d\) với độ dài \(m\) và thoả điều kiện phần tử cuối cùng của \(c\) đứng trước phần tử đầu tiên của \(d\) trong hoán vị \(a\). Ví dụ \(b\) là: \([4, 5, 1, 3]\) thì \(c\) là \([4, 5]\) và \(d\) là \([1, 3]\), giống như việc bạn chia dãy \(b\) ra làm 2 nửa trái phải ấy.

Khi tới đây, nhiều bạn nghĩ tới bài này là 1 bài quy hoạch động cơ bản giống như bài tìm dãy con chung dài nhất (khi \(D = 0\) thì đúng là nhìn giống thật), và ra một công thức quy hoạch động kiểu: \(F[i][j]\) là “dãy con chung” dài nhất khi xét tới vị trí \(i, j\) của mảng \(a\), cách làm như sau:

Độ phức tạp của thuật toán này là \(O(n^2)\).

Nhưng thuật toán trên không đúng, vì từ công thức trên, các bạn đã “vô tình” xem \(a\) là thành 2 mảng riêng, và không còn giữ điệu điều kiện giữa \(c\) và \(d\) mà mình đã nói ở trên.

Vậy tới đây ta phải làm sao? Đơn giản thôi, ta chia dãy \(a\) ra thành 2 dãy trái và phải, và quy hoạch động trên 2 dãy đó thay vì dãy \(a\) ban đầu. Việc chia dãy \(a\) ra thì có \(n\) cách chia (giống như đặt vách ngăn ở giữa mảng), với mỗi cách chia thì ta lại quy hoạch động mất \(O(n^2)\), do đó độ phức tạp là \(O(n^3)\), đủ tốt cho subtask này.

Với subtask này, việc dùng thuật toán vừa trình bày ở trên sẽ không khả thi, thuật toán trên gồm 2 bước:

1. Chia dãy \(a\) ra làm 2 dãy trái phải (có \(O(n)\) cách chia)
2. Với mỗi cách chia, ta phải quy hoạch động trong \(O(n^2)\)

Ta có thể thấy thuật toán trên chưa tận dụng được điều kiện của đề bài: \(D\) nhỏ, do đó ta có thể nghĩ tới một hướng tối ưu mà có tận dụng tới điều kiện trên.

Xem lại 2 bước trên, bước 1 rất khó để tối ưu xuống, do đó ta nên tập trung vào bước 2 để giảm độ phức tạp thuật toán.

Nhìn kỹ lại công thức QHĐ:

Ta có thể thấy với mỗi \(i\), chỉ có nhiều nhất \(2 * D\) chỉ số \(j\) thoả mãn \(\lvert a[i] - a[j] \rvert \le D\) (vì \(a\) là hoán vị). Ta sẽ tận dụng điều này để tối ưu thuật toán.

Ta nhìn vào test này, với \(D=1\)

Dãy \(a\): \([1, 5, 3, 7, 2, 8, 6, 4]\). Giả sử ta phân dãy \(a\) ra thành: \([1, 5, 3, 7 \mid 2, 8, 6, 4]\) thì:

• Số 1 có thể ghép được với số 2 (ở vị trí 5)
• Số 5 có thể ghép được với số 6, 4 (ở vị trí 7, 8)
• Số 3 có thể ghép được với số 2, 4 (ở vị trí 5, 8)
• Số 7 có thể ghép được với số 8, 6 (ở vị trí 6, 7)

Việc chọn ra dãy \(b\) chính là chọn từng số bên trái và ghép với số bên phải sao cho các vị trí được chọn ở bên phải tạo thành dãy con tăng. Ví dụ ta chọn các cặp số (1, 2) và (5, 4), thì ta có thể thấy vị trí của số 2 và 4 (là 5 và 8) tạo thành 1 dãy con tăng. Lại ví dụ ta chọn các cặp số (1, 2), (5, 6) và (3, 4), vị trí của các số 2, 6, 4 (là 5, 7, 8) tạo thành 1 dãy con tăng.

Ta có thể phát biểu bài toán theo cách này: ta có một mảng gồm nhiều đoạn, ở mỗi đoạn ta cần chọn ra nhiều nhất 1 số, sao cho các số được chọn ra phải là dãy con tăng.

Bài toán này thì liên quan gì tới bài toán cũ của chúng ta?

Với mỗi số bên trái, sẽ có một số vị trí bên phải (không quá \(2\times D\)) có thể ghép được với số đó, thì ta xem các vị trí này là thành một “đoạn”. Ví dụ vẫn với cách phân dãy \(a\) trên, thì mảng gồm các đoạn là:

\([5 \mid 7, 8 \mid 5, 8 \mid 6, 7]\) (| biểu thị cho phân tách đoạn, lưu ý mảng này lưu vị trí của số trong mảng \(a\) chứng không phải lưu giá trị).

Tới đây, việc chọn các cặp số (1, 2), (5, 6) và (3, 4) từ dãy \(a\) (ứng với vị trí 5, 7, 8 ở bên phải) cũng ứng với dãy con tăng ở mảng trên và thoả điều kiện mỗi đoạn chỉ được chọn nhiều nhất 1 số.

Vậy làm sao để giải quyết bài toán tìm dãy con tăng của mảng có nhiều đoạn, mà mỗi đoạn không được chọn nhiều số? Liệu với thuật toán tìm dãy con tăng mà ta thường dùng, có cách nào để đảm bảo việc mỗi đoạn chỉ chọn nhiều nhất 1 số hay không? Câu trả lời là có, và cách làm là: ở mỗi đoạn, ta sắp xếp các phần tử trong đoạn giảm dần, sau đó chỉ cần áp dụng thuật toán tìm dãy con tăng cơ bản là được.

Ví dụ: thay vì ta lưu mảng là \([5 \mid 7, 8 \mid 5, 8 \mid 6, 7]\) thì ta sắp xếp từng đoạn giảm dần: \([5 \mid 8, 7 \mid 8, 5 \mid 7, 6]\), ta có thể bỏ luôn dấu phân cách: \([5, 8, 7, 8, 5, 7, 6]\). Sau đó áp dụng thuật toán tìm dãy con tăng trên mảng mới này.

Tại sao cái này đúng? Bởi vì ta đang tìm dãy con tăng, khi mà mỗi đoạn ta sắp xếp giảm dần thì rõ ràng không thể chọn 2 phần tử của 1 đoạn được vì nó sẽ tạo thành dãy giảm.

Tóm lại, ta cần: tạo ra mảng các đoạn, sắp xếp giảm dần các đoạn, chạy thuật toán tìm dãy con tăng. Bước này tốn tất cả là \(O((n \times D \times log(n \times D)))\) độ phức tạp, do độ dài mảng các đoạn là \(O(n \times D)\), tìm dãy con tăng thì mất thêm log. Để cho đơn giản trong việc viết độ phức tạp, do \(D\) nhỏ nên mình loại bỏ \(D\) đi (cho tiện), ta có thể xem độ phức tạp là \(O(nlogn)\).

Vậy, ta đã cải tiến được bước quy hoạch động từ \(O(n^2)\) xuống \(O(nlogn)\), tới đây thì độ phức tạp toàn bài toán là \(O(n^2logn)\), đủ tốt để chạy subtask này.

Nhận xét

Bài này nhiều bạn dễ ngộ nhận về việc quy hoạch động tìm dãy con chung (như mình đã nói ở subtask 2), dễ dẫn tới sai nếu không test cẩn thận.

Về subtask full thì mình cảm thấy khá là khó nghĩ ra trong giờ thi nếu như các bạn chưa từng chuyển bài toán LCS thành LIS bao giờ. Còn với những bạn đã biết cách chuyển thì cũng cần có cái nhìn tinh tế, phải thật sự hiểu cách chuyển thì mới áp dụng sang bài này được.

Fact không fun: Lúc mình nghĩ ra thuật subtask 2, mình không nghĩ ra cách để optimize nó sang subtask 3, mặc dù mình cũng muốn chuyển LCS -> LIS, nhưng mà lúc đó lú nên không nghĩ tới :’(.

Bài 2: COMNET

Tóm tắt đề bài:

Có một cây gồm \(n\) đỉnh, cần đếm số cách chọn ra \(k\) đỉnh sao cho số cạnh ít nhất cần dùng để làm \(k\) đỉnh này liên thông nằm trong đoạn từ \(L\) tới \(R\).

Lưu ý: \(k\) nhỏ.

Lời giải:

Với \(k = 2\), ta cần chọn ra 2 đỉnh, số cạch để làm 2 đỉnh liên thông chính là khoảng cách giữa 2 đỉnh đó. Do đó, ta chỉ cần duyệt qua mọi cặp đỉnh và tính khoảng cách giữa chúng, độ phức tạp \(O(n^3)\)

Thay vì duyệt 2 đỉnh như subtask 1, ta có thể duyệt cả 3 đỉnh với độ phức tạp \(O(n^3)\), tính số cạnh cần dùng trong \(O(n)\) bằng DFS. Tổng độ phức tạp sẽ là \(O(n^4)\), sẽ khoảng 10^8 phép tính, vẫn đủ an toàn để chạy trong 1 giây.

Cách tính số cạnh cần dùng bằng DFS, ta tạm xem 3 đỉnh được chọn là \(a, b, c\):

• Xem gốc của cây là \(a\)
• Một đỉnh \(u\) được gọi là quan trọng nếu như trong cây con gốc \(u\) có chứa đỉnh \(b\) hoặc \(c\).
• Số cạnh cần dùng chính bằng số đỉnh quan trọng trừ đi 1.

Mã giả như sau:

bool DFS(u): nếu u = b hoặc u = c thì u là đỉnh quan trọng; duyệt v kề với đỉnh u: Nếu DFS(v) đúng thì ta suy ra u là đỉnh quan trọng; return u có là đỉnh quan trọng hay không; ... gọi DFS(a);

Tuy vậy, vẫn có cách tính số đỉnh quan trọng trong \(O(1)\):

số đỉnh quan trọng \(= \frac{dist(a, b) + dist(b, c) + dist(a, c)}{2}\)

Subtask này thì nếu ta duyệt qua 4 đỉnh rồi lại kiểm tra trong \(O(n)\) thì độ phức tạp sẽ lên tới \(O(n^5)\), ta có thể áp dụng cách tính nhanh số đỉnh quan trọng trong \(O(1)\) tuy nhiên mình sẽ không đi theo hướng giải này.

Tạm thời ta xem lại 1 chút thuật toán ở subtask2, sau khi duyệt qua 3 đỉnh \(a, b, c\), ta có thể vẽ cây như sau:

Chú thính:

• Xanh lá: đỉnh quan trọng
• Đỏ: đỉnh \(a, b, c\) (lưu ý \(a, b, c\) cũng là đỉnh quan trọng, mình chỉ tô khác cho dễ nhìn thôi)
• Đen: các đỉnh khác

Ta có thể thấy, việc chọn thêm 1 đỉnh thứ 4, sẽ làm tăng số cạnh lên đúng bằng số cạnh đen. Mà số cạnh đen lại chính là số cạnh trên đường đi ngắn nhất từ đỉnh đó tới các đỉnh xanh/đỏ. Điều này dẫn ta tới việc khi ta có 3 đỉnh \(a, b, c\) và ta muốn thêm đỉnh \(d\) vào, thì ta không cần DFS lại để tính trong \(O(n)\) mà có thể tính trong \(O(1)\)

Ta làm như sau:

• Duyệt qua 3 đỉnh \(a, b, c\) (\(O(n^3)\)), với mỗi cách duyệt:
  • Tìm ra các đỉnh quan trọng như subtask 2 (\(O(n)\))
  • Tình \(G(u)\) là khoảng cách ngắn nhất từ đỉnh \(u\) tới 1 đỉnh quan trọng bất kì. Ta có thể tính mảng \(G\) bằng kỹ thuật BFS nhiều nguồn (\(O(n)\))
  • Duyệt qua đỉnh \(d\) để tính kết quả (\(O(n)\))

Độ phức tạp: \(O(n^4)\). Tuy nhiên, thật tình mà nói thì mình nghĩ subtask này người ra đề muốn chúng ta làm thuật quy hoạch động, thay vì thuật mình vừa trình bày.

Với subtask này thì độ phức tạp \(O(n^4)\) hay cả \(O(n^3)\) đều không khả thi.

Nhận xét: với 3 đỉnh \(a, b, c\), sẽ có 1 và duy nhất 1 đỉnh thỏa mãn nếu cắt đỉnh đó đi khỏi cây thì \(a, b, c\) sẽ nằm ở 3 thành phần liên thông khác nhau. Ta tạm gọi đỉnh đó là đỉnh cắt. Và lưu ý rằng đỉnh cắt cũng có thể là 1 trong 3 đỉnh \(a, b, c\).

Trên hình, đỉnh cắt chính là đỉnh được được khoanh tròn.

Từ nhận xét trên ta có thể nghĩ tới việc duyệt qua đỉnh cắt, sau đó đếm số cách chọn 3 đỉnh \(a, b, c\) nằm ở 3 cây con khác nhau sao cho tổng khoảng cách tới đỉnh cắt nằm trong đoạn \(L, R\).

Như trên hình, đỉnh cắt là đỉnh xanh dương, đỉnh này phân ra 4 nhánh con, ta cần chọn ra 3 đỉnh, mỗi đỉnh nằm ở mỗi nhánh khác nhau.

Tới đây, bài toán quy về như sau:

• Ta có \(m\) vector \(V_1, V_2, V_3, \dots, V_m\) các số (với \(m\) chính là số con của đỉnh cắt). Vector \(V_i\) lưu các khoảng cách (số cạnh) từ các đỉnh trong cây con \(i\) đi tới đỉnh cắt.
• Ta cần chọn ra 3 số trong 3 vector \(V_a, V_b, V_c\) khác nhau sao cho tổng của 3 số này nằm trong đoạn \(L, R\).

Bài toán này ta có thể làm dễ dàng bằng QHĐ cái túi:

• Gọi \(F[i][sum][k]\) là số cách chọn ra \(k\) số từ các vector \(V_1, V_2, \dots, V_i\), với tổng các số đã chọn là \(sum\).

Cách tính \(F[i][sum][k]\):

• Ta duyệt qua từng số trong vector \(i\), tạm gọi số đó có giá trị là \(x\):
  • Nếu ta chọn \(x\): \(F[i][sum][k] += F[i - 1][sum - x][k - 1]\);
  • Nếu ta không chọn \(x\): \(F[i][sum][k] += F[i - 1][sum][k]\);

Khởi tạo \(F[0][0][0] = 1\) và \(F[0][0][1] = 1\) (Vì ta có thể chọn điểm cắt cũng là 1 số).

Kết quả chính là tổng của \(F[m][sum][3]\) với sum duyệt từ \(L\) tới \(R\).

Chung quy lại thuật toán của ta sẽ qua các bước như sau:

• Duyệt qua các đỉnh cắt
• Với mỗi đỉnh cắt thì tính lại hàm quy hoạch động \(F[i][sum][k]\).

Trên thực tế, khi cài đặt ta có thể chỉ dùng mảng 2 chiều khi QHĐ để tiết kiệm bộ nhớ cũng như thời gian.

Để đánh giá độ phức tạp của thuật toán này, nếu chỉ nhìn vào các vòng for mà đánh giá thì độ phức tạp của nó sẽ là \(O(n^3 * K)\) hoặc thậm chí là \(O(n^4 * K)\).

Tuy nhiên, nếu cài đặt tối ưu, duyệt các trạng thái quy hoạch động một cách hợp lý thì độ phức tạp của toàn bộ thuật toán này chỉ là \(O(n^2 \times K)\).

Phần chứng minh độ phức tạp mình sẽ dẫn chứng ở subtask 5.

Với 4 đỉnh thì ta không còn đỉnh cắt nữa, nhưng từ subtask 4 nó cho ta 1 hướng đi mới đó là dùng Quy hoạch động để đếm số cách chọn 3 đỉnh, tiếp tục theo hướng nghĩ này thì ta sẽ dùng thuật toán Quy hoạch động cái túi trên cây (Knapsack on tree) để làm. Kiến thức này đã được cho ra trong bài 6 năm ngoái.

Hàm QHĐ có thể làm như sau: \(F[u][sum][k]\) chính là số cách chọn \(k\) đỉnh trong cây con gốc \(u\), sao cho số lượng cạnh để \(k\) đỉnh đó liên thông với đỉnh \(u\) là \(sum\).

Để tính hàm \(F\) cho từng đỉnh \(u\) thì ta có thể làm giống như ở subtask 4, nhưng lưu ý rằng mỗi subtree bây giờ ta có thể chọn nhiều hơn 1 đỉnh:

• Gọi \(G[u][i][sum][k]\) là số cách chọn \(k\) đỉnh trong cây con gốc \(u\) khi xét các cây con \(V_1, \dots, V_i\), số lượng cạnh cần dùng là \(sum\).
• Với mỗi cây con \(v\) thứ \(i\) của \(u\):
  • \[G[u][i][sum][k] += G[u][i - 1][sum - (cntEdge_v + 1)][k - k_v] * F[v][cntEdge_v][k_v]\]
  • Với \(k_v\) là số đỉnh ta chọn từ cây con \(v\), và \(cntEdge_v\) chính là số cạnh để đối \(k_v\) đỉnh đó. Lưu ý tưởng hợp \(k_v = 0\)

Trong thực tế, ta không cài đặt hàm \(G\) mà ta sẽ tính trực tiếp trên mảng \(F\) để tiết kiệm thời gian và bộ nhớ.

Thuật toán trên có độ phức tạp O(N^2 * K^2), dù nghe rất vô lý. Các bạn có thể tham khảo phần chứng minh ở comment này: https://codeforces.com/blog/entry/52742?#comment-367974

Code tham khảo: COMNET.cpp

Nhận xét:

Bài này nhiều subtask nên cũng có nhiều kiểu chiến thuật làm bài cũng như là thuật toán khác nhau, mình nghĩ sẽ còn nhiều hướng giải khác cho các subtask nhỏ. Bài này nếu như chưa biết Knapsack on tree thì làm thuật chuẩn trong giờ rất khó, tuy nhiên 2 subtask đầu rất dễ và chiếm tới 50% số điểm nên các bạn duyệt trâu cũng đã có một lượng điểm kha khá.

Bài này mình thấy cài thuật AC còn dễ và ngắn hơn cài thuật trâu đối với các bạn đã biết Knapsack on tree, và kiến thức này cũng đã có trong đề thi năm trước (mặc dù nó là bài 6).

Bài 3: OR

• Tag: DP SOS, Bao hàm loại trừ, Tổ hợp

Tóm tắt đề bài:

Cho một dãy \(a\) gồm \(n\) phần tử. Đếm số cách chọn một dãy con \(b\) của \(a\) có \(K\) phần tử sao cho tổng or của dãy con đó chia hết cho 3, và nằm trong đoạn từ \(L\) tới \(R\). Nói cách khác:

• \[v = b[1] \mid b[2] \mid \dots \mid b[K]\]
• \[L \le v \le R\]
• \[v \pmod 3 = 0\]

Lời giải:

Nhận xét chung: điều kiện chia hết cho 3 chỉ để cho vui, nó không làm bài toán khó lên hay dễ đi, cho nên trong lời giải mình sẽ không bàn tới nó.

Trong lời giải mình có dùng 1 số thuật ngữ mà mình đặt ra để cho tiện nói, mình sẽ định nghĩa ở đây:

• Nói số \(a\) là tập con của số \(b\) nếu \(b \And a = a\) (phép and), hay nói cách khác là mọi bit của \(a\) đều xuất hiện trong \(b\). Ta ký hiệu luôn \(a \subset b\) nghĩa là \(a\) là tập con của \(b\).
• \(nBit\): số bit cần dùng để biểu diễn số \(a[i]\) (khoảng 20 đối với giới hạn bài toán \(a[i] = 10^6\))

Subtask này \(n\) nhỏ nên ta chỉ cần sinh nhị phân dãy \(a\) và kiểm tra điều kiện or.

Sinh nhị phân là phần cơ bản trong đệ quy quay lui, mình thì thích cách viết đệ quy dưới đây:

void trau(int i, int len, int or_value) { if (i > n) { if (len == K && L <= or_value && or_value <= R && or_value % 3 == 0) ans += 1; return; } trau(i + 1, len, or_value); //không chọn phần tử i trau(i + 1, len + 1, or_value | a[i]); //chọn phần tử i }

Độ phức tạp \(O(2^n)\)

Với subtask này, nếu ta nhìn kỹ hơn vào các tham số của hàm trau ở subtask 1, ta có thể thấy các tham số đều đủ nhỏ để có thể lưu vào 1 mảng 3 chiều, do đó ta có thể dùng kỹ thuật đệ quy có nhớ (aka quy hoạch động) ở đây.

Có một việc đáng lưu ý ở đây là: do tham số or_value phụ thuộc vào \(a[i]\) nên nhiều bạn tạo mảng có dạng \(f[200][200][200]\) điều này là sai, bởi vì tuy \(a[i] \le 200\) nhưng giá trị or của chúng có thể lớn hơn 200, chính xác phải là \(255\) (lấy 128 or với 127 là có).

Độ phức tạp của thuật toán đệ quy có nhớ (aka quy hoạch động) này là: \(O(n^2 * 2^8)\)

Do \(L=R\) nên ta chỉ cần or ra 1 giá trị duy nhất (là \(L\)). Do đó ta chỉ cần đảm bảo mọi bit 1 của \(L\) đều được xuất hiện trong các giá trị được chọn.

Tuy nhiên, đếm số cách chọn ra \(k\) số để or lại bằng \(L\) là không đơn giản. Ta chỉ có thể đếm được số cách chọn ra \(k\) số để or lại là tập con của \(L\). Chẳng hạn nếu ta có \(cnt[L]\) là số số \(a[i]\) là tập con của \(L\), thì số cách chọn ra \(k\) số để tổng or là tập con của \(L\) chính bằng \(C^k_{cnt[L]}\).

Từ đây ta có thể dùng bao hàm loại trừ để đếm được số tập con có tổng or chính bằng \(L\). Các bạn có thể đọc thêm về bao hàm loại trừ ở thư viện VNOI: Bao hàm loại trừ

Cách tính như sau: đặt \(f[i] = C^k_{cnt[i]}\) (với \(cnt[i]\) chính là số số trong mảng \(a\) là tập con của số \(i\)) .

Do \(a[i]\) đều có dạng luỹ thừa của 2 nên việc tính \(cnt[i]\) đơn giản, ta có thể duyệt qua bit của \(i\) và đếm số lượng phần tử của \(a\) có bit tương ứng, ta có thể tính toàn bộ mảng \(cnt\) trong \(O(n \times nBit)\).

Kết quả chính bằng: \(\sum_{i \subset L)} sign(mask) \times f[mask]\). Với \(sign(mask)\) là \(-1\) nếu mask khác tính chẵn lẻ về số bit so với \(v\), ngược lại \(sign = 1\).

Việc tính kết quả này chính bằng số tập con của \(L\), ta có thể xem nó là \(O(L)\).

Chung quy lại, thuật toán gồm 3 bước:

1. Tính mảng \(cnt\) (\(O(n \times nBit)\))
2. Tính mảng \(f\) (\(O(n)\))
3. Tính kết quả bằng bao hàm loại trừ (\(O(L)\))

Độ phức tạp: \(O(n \times nBit)\)

Ở subtask này việc tính \(cnt[i]\) không còn đơn giản nữa bởi vì \(a[i]\) không còn có dạng luỹ thừa của 2. Do vậy, ta cần giải quyết việc đếm này.

Tới đây ta cần 1 kỹ thuật khác để tính mảng \(cnt\) chính là kỹ thuật DP SOS - Quy hoạch động Sum over subset. Việc tính mảng \(cnt\) chính là những gì DP SOS giải quyết. Cho nên ta chỉ cần áp dụng thẳng vào thì ta sẽ tính được mảng \(cnt\) trong độ phức tạp \(O(2^{nBit} * nBit)\).

Vậy ta chỉ cần thay bước 1 của thuật toán ở subtask 3 thành DP SOS là được.

Độ phức tạp: \(O(2^{nBit} * nBit)\)

Tới đây, ta không chỉ tính 1 kết quả cho \(L\) nữa, mà ta cần tính kết quả cho mọi số trong đoạn \([L; R]\). Ta không thể cứ với mỗi số lại bao hàm loại trừ lại được, vì mỗi lần bao hàm loại trừ rất tốn thời gian.

Ở subtask 3, ta được làm quen với bao hàm loại trừ. Ở subtask 4, ta phải dùng DP SOS. Từ 3 và 4 suy ra, ta cần làm bao hàm loại trừ tối ưu bằng DP SOS ở sub 5 = ))).

Bước cải tiến này tập trung vào bước 3 của thuật toán, ta làm như sau: sau khi tính được mảng \(f\) ở bước 2, ta thân thêm hệ số 1/-1 vào \(f[i]\). Nếu \(i\) có lẻ bit thì ta nhân 1, nếu \(i\) có chẵn bit 1 thì ta nhân \(-1\).

Sau đó tính DP SOS của mảng \(f\), tạm gọi mảng được tính là \(g\). Lúc này, \(\lvert g[i] \rvert\) đúng bằng số lượng tập con có \(k\) phần tử có tổng or đúng bằng \(i\).

Tóm lại, ta có các bước sau:

1. Tính mảng \(cnt\) bằng DP SOS (\(O(2^{nBit} \times nBit)\))
2. Tính mảng \(f\) (\(O(n)\))
3. Thêm hệ số vào mảng \(f\), tính DP SOS của mảng \(f\) (\(O(2^{nBit} \times nBit)\))
4. Tính kết quả bằng mảng DP SOS vừa tính được ở bước 3 (\(O(n)\))

Nhận xét:

Đây là một bài khó, yêu cầu một kiến thức lạ đó là DP SOS, kiến thức này lần đầu được cho trong đề thi HSG. Theo mình thấy DP SOS là kiến thức cũng ít được nhắc tới khi ôn vòng 1, thường những bạn aim giải cao ở TST hay APIO mới cày. Mình thậm chí lúc chuẩn bị học vòng 2 mới được anh Mofk bảo là học DP SOS đi, lúc đó mới biết nó là gì :v.

Nhận xét ngày 1:

Mình thấy đề rất hay, để lấy 50% điểm của ngày 1 là không khó. Tuy nhiên, để AC bất kì bài nào trong đề đều yêu cầu một lượng kiến thức tốt cùng với thật sự hiểu những gì mình đã học, phải có tư duy mở rộng vấn đề. Ví dụ bài 1 thì có yêu cầu chuyển từ LCS -> LIS. Bài 2 là Knapsack on tree nhưng cũng không quá cơ bản. Bài 3 thì yêu cầu hiểu rõ DP SOS có thể làm được gì. Để AC được cả 3 bài thì đúng là yêu cầu một lượng kiến thức rất khủng. Đề cũng đánh vào tư duy nhiều hơn là code, mình thấy cả 3 bài nếu code thuật chuẩn thì tương đối là dễ code.

Mình rất thích đề này, nhưng khả năng cao là vào thi mình sẽ bị đề này đập tơi tả :’(.

Blog này nhằm cung cấp một số tricks (thề mình không biết phải dịch chữ này ra như thế nào cho hợp lý) mà mình hay dùng khi code bằng C++ trong lập trình thi đấu. Lưu ý là các trick này đa số chỉ phù hợp trong lập trình thi đấu, nó giúp bạn tăng tốc độ code và vì thế có thể giảm tính đọc hiểu của code. Vì vậy hãy xem đây là tham khảo thôi nhé :3

In mảng 2 chiều

Giả sử bạn có mảng 2 chiều \(a\) với kích thước \(n \times m\), và bạn cần in nó ra theo format: \(n\) dòng, mỗi dòng gồm \(m\) số cách nhau 1 dấu cách.

Code bình thường thì nó có thể như thế này:

for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) cout << a[i][j] << ' '; cout << '\n'; }

Nhưng bạn có thể code thế này, cho kết quả tương tự (thật ra là không, vì ở mỗi cuối dòng không còn space nữa):

for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cout << a[i][j] << " \n"[j == m];

Thoạt nhìn thì có thể hơi lấn cấn ở đoạn " \n"[j == m], lần đầu mình thấy trick này mình cũng hơi khó hiểu đoạn đó. Cơ mà thật sự thì nó rất dễ hiểu, " \n" là một xâu gồm 2 phần tử, phần tử 0 là space, phần tử 1 là dấu xuống dòng. Đoạn [j==m] chính là để truy xấu phần tử của xâu đó, nếu \(j\) có giá trị bằng với \(m\) thì j==m cho kết quả là 1 (true), vậy nó sẽ truy xuất vào phần tử 1 của xâu ở trên, chính là xuống dòng. Còn ngược lại thì nó in ra space (truy xuất vào phần tử 0).

Lấy min/max của nhiều số

Thay vì min(a, min(b, c)) thì các bạn có thể dùng min({a, b, c}), cách này có thể dùng cho nhiều hơn 3 biến luôn.

Structured binding

Giả sử bạn có 1 vector \(a\) gồm các pair<int, int>, bạn muốn duyệt hết các phần tử trong vector này thì có 2 cách phổ biến:

for (int i = 0; i < a.size(); ++i) { cout << a[i].first << ' ' << a[i].second << '\n'; }

1. Range-based for loop, cách này chỉ dùng được từ c++11 trở lên:

for (auto p : a) { cout << p.first << ' ' << p.second << '\n'; }

Với cả 2 cách trên thì khi muốn truy xuất các giá trị first hay second thì ta phải dùng p.first hoặc p.second, nhiều khi điều này khá là phiền phức, từ c++17 trở đi ta có thể làm như sau:

for (auto [x, y] : a) { cout << x << ' ' << y << '\n'; }

Không chỉ có thể dùng với pair của STL, nó có thể dùng với struct của người dùng định nghĩa, tuple, … Đây cũng là trick mình thường xuyên sử dụng nhất, vì nó làm tăng tốc độ code lên rất nhiều.

Kỹ thuật dùng ở code trên là Structured binding, xuất hiện ở c++17. Các bạn còn thi HSG QG thì lưu ý điều này, bởi vì cái trick này không dùng được trong phòng thi Quốc Gia.

Cout & return

Nhiều khi các bạn sẽ rơi vào trường hợp code như thế này:

int main() { // stuff if (condition) { cout << something; return 0; } // stuff }

Với code trên, các bạn cần kiểm tra 1 điều kiện nào đó, sau đó sẽ in ra và kết thúc chương trình. Ta có thể rút ngắn code bằng cách vừa return vừa cout trong 1 dòng code:

int main() { // stuff if (condition) return !(cout << something); // stuff }

Operator << trong cout sẽ trả về một cái ostream, khi ta thêm ! đằng trước nó thì sẽ giá trị ostream này sẽ được convert sang bool, và có giá trị là 0. Vì thế dòng lệnh trên sẽ in ra kết quả rồi sau đó return 0.

Có một cách khác để thực hiện trick này, cách này thì có thể return nhiều loại giá trị hơn, thay vì chỉ return 0:

int main() { // stuff if (condition) return cout << something, 0; // stuff }

Ở code này, đáng lưu ý nhất là dòng cout << something, 0;, cái này thì liên quan tới câu lệnh có dấu ,. Với các khối lệnh có dấu , thì các lệnh được ngăn cách bởi dấu , sẽ được thực hiện từ trái sang phải, và giá trị trả về của khối lệnh chính là giá trị của lệnh cuối cùng. Vì thế, với khối lệnh cout << something, 0 thì lệnh cout << something sẽ được thực hiện trước, sau đó sẽ tới “lệnh” 0, và 0 chính là giá trị trả về của khối lệnh này, do đó return sẽ nhận giá trị 0.

Trick trên cũng có thể dùng ở hàm return void, bằng cách ta ép kiểu ostream sang void:

void foo() { // stuff if (condition) return void(cout << something); // stuff }

Thoát nhiều vòng lặp lồng nhau

Giả sử ta có một cái ma trận 2 chiều \(a\) với kích thước \(n \times m\), ta cần tìm vị trí đầu tiên xuất hiện của phần tử \(x\) trong ma trận đó, nếu các bạn đang lười viết hàm, và muốn viết ở main luôn để tăng tốc độ, thì có thể các bạn sẽ code một cái như thế này:

int main() { // stuff pair<int, int> pos = {-1, -1}; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) if (a[i][j] == x) { pos = {i, j}; break; } if (pos != {-1, -1}) break; } // stuff

Cách code trên bị dài chỉ vì ta phải kiểm tra các điều kiện để thoát khỏi vòng lặp. Với nhiều vòng lặp hơn nữa thì việc thoát khỏi nó đúng là thảm hoạ. Có một số cách fix code này rất izi đó là:

1. Viết hàm. Nếu ta viết một hàm riêng thì chỉ cần return nếu tìm thấy \(x\), không cần quan tâm tới chuyện thoát vòng lặp nữa. Nhưng cách này có thể làm giảm tốc độ code cũng như tăng số lượng hàm con lên quá mức cần thiết, một điều mà có thể là dân CP như mình không thích (không biết mọi người khác thì sao?).
2. Dùng goto. Quên nó đi = )).

Ở đây mình muốn giới thiệu cách dùng lambda, cách này cũng giống như là viết hàm vậy, nhưng theo mình thấy là nó code nhanh hơn cũng như là không phải thoát ra khỏi scope code hiện tại để viết hàm, mà có thể viết trực tiếp luôn:

int main() { // stuff auto pos = [&]() -> pair<int, int> { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) if (a[i][j] == x) { return {i, j}; } } return {-1, -1}; }(); // stuff

Code trên có thể nhìn hơi rối nếu bạn chưa quen cách dùng lambda trong c++, nhưng mà nó hoạt động thế này: [&]() -> pair<int, int> đoạn này là khai báo một cái lambda, nhận vào mọi biến dưới dạng pass by reference, lambda này return một cái pair<int, int>, đây là cách khai báo Trailing return type. Có một điều đáng lưu ý là sau khi khai báo xong thì mình gọi luôn hàm lambda này (ở dòng áp chót có đoạn gọi ()), cái này là vì ta chỉ sử dụng đoạn code này một lần duy nhất, thay vì đặt tên cho nó và tí nữa gọi, thì ta có thể gọi ngay sau khi khai báo, để nó chạy hàm này và return thứ mình cần luôn.

Cái trick này khá hữu dụng nếu bạn cần thoát khỏi rất nhiều vòng lặp lồng nhau.

Tạm thời mình chỉ nhớ được bao nhiêu đây, khi nào nhớ tiếp mình sẽ update :v.

Các trick này có thể khiến code bạn ngắn hơn nhưng cũng có thể làm code bạn khó debug hơn, nên xem xét cái nào phù hợp thì dùng thôi nhé.