Test Set 1

Trong Test Set 1 có rất ít mô-đun. Ta có thể thử mọi thứ tự của các bộ khởi phát thủ công, mô phỏng đúng quy tắc trong đề để tính tổng mức vui của từng thứ tự, rồi lấy giá trị lớn nhất.

Lưu ý rằng một mô-đun vừa trỏ vào vực thẳm vừa không bị mô-đun nào khác trỏ đến luôn đóng góp chính hệ số vui của nó vào tổng, bất kể thứ tự. Vì vậy, có thể giả sử mọi mô-đun như thế đều được kích hoạt trước theo một thứ tự cố định. Số thứ tự cần thử giảm từ \(N!\) xuống nhiều nhất \((N/2)!\), nhỏ hơn rất nhiều.

Test Set 2

Trước tiên mô hình hóa dữ liệu vào thành một rừng có gốc, trong đó quan hệ cha biểu diễn quan hệ “trỏ đến”. Các gốc là những mô-đun trỏ vào vực thẳm.

Giống nhiều bài trên cây, ta giải hiệu quả bằng chia để trị, kết hợp ghi nhớ hay quy hoạch động để giữ thời gian chạy nhỏ.

Mỗi cây, tức mỗi thành phần liên thông của rừng, có thể được giải độc lập. Gốc cây được kích hoạt bởi bộ khởi phát thủ công đầu tiên. Do đó, ta thử mọi khả năng cho bộ khởi phát đầu tiên và xóa đường đi giữa nó với gốc. Phần còn lại là nhiều cây con tách rời để giải đệ quy.

Một cách hình thức, gọi \(F(i)\) là hệ số vui của đỉnh \(i\), và \(Ftree(t)\) là giá trị vui của cây con có gốc \(t\). Nếu \(t\) là một đỉnh đơn lẻ, trả về \(F(t)\). Nếu không, lấy giá trị lớn nhất theo mọi lựa chọn \(x\) của

trong đó \(x\) là một lá của cây con, \(\operatorname{fun}(x,t)\) là hệ số vui lớn nhất trên đường từ \(x\) đến gốc \(t\), và tổng chạy qua mọi cây con \(s\) mà cha của gốc \(s\) trong cây ban đầu nằm trên đường vừa nêu.

Miền của \(Ftree\) có kích thước bằng số cây con, cũng bằng số đỉnh của cây. Nếu ghi nhớ kết quả, tổng thời gian tính nó cho mọi cây con của một cây kích thước \(k\) bằng kích thước miền \(k\) nhân thời gian tính một phần tử, không kể chi phí lời gọi đệ quy. Phép tính tổng khiến thời gian cho một phần tử là \(O(k)\), nên tổng là \(O(k^2)\). Trường hợp xấu nhất toàn bộ rừng đầu vào chỉ là một cây, vì thế độ phức tạp toàn thuật toán là \(O(N^2)\).

Test Set 3

Tiếp tục mô hình của Test Set 2, ta thấy đáp án cho \(Ftree(t)\) có thể tách thành

trong đó \(a\) là một con của \(t\), còn \(x\) là một lá. Để cực đại biểu thức, cần chọn lá \(x\) làm nhỏ nhất \(\operatorname{fun}(x,a)\). Như vậy, \(\operatorname{fun}(x,t)\) chắc chắn tận dụng được \(F(t)\) trên đường đi, còn mọi cây con \(s\) khác đạt giá trị lớn nhất có thể. Nếu chọn một đường không phải nhỏ nhất, đường nhỏ nhất sẽ bị tính như một trong các cây con khác, làm giảm \(\sum_sFtree(s)\) và do đó giảm đáp án cuối cùng.

Có thể xác định \(x\) bằng một lượt DFS, giải mỗi cây kích thước \(k\) trong \(O(k)\). Vì thế tổng độ phức tạp là \(O(N)\).

Phần trình bày dựa trên phân tích chính thức của Google Code Jam 2022, Qualification Round.