Các bạn có thể tải tutorial cho các bài trong kỳ AlgoBattle vừa qua tại ĐÂY.

A. Piccôlô vs. Mabư Béo

Ta chia hai trường hợp: ~q \ge 3~ và ~q == 2~.

Với ~q \ge 3~: ta nhận thấy số lượng ~N~ thỏa mãn sẽ là ~(10^{16}) ^ {\frac{1}{3}} (10^{16}) ^ {\frac{1}{4}} + (10^{16}) ^ {\frac{1}{5}} + \ldots \le 2 * 10^ 6~.

Vì vậy, hãy tính trước một mảng gồm toàn các số ~N~ thỏa mãn tìm được ~q \ge 3~ và tìm kiếm nhị phân trên đó để ra được số thỏa mãn.

Với ~q == 2~: ta cần kiểm tra ~N~ là số chính phương, mà không được dùng hàm sqrt cho sẵn -> sử dụng Binary search.

B. Piccôlô và Võ đài Sinh Tử

Ta sẽ phân hoạch ra hai vùng:

• (I) vùng có hoành độ, hoặc tung độ bằng ~1~, và
• (II) và vùng còn lại.

Đối với vùng (I), ta sẽ tính trước (sử dụng sàng) + tìm được tất cả các số nửa nguyên tố dựa vào khoảng tọa độ còn lại.

Đối với vùng (II), ta sẽ tìm tất cả số nguyên tố nằm trong đoạn [a, c], và tất cả số nguyên tố nằm trong đoạn [b, d]. Bạn đọc tự tìm công thức tính khi đã có được số lượng số nguyên tố ở hai vùng này.

Số lượng số nửa nguyên tố là tích của hai số trên, trừ đi cho số số nguyên tố nằm trên cả hai đoạn.

Kết quả sẽ là số điểm tìm được ở cả hai vùng.

C. Piccôlô Chui Ra Khỏi Hang

Ta lần lượt duyệt từ tấm ván thấp nhất lên cao nhất. Xét tấm ván thứ ~i~, ta sẽ tìm các tấm ván ~j~ với ~h[j] < h[i]~ mà Piccôlô có thể nhảy lên được tấm ván ~i~.

Để làm điều đó, ta xét các tấm ván lần lượt từ ~i-1~ đến tấm ván đầu tiên và duy trì khoảng diện tích ~A~ mà Piccôlô có thể nhảy đến tấm ván ~i~. Ta có thể xác định ~A~ bởi hai vector:

• Vector bên trái bắt đầu từ điểm xa nhất của tấm ván ~i~ và đi qua điểm xa nhất của một tấm ván được lắp vuông góc với bức tường trái.
• Vector bên phải bắt đầu từ điểm xa nhất của tấm ván ~i~ và đi qua điểm xa nhất của một tấm ván được lắp vuông góc với bức tường phải.

~A~ sẽ thu hẹp dần trong quá trình duyệt từ tấm ván ~i-1~ đến tấm ván đầu tiên.

Xét tấm ván ~j < i~, tại lúc này ta đã có hai vector được cập nhật dựa trên các tấm ván từ ~j+1~ đến ~i~. Nếu có ít nhất một điểm của tấm ván ~j~ nằm trong ~A~ (lưu ý là không nằm trực tiếp trên 2 vector) thì Piccôlô có thể nhảy từ tấm ván ~j~ đến tấm ván ~i~.

Trong quá trình duyệt ~i~, ta sẽ lưu phương án tốt nhất cho mỗi tấm ván ~i~.

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

D. Piccôlô Hợp Thể

Dựng mảng ~H~ có ~N~ phần tử, với mỗi phần tử là hiệu của hai phần tử tương ứng trong ~A~ và ~B~. Nói cách khác, với ~H_i = A_i - B_i~.

Với mỗi ~r~ thỏa mãn ~1 \le r \le N~, ta tìm phần tử ~l~ nhỏ nhất, sao cho GCD của các phần tử có chỉ số từ ~l~ đến ~r~ trong ~H~ không bé hơn ~2~.

Để tìm ~l~ nhanh chóng, đủ tối ưu để vượt qua time limit, ta có thể sử dụng các kỹ thuật khác nhau: Segment tree, RMQ, ... để có thể tính nhanh GCD của một đoạn trong ~O(log(n))~. Sau đó, binary search để tìm ~l~.

E. Piccôlô và Phép Thuật của Frieza

Đầu tiên, thử giải bài toán này với ĐPT ~O(N^2 * log(N))~.

Thay vì duyệt qua tất cả các hoán vị, ta sẽ muốn thử xem, với bao nhiêu hoán vị, mà nhãn ~i~ nằm ở vị trí thứ ~p~ trên cây, mà các phần tử trên đường đi từ gốc đến ~p~ tăng dần.

Kết quả là ~C(i - 1, h(p) - 1) * (n - h(p))!~, với ~h(p)~ là độ cao của node thứ ~p~ trên cây (quy định ~h(1) = 1~). Nếu ta tính trước các ~x!~ với mọi ~x \le n~, thì ~C()~ sẽ được tính trong ~O(log(10^9 + 7))~.

Tiếp theo, ta có thể đánh giá tiếp như sau để giảm độ phức tạp:

~\sum_{i = 1}^{n} C(x - 1, i - 1) = C(n, x)~

Có thể chứng minh trực quan sử dụng tam giác Pascal.

Optimized complexity ~O(N * log(N))~.

F. Piccôlô dựng Vòm Phòng Ngự

Ta chia bài toán ra làm hai trường hợp:

Đầu tiên nếu ~2K > N~: đặt ~x = min(K, N)~, xây dựng tập hợp hoán vị như sau:

~(1, 2, 3, \ldots, x | x + 1, x + 2, \ldots, N)~ ~(2, 3, \ldots, x, 1 | x + 1, x + 2, \ldots, N)~ ~(3, 4, \ldots, x, 1, 2 | x + 1, x + 2, \ldots, N)~ ~\ldots~ ~(n, 1, 2, \ldots, x - 2, x - 1 | x + 1, x + 2, \ldots, N)~

Dấu ~|~ được đặt ở giữa mỗi hoán vị chỉ đóng vai trò giúp các bạn hiểu ý tưởng xây dựng.

Luôn chứng minh được, với bất kỳ hoán vị độ dài ~N~ nào được sinh ra, ta có thể tìm được một hoán vị trong tập hợp này mà có ít nhất một vị trí trùng số.

Đối với trường hợp ~2K \le N~: ta sẽ chứng minh rằng không thể xây dựng tập hợp nào. Nói cách khách, với bất kỳ tập hợp nào có ~K~ hoán vị được sinh ra, luôn tồn tại một hoán vị mà vượt qua lớp hoán vị của cả ~K~ tập hợp đó.

\textbf{Gợi ý}: sử dụng cặp ghép cực đại ;)

G. Piccôlô Tree - Kỷ Niệm Chương Huyền Thoại

Ta xét bài toán nhỏ sau, cho dãy số ~A~ có ~N~ phần tử (~1 \le N \le 2 \times 10^5~). Có ~q~ truy vấn, mỗi truy vấn có dạng ~l~, ~r~ và ~k~, tìm số các số từ trong dãy ~A~ từ index ~l~ đến ~r~ sao cho chia hết cho ~k~. (~1 \le l, r, k \le 10^5~)

Để giải quyết bài toán trên, ta làm như sau:

Đặt ~s = \sqrt 10^5~.

Chia 2 trường hợp

• Nếu ~k \le s ~, ta có thể áp dụng ý tưởng prefix sum để tính toán từng truy vấn trong ~O(s)~.

• Ngược lại ~k > s ~, gọi ~cnt(x)~ là số các số ~x~ trong đoạn ~[l, r]~. Duyệt các số ~p~ từ ~1~ đến ~s~, kết quả của truy vấn sẽ là ~\sum cnt(p \times k)~. Để tính ~cnt(x)~ trong ~[l, r]~ ta có thể dùng thuật toán Mo. Độ phức tạp mỗi truy vấn là ~O(s + \sqrt N)~.

Như vậy với bài toán trên độ phức tạp sẽ là ~O(q \times (s + \sqrt N ))~

Đối với bài toán gốc, ta có thể làm tương tự như vậy. Khi cắt một cạnh trên cây, cây sẽ chia làm 2 cây riêng biệt, nhưng cây con nằm dưới cạnh cắt thì có thứ tự dfs liên tiếp nhau, tương đồng với ~[l, r]~ trong bài toán trên. Sau đó có thể sử dụng phép bù trừ để tính giá trị của cây con còn lại.

Hoặc là ta có thể lưu giá trị ~k~ của các truy vấn vào các cạnh, và thực hiện tính toán khi dfs, như vậy thì sẽ không cần sử dụng thuật toán Mo.

H. Piccôlô chơi TETRIS Người Già

Nhận xét:

• Khi một viên gạch rơi xuống một hàng, nó sẽ được neo cùng với các ô thuộc hàng đó mãi mãi (nghĩa là tất cả các viên gạch thuộc hàng đó sẽ rơi xuống hoặc biến mất cùng nhau).
• Nếu ta đánh chỉ số các hàng được tạo ra theo thời gian tăng dần, hàng xuất hiện sau luôn luôn ở trên hàng xuất hiện trước.

Lời giải:

Dựng cây segment tree để quản lý các cột.

Mỗi node của cây quản lý một đoạn ~[L, R]~, ta lưu tập các hàng ~S(L, R) = \{r_i, ...\}~ thoả mãn hàng ~r_i~ chứa mọi viên gạch thuộc các cột ~[L..R]~.

Chú ý rằng trong quá trình xây dựng và cập nhật cây, nếu một hàng ~r_i~ tồn tại ở cả 2 con ~left~ và ~right~ của một node ~par~, ta sẽ chuyển ~r_i~ lên lưu ở ~par~ và xoá ~r_i~ ở cả ~left~ và ~right~.

Như vậy cột ~j~ chứa hàng có chỉ số ~i~ khi và chỉ khi ~i~ tồn tại trong tập ~S~ của một node trên đường đi từ nút gốc đến nút lá quản lý cột ~i~.

Độ cao của một cột chính là độ cao của hàng có chỉ số lớn nhất thuộc cột đó.

Ở nút gốc, ~S(0, W-1)~ chứa tập các hàng mà sẽ biến mất khỏi bảng. Sau mỗi nước đi ta chỉ cần xoá các hàng này ở nút gốc.

Đánh giá:

• Chi phí xử lý mỗi truy vấn thả gạch là ~O(f(N) \times g(N))~, với ~f(N)~ là độ phức tạp của thao tác cập nhật segment tree và ~g(N)~ là độ phức tạp của thao tác cập nhật trên mỗi tập ~S~. Với cài đặt persistent segment tree và persistent set bằng kỹ thuật path copy trên cây nhị phân cân bằng, ta đạt được độ phức tạp ~O(log^2(N))~ mỗi truy vấn.
• Truy vấn rollback có chi phí ~O(1)~.
• Chi phí bộ nhớ cỡ ~O(N \times log^2(N))~.

Ghi chú:

• Lời giải được trình bày là online. Ta có thể có thuật toán hiệu quả hơn nếu làm offline (vì các truy vấn đã được biết trước).
• Nếu đề bài không yêu cầu xử lý thao tác rollback, ta có thể giải bài toán với độ phức tạp tuyến tính (amortized ~O(1)~ mỗi truy vấn).