Phân tích: Perfect Harmony

Bài toán này hóa ra rất, rất lắt léo, do có nhiều trường hợp cần xem xét và khả năng tràn số nguyên. Vì vậy, chúng ta sẽ xem xét giải pháp một cách cẩn thận.

Để giải quyết tập dữ liệu nhỏ (Small dataset), chỉ cần lặp qua tất cả các nốt mà Jeff có thể chơi và với mỗi nốt, hãy kiểm tra xem nó có hòa hợp với tất cả các nốt khác hay không. Lưu ý rằng có hai trường hợp cần xem xét cho mỗi nốt - hoặc tần số của nó phải là ước của tần số nốt Jeff, hoặc tần số nốt Jeff phải là ước của nó.

Đối với tập dữ liệu lớn (Large dataset), chiến lược này sẽ không đủ - có quá nhiều nốt mà Jeff có thể chơi để kiểm tra.

Chúng ta sẽ bắt đầu bằng cách sắp xếp tất cả các tần số đầu vào. Bây giờ giả sử rằng tần số của nốt mà Jeff sẽ chơi (chúng ta ký hiệu là \(F\)) nằm đâu đó giữa các tần số \(f_k\) và \(f_{k+1}\). Điều này có nghĩa là, cụ thể, tất cả các tần số \(f_1, f_2, \dots, f_k\) đều không lớn hơn \(F\); vì vậy \(F\) phải chia hết cho tất cả chúng. Điều này có nghĩa là \(F\) phải chia hết cho Bội chung nhỏ nhất của chúng (mà chúng ta sẽ ký hiệu là \(LCM(f_1, f_2, \dots, f_k)\)). Tương tự, \(F\) phải là ước của Ước chung lớn nhất của \(f_{k+1}\) đến \(f_N\).

Tính toán GCD và LCM

Để sử dụng thông tin này, chúng ta cần tính toán tất cả các LCM của các tập hợp \(f_1, \dots, f_k\) cho bất kỳ \(k\) nào, và cả các GCD của các tập hợp \(f_{k+1}, \dots, f_N\) cho bất kỳ \(k\) nào.

Chúng ta hãy nhớ lại rằng GCD của hai số \(a\) và \(b\) có thể được tính bằng thuật toán Euclid trong thời gian \(O(\log(a + b))\). Để tính LCM của hai số, chúng ta sử dụng công thức \(LCM(a, b) = a \times b / GCD(a, b)\). Sử dụng công thức này, chúng ta có thể tính toán tất cả các GCD và LCM cần thiết trong \(O(N)\) thao tác GCD, bằng cách quy nạp. Ví dụ, sau khi đã tính được \(k-1\) LCM đầu tiên, chúng ta tính cái thứ \(k\) như sau: \(LCM(f_1, \dots, f_k) = LCM(LCM(f_1, \dots, f_{k-1}), f_k)\), và số đầu tiên trong số đó đã được tính trước đó.

Lưu ý rằng người ta cũng có thể tính toán tất cả các GCD và LCM trực tiếp, trong \(O(N^2)\) thao tác GCD. Với giới hạn \(10^4\) về GCD, điều này cũng sẽ chạy kịp thời gian.

Một nhận xét cuối cùng ở đây là khi tính toán các LCM, chúng ta nên cẩn thận để tránh tràn số. Có thể xảy ra trường hợp LCM của một số tần số đầu vào không vừa với số nguyên 64-bit (nói chung, LCM của \(10^4\) số, mỗi số lên đến 16 chữ số, thậm chí có thể có 160.000 chữ số!). Tuy nhiên, lưu ý rằng Jeff không thể chơi các nốt có tần số lớn hơn \(10^{16}\), do đó nếu LCM của bất kỳ số nào lớn hơn \(10^{16}\) (hoặc thậm chí lớn hơn \(H\)), chúng ta có thể thay thế nó một cách an toàn bằng \(10^{16} + 1\) mà không làm thay đổi kết quả - Jeff dù sao cũng sẽ không thể chơi một nốt có tần số chia hết cho LCM này. Vì vậy, khi chúng ta tính toán công thức \(a \times b / GCD(a, b)\), trước tiên chúng ta nên chia bất kỳ số nào trong hai số, ví dụ \(a\), cho GCD, sau đó kiểm tra xem tích kết quả có vượt quá \(H\) hay không (ví dụ: bằng cách kiểm tra xem \((H + 1) / b \ge a / GCD(a, b)\)), và chỉ thực hiện phép nhân nếu nó không vượt quá.

Các trường hợp đặc biệt trước

Trước khi tiếp tục, chúng ta cũng nên xem xét rằng có hai trường hợp đặc biệt khi phân tích trên không áp dụng - khi \(F\) là ước của tất cả các tần số đầu vào và khi \(F\) chia hết cho tất cả chúng.

Có một số cách để xử lý chúng. Đối với trường hợp đầu tiên, cách dễ nhất là thêm một nốt nhạc khác có tần số 1 vào đầu vào. Điều này sẽ không làm cho nhiệm vụ của Jeff khó hơn, vì bất kỳ số nào cũng chia hết cho 1, và mặt khác sẽ đảm bảo rằng \(F\) luôn chia hết cho ít nhất một trong các số trong đầu vào.

Đối với giới hạn trên, không có mẹo tương tự nào tồn tại (không có số nào chia hết cho bất kỳ \(F\) nào mà Jeff có thể chọn; người ta có thể xem xét LCM của tất cả các số mà nhạc cụ của Jeff có thể chơi, nhưng số này thường quá lớn). Vì vậy, nếu chúng ta không tìm thấy giải pháp \(F\) nằm giữa bất kỳ hai tần số đầu vào nào, chúng ta phải xem xét trường hợp này một cách riêng biệt. May mắn thay, nó không phức tạp - nếu \(C\) là LCM của tất cả các số đầu vào, thì kết quả sẽ là bội số nhỏ nhất của \(C\) lớn hơn hoặc bằng \(L\), với điều kiện nó không lớn hơn \(H\).

Các trường hợp tiêu chuẩn

Lưu ý rằng vì chúng ta đang tìm tần số thấp nhất mà Jeff có thể chơi, chúng ta có thể điều tra các khả năng từng cái một - trước tiên hãy kiểm tra xem có giải pháp nào giữa \(f_1\) và \(f_2\) không, nếu có - hãy trả về nó (nhớ lại rằng \(f_1\) là 1, vì vậy không có giải pháp nào nhỏ hơn \(f_1\)). Nếu không tìm thấy giải pháp, hãy tìm giữa \(f_2\) và \(f_3\), v.v. Cuối cùng, nếu không tìm thấy giải pháp nào giữa \(f_{N-1}\) và \(f_N\), chúng ta xem xét trường hợp đặc biệt đã phân tích ở trên.

Bây giờ là điểm mấu chốt của vấn đề - làm thế nào chúng ta có thể kiểm tra (nhanh chóng) xem một giải pháp có được tìm thấy giữa \(f_k\) và \(f_{k+1}\) hay không? Lưu ý rằng khoảng này có thể chứa tới \(10^{16}\) số, vì vậy việc kiểm tra vét cạn là không thỏa đáng.

Nhớ lại rằng nếu \(F\) nằm giữa \(f_k\) và \(f_{k+1}\), thì nó phải chia hết cho \(GCD(f_{k+1}, \dots, f_N)\) (chúng ta sẽ ký hiệu số này là \(D\)), và nó phải chia hết cho \(LCM(f_1, \dots, f_k)\) (chúng ta sẽ ký hiệu số này là \(C\)). Vì vậy, cụ thể, nếu \(D\) không chia hết cho \(C\), chúng ta biết không có giải pháp nào trong khoảng này.

Có thêm hai trường hợp dễ dàng để xem xét. Nếu các khoảng \([L, H]\) và \([C, D]\) rời nhau, rõ ràng không có giải pháp nào trong khoảng này. Nếu \(C\) nằm trong khoảng \([L, H]\) (và \(D\) chia hết cho \(C\), điều mà chúng ta đã kiểm tra), thì rõ ràng nó là giải pháp nhỏ nhất trong khoảng này, vì vậy chúng ta có thể trả về nó một cách an toàn.

Lưu ý rằng có tối đa một khoảng mà các kiểm tra dễ dàng đó (và cụ thể là thời gian không đổi) sẽ không đủ. Thật vậy, nếu đối với một số \(k\) nào đó, các khoảng \([L, H]\) và \([C, D]\) không rời nhau, thì đối với bất kỳ khoảng tiếp theo \([C', D']\) nào thu được cho một \(k'\) khác, hoặc \(C'\) nằm trong \([L, H]\), hoặc hai khoảng đó rời nhau, vì \(L \le D \le f_{k+1} \le C'\).

Cuối cùng, chúng ta có thể tập trung vào một khoảng này. Chúng ta muốn tìm số \(F\) nhỏ nhất trong khoảng \([L, H]\) là ước của \(D\) và chia hết cho \(C\). Đối với điều này, chỉ cần xem xét tất cả các ước của \(D\) và kiểm tra từng cái một. Các ước của \(D\) có thể được liệt kê trong thời gian tỷ lệ thuận với căn bậc hai của \(D\) - đối với mỗi ước \(d\), hoặc \(d\) hoặc \(D/d\) không lớn hơn căn bậc hai của \(D\), do đó để tìm tất cả các ước, chúng ta kiểm tra tất cả các số không lớn hơn căn bậc hai, và nếu một số \(d\) chia hết cho \(D\), chúng ta thêm cả \(d\) và \(D/d\) vào danh sách các ước. Thuật toán này trả về các ước gần như đã được sắp xếp, vì vậy thật dễ dàng để xem xét chúng theo thứ tự tăng dần và tìm ước đầu tiên vừa là bội của \(C\) vừa rơi vào khoảng \([L, H]\).

Tóm tắt

Đây không phải là một bài toán dễ và đòi hỏi khá nhiều sự cẩn thận và chú ý. Hãy liệt kê các bước để tóm gọn lại:

• Sắp xếp tất cả các tần số đầu vào (trong thời gian \(O(N \log N)\)).
• Thêm 1 vào đầu danh sách đầu vào (trong thời gian \(O(1)\) 🙂 ).
• Tính toán các LCM tiền tố và GCD hậu tố (trong \(O(N)\) thao tác GCD, mỗi thao tác mất \(O(\log H)\) thời gian (vì chúng ta không xem xét kết quả lớn hơn \(H\))).
• Đối với mỗi \(k\) từ 1 đến \(N-1\), hãy kiểm tra xem GCD thích hợp có chia hết cho LCM thích hợp hay không (nếu không, hãy chuyển sang khoảng tiếp theo); liệu LCM có rơi vào \([L, H]\) không (nếu có, hãy trả về LCM) và liệu các khoảng \([LCM, GCD]\) và \([L, H]\) có giao nhau hay không (nếu không, hãy chuyển sang khoảng tiếp theo). Việc này mất thời gian không đổi cho mỗi khoảng, tổng cộng là \(O(N)\).
• Nếu chúng ta vẫn đang phân tích khoảng này, hãy tìm tất cả các ước của GCD và kiểm tra từng cái một. Việc này mất thời gian \(O(\sqrt{H})\).
• Nếu vẫn chưa tìm thấy câu trả lời, việc còn lại là kiểm tra bội số nhỏ nhất của LCM của tất cả các đầu vào mà lớn hơn hoặc bằng \(L\). Việc này được thực hiện trong thời gian không đổi.

Cũng có những cách tiếp cận khác cho bài toán này. Ví dụ, người ta có thể phân tích tất cả các ước của tần số đầu vào lớn nhất, và đối với mỗi ước trong số đó, sử dụng tìm kiếm nhị phân để tìm khoảng chứa nó và (trong thời gian không đổi, sử dụng các LCM và GCD đã tính trước) kiểm tra xem nó có phải là một giải pháp đúng hay không. Chúng tôi khuyến khích bạn tự mình phân tích các chi tiết của cách tiếp cận này.

Dựa trên phân tích chính thức của Google Code Jam.