1 năm, 5 tháng trước

Mình có note lại solution của các bài VNOI Online 2016, các bạn có thể tham khảo.

Bài VOMOVREC:

Cần cực tiểu hóa khoảng cách di chuyển max của các hình nhữ nhật. Ta sẽ tìm kiếm nhị phân kết quả của bài toán. Với mỗi giá trị chia nhị phân V, ta sẽ “nở” các hình chữ nhật ra về bốn phía một độ dài bằng V. Lúc này điều kiện cần và đủ để tất cả các hình chữ nhật ban đầu có thể di chuyển với khoảng cách không quá V thỏa mãn yêu cầu là tất cả các hình chữ nhật đã được nở có phần giao. Điều kiện N hình chữ nhật có phần giao chung hay không là max(X1) < min(X2) và max(Y1) < min(Y2).

Bài VOXOR:

Bài này yêu sử dụng kiến thức về Trie. Mỗi số có thể coi như một xâu nhị phân 31 bit (vì 10^9 < 2^31). Sau khi chèn các xâu nhị phân vào cây Trie, với mỗi node của cây ta tính thêm trường size là số lá trong gốc cây con. Dựa vào trường size này ta dễ dàng thực hiện truy vấn tìm số hạng thứ K, việc này có thể thực hiện tương tự như việc tìm kiếm một node trên cây BST, ta sẽ đi từ gốc xuống lá, tại mỗi node thì nếu k <= size(cây con trái) thì ta nhảy sang trái, nếu không thì nhảy sang phải và cộng kết quả thêm một lượng lũy thừa 2 tương ứng với độ sâu của node hiện tại.

Để xử lí truy vấn xor tất cả các số, ta chỉ việc quản lí thêm một mảng flipped[] ở mỗi độ cao. Phép xor với X chỉ đơn giản là thay đổi trạng thái của flipped[] ở những vị trí bit 1 của X.

Bài VOROOM: Solution của chính tác giả: https://docs.google.com/document/d/1lKJl227zaFexMjEVPeoD5HP1bXRkGtOcLtf4n8U9dv8/edit?usp=sharing

 

Bài VOGAME:

Dựa theo luật chơi có thể phát hiện ra một bất biến: “tính chẵn lẻ của số bi màu đỏ là không đổi”. Vì vậy nến kết quả của bài toán chính là số bi màu đỏ modulo 2 !!! Để giải quyết trọn vẹn bài toán ta chỉ cần để ý là dãy A được sinh ra theo quy tắc trong đề tuẩn hoàn theo chu kỳ (D+1), nhờ vậy có thể tính ra số bi đỏ trong O(D).

Bài VOLAND:

Cá nhân mình thấy bài này thuật toán không có gì khó, tuy nhiên để cài đặt chính xác trong thời gian hạn hẹp thì không đơn giản.

Bài này sử dụng kỹ thuật mảng cộng dồn 2D để có thể truy vấn nhanh tổng của một hình chữ nhật trong O(1). Để tính nhanh tổng của một hình thoi thì ta quay bảng một góc 45 độ (nhìn theo đường chéo), và hình thoi sẽ trở thành hình chữ nhật.

Bước tiếp theo là ta sẽ for các đường cắt của hai hình  (vì hai hình rời nhau nên sẽ tồn tại đường thẳng mà hai hình nằm trên hai nửa mặt phẳng). Các đường cắt cần thiết có thể nằm ngang, nằm dọc, hoặc xiên góc 45 độ. Ta sẽ giải quyết trường hợp đường cắt nằm ngang, trong đó hình chữ nhật ở trên, còn hình thoi ở dưới, các trường hợp khác tương tự: Tạo mảng Up[], Down[] trong đó Up[i] là hình chữ nhật có tổng lớn nhất nằm gọn trong khoảng từ hàng 1 đến hàng I, tương tự Down[i] là hình thoi max gọn trong khoảng hàng i đến hàng m. Kết quả của trường hợp này sẽ là max(Up[i] + Down[i+1]).

Để code được gọn thì ta chỉ cần giải quyết một số trường hợp cơ sở, rồi lần lượt quay bảng 90 độ và sử dụng lại code.

Bài VOMARIO:

Sử dụng Interval Tree để quản lí tập các đoạn thẳng. Có thể dễ dàng tìm được công thức QHĐ O(N^2) với F(i) = số năng lượng max đến lượt chơi thứ i. Để giảm độ phức tạp thì có thể dùng IT để cập nhật nhanh.

Chi tiết ở bài này có thể đọc comment trên forum VNOI.

1 năm, 5 tháng trước

Cảm ơn Đức đã chia sẻ thuật toán của mình về các bài VO năm nay nhé :v

Về official solutions, hiện tại các PS đều đang khá bận nên có lẽ sẽ không thể viết sol được trong tương lai gần. Các bạn có thể tham khảo thuật toán của Đức, mình thấy được viết khá dễ hiểu và đầy đủ.

Mình là tác giả của bài VOMARIO, bài này mình thấy thuật toán Đức nói chưa được rõ lắm nên mình đã viết lại solution. Sau đây là cách làm chi tiết cho từng subtask của bài VOMARIO:

 

Subtask 1: Duyệt 2^N trạng thái, mỗi trạng thái có các bit 1 thể hiện những cây nấm mà Mario sẽ ăn. Với mỗi trạng thái, duyệt qua các cây nấm Mario ăn, thực hiện thay đổi cân nặng và năng lượng như trong đề bài, sẽ ra được mức năng lượng cuối cùng. Lấy max năng lượng của tất cả các trạng thái.

ĐPT: O(2^N * N).

 

Subtask 2: Quy hoạch động. Gọi f[i] là mức năng lượng lớn nhất có thể đạt được sau khi ăn cây nấm thứ i. Với j là cây nấm ăn trước đó (j < i), ta có công thức f[i] = f[j] - w[j] * |x[i] - x[j]| + e[i]. Duyệt j từ 1 đến i - 1, áp dụng công thức quy hoạch động kia, chọn j sao cho f[i] đạt max. Đáp số là max(f[i], i = 1 -> N).

ĐPT: O(N^2).

 

Subtask 3: Mọi w[i] bằng nhau, ta gọi chung là w. Nhìn lại công thức QHĐ trong sub 2, xét 2 trường hợp:

* Trường hợp 1: x[j] < x[i] => |x[i] - x[j]| = x[i] - x[j], biến đổi công thức QHĐ:

f[i] = f[j] - w * (x[i] - x[j]) + e[i]

f[i] = (f[j] + w * x[j]) - w * x[i] + e[i]

Vì (- w * x[i] + e[i]) luôn cố định với i cố định, công việc của ta là tìm max(f[j] + w * x[j]). Ta sẽ sử dụng một cây IT, lưu tại vị trí x[j] giá trị f[j] + w * x[j]. Để tìm max(f[j] + w * x[j]), ta truy vấn max trên cây IT trong khoảng từ -oo đến x[i]. Lưu ý là vì x[i] có thể lên đến 10^9 nên ta phải rời rạc hóa tọa độ lại.

* Trường hợp 2: x[j] > x[i] => |x[i] - x[j]| = x[j] - x[i], biến đổi công thức QHĐ:

f[i] = f[j] - w * (x[j] - x[i]) + e[i]

f[i] = (f[j] - w * x[j]) + w * x[i] + e[i]

Làm tương tự như trường hợp 1, nhưng lần này là tìm max của f[j] - w * x[j] và truy vấn trong khoảng từ x[i] đến +oo. Ta phải dùng một cây IT khác để lưu f[j] - w * x[j].

Sau khi tính được f[i], ta cập nhật f[i] + w * x[j] và f[i] - w * x[j] lần lượt trên 2 cây IT.

ĐPT: O(N * log(N)).

 

Subtask 4: Giống như sub 3, xét 2 trường hợp. Tuy nhiên lần này w[i] khác nhau, vì vậy biểu thức ta cần tìm max cũng phức tạp hơn. Cụ thể ở trường hợp 1, ta cần tìm max(-w[j] * x[i] + f[j] + w[j] * x[j]) và ở trường hợp 2, ta cần tìm max(w[j] * x[i] + f[j] - w[j] * x[j]). Đây là dạng đoạn thẳng ax + b, trong đó a = -w[j] và b = f[j] + w[j] * x[j] (trường hợp 1). Bài toán trở thành bài toán truy vấn đoạn thẳng: có một tập các đoạn thẳng cho bởi 2 hệ số (a, b) và phạm vi phủ của nó trên trục hoành, với một x bất kì ta tìm đoạn thẳng phủ x và ax + b đạt max. Ta sẽ áp dụng IT đoạn thẳng ở đây, cụ thể với mỗi i ta sẽ truy vấn để tìm điểm cao nhất ở x[i] thuộc một đoạn thẳng nào đó và tính được f[i] = tung độ điểm đó + e[i]. Sau đó ta sẽ update vào cây IT đoạn thẳng 2 đoạn thẳng, một đoạn thẳng có a = w[i] và b = f[i] - w[i] * x[i] từ x[i] về bên trái và một đoạn thẳng có a = -w[i] và b = f[i] + w[i] * x[i] từ x[i] về bên phải. Chi tiết về IT đoạn thẳng xem ở bài sau: http://vnoi.info/forum/5/5052/.

ĐPT: O(N * log^2(N)).

1 năm trước
Trả lời chipchip3412
  Hiện bài gốc

cảm ơn bác đã chia sẻ và mình học hỏi được rất nhiều