Hôm nay Hạnh dạy. Nói chung như mọi lần Hạnh dạy, bài thì hay nhưng có vẻ như Hạnh vẫn tốn rất nhiều thời gian giảng bài. Mình thực sự không muốn nghe cho lắm vì vẫn muốn nghĩ bài một mình, sau đó có reference của Hạnh để improve solution thì vẫn thích hơn.

Stretching Streamers (NAIPC 2017, bài C)

Tóm tắt đề bài

Có N điểm viết trên một đường tròn, điểm thứ i chứa số nguyên dương A[i]. 2 số có cạnh đến nhau khi ước chung lớn nhất lớn hơn 1. Không được chọn 2 cạnh đè lên nhau (trừ khi đè ở đầu mút), đếm số cách dựng cây khung N điểm mod 1e9 + 7.

Giới hạn

3 <= N <= 300, 2 <= A[i] <= 10^9.

Dựng cây như nào?

Đơn giản ta có thể tóm tắt quá trình dựng cây như sau:

• Đầu tiên chọn đỉnh 1 làm gốc.
• Từ đỉnh 1 chọn một tập đỉnh X[1..M] là con của đỉnh 1. Hiển nhiên 1 phải có cạnh đến tất cả các đỉnh trong tập.
• Mỗi đỉnh X[i] quản lí 1 đoạn L[i] <= X[i] <= R[i] sao cho L[1] = 2; R[i] + 1 = L[i + 1] và R[M] = N. (1)
• Ta dựng cây cho mỗi đoạn L[i]..R[i], với điều kiện không có cạnh (x, y) với x <= X[i] <= y. Để tính cái này ta làm tương đương, đệ quy xuống.

Tại sao lại có (1)? Đơn giản vì không thể tồn tại cạnh sao cho 2 đỉnh nằm 2 bên của một X[i] nào đó, vì chúng sẽ cắt qua cạnh (1, X[i]).

Biến đổi đoạn L[i]..R[i].

Do có điều kiện không có cạnh (x, y) mà x <= X[i] <= y nên ta có thể chia đoạn L[i]..R[i] thành 2 đoạn L[i]..X[i] và X[i]..R[i] độc lập mà vẫn không thay đổi kết quả bài toán.

Khi đó, điều kiện đặc biệt biến mất và ta chỉ cần đệ quy xuống với các đoạn L[1]..X[1], X[1]..R[1], L[2]..X[2], …, X[M]..R[M].

Công thức quy hoạch động

Từ các nhận xét trên, ta có công thức quy hoạch động sau:

Gọi f[l][r] là số cách dựng cây với các đỉnh thuộc đoạn l..r. Hiển nhiên f[i][i] = 1.

Ta có

for (int k = l + 1; k <= r; ++k)
  for (int st = l + 1; st <= k; ++st)
    f[l][r] += f[l][st - 1] * f[st][k] * f[k][r];

Việc chọn tập X[] cho [l..r] giống với việc từ đoạn [l..st - 1] đã dựng cây, ta thêm đoạn [st..r] bằng cách nối (l, k) (st <= k <= r) rồi dựng 2 cây như trên. Do đó công thức qhđ này hoàn toàn chính xác. Đáp số sẽ là f[1][N]. Tuy nhiên độ phức tạp là O(N^4), chưa đủ để thỏa mãn đề bài.

Tối ưu xuống O(N^3)

Việc chọn đoạn yêu cầu 2 bước, xác định X[i] và đoạn st..r. Liệu ta có thể giảm thiểu số cách lựa chọn không?

Thực chất ta hoàn toàn có thể tách 2 bước này thành 2 công đoạn chọn đoạn, đầu tiên chọn st..X[i] thỏa mãn có cạnh (l, X[i]) và chọn đoạn X[i]..r. Như vậy ta có thể chọn 2 đoạn so le, mỗi lần chuyển trạng thái chỉ mất O(N).

Ta sửa lại công thức qhđ thành f[i][j][k], thêm k là bước hiện tại của chúng ta (0 - chọn nửa đoạn đầu - hay 1 - đã chọn xong). Công thức trở thành:

for (int k = l + 1; k <= r; ++k) {
  if (__gcd(l, r) > 1) // có cạnh từ l đến k
    f[l][r][0] += f[l][k - 1][1] * f[k][r][1];
  if (__gcd(l, k) > 1)
    f[l][r][1] += f[l][k][0] * f[k][r][1];
}

Lúc đầu f[i][i][x] = x và đáp số sẽ là f[1][N][1]. Độ phức tạp là O(N^3).

LISA - RCC 2017 1st Qualification Round, bài E

Tóm tắt đề bài

Cho N xâu và Q truy vấn. Mỗi truy vấn gồm 2 số l, r và yêu cầu trả lời số xâu khác nhau có thể tạo được bằng cách ghép 1 tiền tố khác rỗng với 1 hậu tố khác rỗng của xâu nào đó trong khoảng từ l đến r.

Giới hạn

1 <= N, Q <= 10^5. Tổng độ dài xâu không quá 10^5.

Ghép tiền tố và hậu tố

Ta có thể thấy ngay nếu không có điều kiện “khác nhau”, đáp số chỉ là (số tiền tố trong đoạn) * (số hậu tố trong đoạn). Tuy nhiên có 2 vấn đề sau xảy ra khi ta cần tìm những xâu khác nhau:

• Có thể tồn tại cặp tiền tố giống nhau - đây là phần dễ.
• Tồn tại 2 cặp tiền tố - hậu tố khác nhau nhưng cho ra xâu ghép giống nhau.

Điều kiện đếm

Một trong những kĩ thuật tiêu biểu khi đếm để xử lí lặp là đặt thêm điều kiện cho bài toán sao cho chúng khử đi các trường hợp lặp.

Giả sử ta có 2 xâu Pre[i] và Suf[j], ta có X = Pre[i] + Suf[j]. Vậy nếu tồn tại một cặp khác X = Pre[k] + Suf[l] thì ta có tính chất gì?

Không mất tính tổng quát, giả sử |Pre[i]| < |Pre[k]|. Ta có thể thấy phần thừa ra của Pre[k] chính bằng phần thừa ra của Suf[j]. Như vậy, một cách nghĩ có thể là loại bỏ tất cả việc ghép của các xâu Suf[l] khi đã tồn tại một phần thừa chung như trên.

Bởi vì ta đã lấy ra tất cả tiền tố, nên nếu tồn tại 2 cặp xâu như trên thì sẽ luôn tồn tại X = (Pre[i] + c) + (Suf[j][1..]), trong đó c là chữ cái đầu tiên của Suf[j], và Pre[i] + c cũng là 1 tiền tố (vì nó là tiền tố của Pre[k]). Như vậy, luôn tồn tại các cặp chỉ lệch nhau 1 kí tự - và ta chỉ cần đặt thêm điều kiện để khử trường hợp lệch 1 kí tự là đủ.

Kí tự thừa

Xét trường hợp X = (Pre[i] + c) + (Suf[j][1..]). Ta có thể thêm vào điều kiện sau: Xét Suf[j], nếu c + Suf[j] cũng là một hậu tố trong tập, thì ta không được ghép Suf[j] với Pre[i'] = Pre[i] + c.

Dễ dàng chứng minh tất cả xâu cần tìm đều tồn tại cách ghép duy nhất thỏa mãn điều kiện.

Lưu ý Pre[i'] phải là Pre[i] + c, tức phải có ít nhất 2 kí tự.

Ta gọi các xâu c + Suf[j] không thuộc tập hậu tố là xâu kí tự thừa c.

Đếm như thế nào?

Với điều kiện trên, lời giải của ta sẽ gồm các bước:

• Đếm số tiền tố khác nhau kết thúc ở c.
• Đếm số xâu kí tự thừa c, nhân với số tiền tố đã tìm được ở trên.
• Với mỗi hậu tố, kiểm tra xem liệu ta có thể tạo được hậu tố bằng cách ghép 1 kí tự đầu tiên từ 1 tiền tố nào đó với các kí tự còn lại của hậu tố. Vốn dĩ việc này là cần thiết bởi vì đây là trường hợp duy nhất mà 1 xâu có thể được tạo từ một hậu tố không có kí tự thừa, và không được xét ở trường hợp trên.

Số tiền tố khác nhau

Trước tiên ta sort lại các truy vấn theo R[i] và xử lí offline.

Lần lượt thêm các tiền tố vào Trie (chống lặp), đồng thời lưu lại với mỗi nút lần cuối cùng nó xuất hiện.

Giả sử ta đang ở truy vấn L[i], R[i] và đã thêm tất cả các tiền tố của S[i]..S[R[i]]. Không khó để nhìn ra số lượng tiền tố khác nhau chính là số nút mà lần xuất hiện cuối cùng >= L[i]. Ta có thể dùng IT hoặc BIT làm công cụ đếm phân phối số nút xuất hiện ở từng thời điểm và tính tổng nhanh.

Để có thể tính số tiền tố xuất hiện mà kết thúc với kí tự c cụ thể, ta có thể dùng 26 IT / BIT thay vì 1, với mỗi loại tiền tố ta có 1 cây đếm phân phối riêng.

Độ phức tạp mỗi truy vấn là O(26 * log(N)).

Số hậu tố với kí tự thừa

Trước tiên, vì bản chất xâu thừa chính là c + Suf[i] nên sẽ có (số tiền tố khác nhau) xâu như vậy (với 1 kí tự c). Tuy nhiên ta phải trừ đi các xâu cũng là hậu tố - chính là số hậu tố bắt đầu với c mà có trên 1 kí tự. Để đếm số lượng xâu bị tính thừa ta có thể lật ngược xâu, biến hậu tố thành tiền tố và đếm như phần trên.

Phần này ta cũng làm O(26 * log(N)) mỗi truy vấn.

Các hậu tố cộng thêm

Phần này khá đơn giản, với mỗi hậu tố bắt đầu với kí tự c ta có thể kiểm tra có tồn lại hậu tố Pre[i] = c nào không. Ta có thể làm kèm với thao tác đếm ở trên.

Tổng kết

Với Q truy vấn, độ phức tạp sẽ là O(Q * 26 * log(N)), nên cẩn thận 1 chút ở phần cài đặt nếu không có thể sẽ bị TLE vì cài ẩu.

Electric Charges - AIM Tech Round (Div. 1)

Tóm tắt đề bài

Cho N điểm trên mặt phẳng. Gióng chúng xuống trục Ox hoặc Oy sao cho khoảng cách giữa 2 điểm gióng xuống xa nhất là nhỏ nhất có thể.

Giới hạn

1 <= N <= 10^5, -10^8 <= X[i], Y[i] <= 10^8

Chặt nhị phân

Trong bài này ta sử dụng chặt nhị phân, một cách thông dụng để giải các bài min-của-max. Bài toán trở thành: tìm một cách xếp sao cho khoảng cách không quá X?

2-SAT??

Tuấn nghĩ ra thuật 2-SAT… Có thể AC nhũng chẳng hay chút nào :D Hiển nhiên một bài C div 1 không thể tốn nhiều thời gian code như thế… Đây không phải round của amd.

Chọn một mốc

Tóm lại ta phải tối ưu max của 3 cái sau:

• (minX - maxX)^2
• (minY - maxY)^2
• max(minX^2, maxX^2) + max(minY^2, maxY^2) Ý tưởng đầu tiên sẽ là for một biến, giả sử minX, và tham lam các biến còn lại.

Khi có minX, ta tính được maxX. Hiển nhiên các điểm có X[i] < minX hoặc X[i] > maxX đều phải chọn sang Y. Ta chỉ cần lấy min và max của các Y[i] đó, so sánh. Bài toán đơn giản?

Thuật toán sai rồi. Rất có thể maxX^2 > minX^2 và sẽ làm cho thuật toán bị ảo tưởng.

Chọn một điểm

Thay vì chọn 1 mốc như minX, ta chọn một điểm và coi nó là minX, đồng thời là điểm có abs(X[i]) lớn nhất được chọn làm X. Khi đó ta có thể yên tâm bốc các điểm nằm ngoài khoảng giới hạn đó là Y và chỉ cần kiểm tra các khoảng cách còn lại.

Tính các Y như nào?

Tóm lại ta cần tính nhanh minY và maxY ở khoảng các điểm có X < L và X > R với L, R bất kì. Ta có thể sort lại các điểm theo tọa độ của X, sau đó xây các mảng dồn min, max để lấy nhanh prefix và suffix.

Xây mất O(N log(N)) (sắp xếp) và truy vấn O(1).

Lắt léo

Còn một trường hợp nữa ta chưa xét đến: chọn tất cả theo trục Y. Trường hợp này không khó, check (maxY - minY) ^ 2 là xong. Tuy vậy mình không nghĩ ra trước khi nộp :(

Tổng kết

Tóm lại ta cần chặt nhị phân, khi kiểm tra cần chạy con trỏ hoặc lấy lower/upper bound. Việc chạy con trỏ khá lằng nhằng không cần thiết nên mình không code. Độ phức tạp là (O(N * log(N) * log(10^17))) hoặc O(N * log(10^17)).