Phân tích: Infinitree

Trước hết, hãy nhìn bài toán dưới góc độ lý thuyết đồ thị. Xét đồ thị có hướng \(G\), mỗi đỉnh biểu diễn một màu và có cạnh \(c_1\to c_2\) nếu \(\mathbf{L_{c_1}}=c_2\) hoặc \(\mathbf{R_{c_1}}=c_2\) (nếu cả hai cùng bằng \(c_2\) thì có hai cạnh \(c_1\to c_2\)). Các nút tầng \(K\) của cây tương ứng với đỉnh cuối của những đường đi độ dài \(K\) trong \(G\) bắt đầu tại đỉnh đen; toàn bộ đường đi tương ứng với nhánh dẫn đến nút. Nếu \(M\) là ma trận kề của \(G\), thì phần tử \((M^K)_{i,j}\) là số hậu duệ màu \(j\) nằm dưới một nút màu \(i\) đúng \(K\) tầng. Do đó \(\sum_j(M^K)_{\text{đen},j}\) là số nút tầng \(K\); cộng trên mọi \(K\le K'\) cho số nút từ gốc đến tầng \(K'\).

Lũy thừa ma trận

Ta tính được \(M^K\) bằng \(O(\log K)\) phép nhân ma trận. Ta chỉ cần \(K\le\mathbf{B}\), và dùng cùng \(M\) cho nhiều \(K\), nên có thể ghi nhớ \(M^{2^p}\) với mọi số nguyên \(p\le\log_2\mathbf{B}\): bắt đầu từ \(M^1=M^{2^0}\) rồi tính \(M^{2^{p+1}}=(M^{2^p})^2\). Khởi tạo cần \(O(\log\mathbf{B})\) phép nhân ma trận, tức \(O(\mathbf{N}^3\log\mathbf{B})\) thời gian. Vì \(K\) có biểu diễn duy nhất thành tổng các lũy thừa của \(2\), \(M^K\) là tích các lũy thừa tương ứng. Thời gian xấu nhất không đổi nhưng thực tế nhanh hơn nhiều. Quan trọng hơn, để tính \(VM^K\) cho vector \(V\), ta lần lượt nhân \(V\) với từng ma trận, chỉ cần \(O(\log\mathbf{B})\) phép nhân vector–ma trận, tức \(O(\mathbf{N}^2\log\mathbf{B})\) thời gian.

Tổng các lũy thừa ma trận

Gọi \(x\) là nút màu \(i\). Số hậu duệ của \(x\) đến tầng \(K'\) là

Ta tính hiệu quả \(\sum_{K\le K'}M^K\) bằng chia để trị, sử dụng

với \(I\) là ma trận đơn vị. Cách trực tiếp cần \(O(\log K')\) phép tính lũy thừa, tức \(O(\log^2K')\) phép nhân ma trận. Gối chồng hai quá trình chia để trị dùng cho lũy thừa và tổng sẽ giảm toàn bộ xuống \(O(\log K')\).

Các giá trị trong ma trận có thể rất lớn. Tuy nhiên, mọi giá trị vượt \(\mathbf{B}\) đều tương đương đối với bài toán, nên ta chặn kết quả phép tính tại một giá trị bất kỳ lớn hơn \(\mathbf{B}\). Nhờ vậy có thể dùng số nguyên 64 bit thông thường, không phát sinh thêm hệ số số học số nguyên lớn trong độ phức tạp.

Test Set 1

Với phần chuẩn bị trên, Test Set 1 khá trực tiếp. Vì \(\mathbf{A}\) luôn là gốc, đáp án là tầng của \(\mathbf{B}\). Ta tìm tầng đó bằng tìm kiếm nhị phân trên hàm “số nút từ gốc đến một tầng nhất định”. Hàm này cần \(O(\log\mathbf{B}')\) phép nhân ma trận, cho thuật toán \(O(\mathbf{N}^3\log^2\mathbf{B})\). Gối chồng phép chia để trị của tìm kiếm nhị phân với phép nhân ma trận có thể giảm tổng thể xuống \(O(\mathbf{N}^3\log\mathbf{B})\), cho phép cả cài đặt hoặc ngôn ngữ chậm hơn.

Test Set 2

Lời giải Test Set 2 dùng cùng mô hình và lý thuyết đồ thị như Test Set 1, nhưng cần thêm nhiều công việc.

Trước hết, định danh duy nhất mỗi nút bằng cặp \((h,x)\): nút ở tầng \(h\) có đúng \(x\) nút khác cùng tầng nằm bên trái. Đây giống một hệ tọa độ. Để đổi chỉ số nút sang cặp, trước tiên tìm tầng như trong Test Set 1. Nếu chỉ số là \(D\) và tầng là \(h\), thì \(x\) là hiệu giữa \(D-1\) và số nút từ gốc đến tầng \(h-1\), đại lượng ta cũng đã biết cách tính. Giờ ta giải bài toán với hai nút ở dạng cặp.

Một lời giải chậm

Ta đi dần xuống cây và luôn giữ cả hai nút \(\mathbf{A},\mathbf{B}\) trong cây con hiện tại. Trạng thái gồm màu gốc cây con hiện tại cùng các cặp biểu diễn \(\mathbf{A},\mathbf{B}\) tương đối với cây con này. Ban đầu gốc màu đen và hai cặp được tính như đoạn trước.

Cho màu gốc hiện tại \(C\) và cặp \((h,x)\) của một nút không phải gốc, ta xác định cây con chứa nó như sau. Số nút tầng \(h\) trong cây con trái đúng bằng số hậu duệ của \(L_C\) ở tầng \(h-1\). Đây là tổng các thành phần của \(e_{L_C}M^{h-1}\), trong đó \(e_i\) có \(1\) ở vị trí \(i\) và \(0\) ở mọi vị trí khác, nên tính được trong \(O(\mathbf{N}^2\log\mathbf{B})\). Chỉ cần so sánh số này với \(x\).

Từ đó có thuật toán: với hai cặp đích \((h_1,x_1),(h_2,x_2)\) và màu gốc \(c\), nếu \(\min(h_1,h_2)=0\) thì đáp án là \(h_1+h_2\). Nếu không, kiểm tra cây con chứa mỗi nút. Nếu chúng khác phía, đáp án cũng là \(h_1+h_2\); nếu cùng phía, đi vào cây con đó. Đi trái đổi gốc thành \(L_c\) và \((h,x)\) thành \((h-1,x)\). Đi phải đổi gốc thành \(R_c\) và \((h,x)\) thành \((h-1,x-t)\), với \(t\) là số hậu duệ tầng \(h-1\) của \(L_c\) — chính đại lượng dùng để quyết định phía.

Thuật toán cần \(\min(h_1,h_2)\) bước và có thể quá chậm khi số này lớn, điều hoàn toàn có thể xảy ra.

Tăng tốc lời giải

Ta chỉ tăng tốc những trường hợp chắc chắn cần. Nếu đồ thị do \(\mathbf{L},\mathbf{R}\) tạo ra có một màu đến được thuộc nhiều hơn một chu trình, tổng số nút cây tăng theo hàm mũ. Khi ấy các giá trị \(h\) của nút đầu vào nhất thiết nhỏ, chỉ tăng theo logarit chỉ số, nên thuật toán chậm chạy được. Chỉ cần thuật toán nhanh hơn khi mọi màu đến được thuộc nhiều nhất một chu trình.

Nếu màu gốc hiện tại không thuộc chu trình, ta đi xuống một bước như thuật toán chậm; màu vừa bỏ lại sẽ không bao giờ làm màu gốc nữa. Nếu \(c_1\) thuộc chu trình \(c_1,c_2,\dots,c_h\), ta muốn đi nhiều bước cùng lúc. Xét nhánh đi qua chu trình \(p\) lần, với \(p\times h<\min(h_1,h_2)\). Nhánh chia cây thành ba phần: hậu duệ nút cuối nhánh, các nút bên trái cây con đó và các nút bên phải. Ta xác định hai nút đích nằm ở đâu. Nếu cả hai ở phần giữa, ngay dưới nhánh, ta đi vào đó. Nếu không, ta không thể đi nhiều vòng như vậy mà giữ cả hai trong cây con hiện tại. Thử các lũy thừa giảm dần của \(2\) làm \(p\), mỗi giá trị chỉ một lần. Sau khi thử \(p=1\) (lũy thừa nguyên nhỏ nhất của \(2\)), quay lại đi từng bước đến khi gặp màu gốc ngoài chu trình, nhiều nhất \(h\) bước đơn.

Để nhảy nhanh, ta tính vector số nút từng màu nằm đúng \(p\times h\) tầng dưới gốc hiện tại ở phía trái. Với \(p=1\), vector là \(\sum_j e_{c_1}M^{h-j+1}\), chỉ cộng các \(j\) mà bước \(c_j\to c_{j+1}\) (hoặc \(c_h\to c_1\) khi \(j=h\)) đi sang phải. Với \(p\) lớn hơn, nhân vector của \(p=1\) với \(M^0+M^h+\cdots+M^{(p-1)h}\). Tổng này được tính tương tự tổng lũy thừa liên tiếp và chỉ một lần cho mỗi \(h\); có \(O(\sqrt{\mathbf{N}})\) giá trị \(h\) khác nhau. Phía phải được tính tương tự.

Từ các vector ở tầng \(p\times h\), ta tìm số nút mỗi phía ở tầng \(h_i\) bằng cách nhân với \(M^{h_i-p\times h}\). Nhờ đó, giống lời giải chậm, ta quyết định cả hai có ở cây con giữa không. Nếu đi vào cây con giữa, trừ \(p\times h\) khỏi cả hai \(h_i\), đồng thời trừ khỏi mỗi \(x_i\) tổng số nút cùng tầng bị bỏ lại bên trái.

Các chi tiết trên cho thuật toán \(O(\mathbf{N}^{3.5}\log\mathbf{N}+\mathbf{N}^2\log\mathbf{B})\). Nếu kém cẩn thận khi tính lũy thừa và tổng lũy thừa ma trận, độ phức tạp có thể lớn hơn. Giới hạn thời gian được cố ý đặt rộng, nên các thuật toán phức tạp hơn nhưng chỉ phụ thuộc theo logarit vào \(\mathbf{B}\) vẫn có thể giải đúng.

Dữ liệu kiểm thử

Chúng tôi khuyên bạn luyện tập gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

Nguồn

Phần phân tích này được dịch đầy đủ từ lời giải chính thức của Google Code Jam 2021, Chung kết thế giới — Infinitree.