Phân tích

Test Set 1

Trong Test Set 1, có nhiều nhất sáu phân tử, vì vậy ta có thể dễ dàng kiểm tra toàn bộ \(6! = 720\) thứ tự có thể có của chúng. Phần không hiển nhiên là cách kiểm tra một thứ tự. Ta không thể thử mọi khối lượng nguyên tử có thể có, bởi chúng có thể là các số nguyên tùy ý và các số nguyên ấy có thể phải rất lớn (do các giá trị \(C_i\) và \(J_i\) có thể lên tới \(10^9\)).

Với mỗi thứ tự phân tử, ta phải xác định xem có tồn tại ít nhất một cặp khối lượng nguyên tử hợp lệ \(w_C\) và \(w_J\), lần lượt dành cho Codium và Jamarium, sao cho các phân tử được xếp theo khối lượng phân tử tăng nghiêm ngặt hay không. Ta không cần tìm ra các giá trị cụ thể; ta chỉ cần chứng minh sự tồn tại hoặc không tồn tại của chúng.

Đặt \(k = w_J / w_C\). Nếu \(w_C\) và \(w_J\) hợp lệ đối với thứ tự đang xét, ta có thể thay \(w_J = k \times w_C\) vào điều kiện dành cho bất kỳ cặp phân tử \((C_a, J_a)\) và \((C_b, J_b)\) nào mà \(a < b\):

Nếu \(J_a = J_b\), bất đẳng thức rút gọn thành \(C_a < C_b\), đây là một phép kiểm tra đơn giản. Nếu điều kiện này sai thì không có cách chọn khối lượng nguyên tử nào hợp lệ, và ta có thể ngừng kiểm tra thứ tự hiện tại. Trong trường hợp ngược lại, sau khi chuyển vế và thực hiện phép chia, biểu thức trở thành:

hoặc

Vì thế, ban đầu ta có thể giả sử \(k\) nhận bất kỳ giá trị nào trong một khoảng vô hạn. Mỗi lần kiểm tra một cặp phân tử, ta thu được một cận trên hoặc cận dưới mới (không lấy dấu bằng) cho \(k\), rồi cập nhật đầu mút tương ứng của khoảng. Nếu các ràng buộc buộc khoảng này trở thành rỗng (chẳng hạn đầu mút trên bị buộc phải nhỏ hơn đầu mút dưới), thì không tồn tại cách chọn khối lượng nguyên tử hợp lệ. Nếu khoảng không rỗng thì tồn tại ít nhất một cách chọn. Lưu ý rằng dù khối lượng nguyên tử của Codium và Jamarium đều phải là số nguyên, mọi giá trị hữu tỉ của \(k\) đều tương ứng với một cặp số nguyên nào đó.

Đây là một tập hợp phép kiểm tra nhanh, và còn nhanh hơn nếu nhận ra rằng ta chỉ cần kiểm tra các cặp phân tử liên tiếp trong thứ tự. Tuy nhiên, cũng như mọi bài toán có so sánh các đại lượng phân số, ta phải cẩn thận tính toán chính xác thay vì dùng xấp xỉ số thực dấu phẩy động.

Test Set 2

Xét lời giải của Test Set 1 theo chiều ngược lại có thể dẫn ta đến lời giải cho Test Set 2. Với hai phân tử bất kỳ có chỉ số \(a\) và \(b\), chúng có thể xuất hiện theo hai thứ tự tương đối. Nếu một trong hai thứ tự là bất khả thi theo phần toán học ở trên, thứ tự còn lại chính là thứ tự của hai phân tử với mọi cách gán khối lượng nguyên tử có thể có. Khi ấy, ta có thể bỏ qua cặp phân tử \((a,b)\). Tuy nhiên, nếu cả hai thứ tự đều khả thi, ta thu được một miền giá trị hợp lệ của tỉ số \(k\) có dạng \((0, R_{a,b})\) cho một thứ tự và miền có dạng \((R_{a,b}, +\infty)\) cho thứ tự kia, trong đó

Điều đó có nghĩa là trong mọi thứ tự ứng với các khối lượng nguyên tử cho tỉ số nhỏ hơn nghiêm ngặt \(R_{a,b}\), hai phân tử \(a\) và \(b\) xuất hiện theo một thứ tự tương đối nhất định; còn trong mọi thứ tự ứng với tỉ số lớn hơn nghiêm ngặt \(R_{a,b}\), chúng xuất hiện theo thứ tự tương đối ngược lại. Nếu tỉ số bằng đúng \(R_{a,b}\), hai phân tử có khối lượng hoàn toàn bằng nhau nên không có thứ tự hợp lệ.

Theo đoạn trước, nếu xét hàm \(f\) ánh xạ các tỉ số sang các thứ tự, thì \(f\) là một hàm hằng từng khúc, không xác định tại mọi tỉ số \(R_{a,b}\) ứng với một cặp \(a,b\), và hằng trên mọi khoảng không chứa tỉ số nào như vậy. Hơn nữa, ảnh của \(f\) trên \((0, R_{a,b})\) gồm các thứ tự mà phân tử \(a\) và \(b\) có một thứ tự tương đối, còn ảnh của \(f\) trên \((R_{a,b}, +\infty)\) gồm các thứ tự mà chúng có thứ tự tương đối ngược lại. Do đó, không có hai phần tử nào trong ảnh của \(f\) giống nhau. Số phần tử trong ảnh của \(f\), cũng chính là đáp án của bài toán, bằng số giá trị \(R_{a,b}\) khác nhau và khác \(0\), cộng thêm \(1\). Lưu ý rằng có thể xảy ra \(R_{a,b} = R_{c,d}\) với các phân tử \(a,b,c,d\) khác nhau, và ta cần đếm số giá trị phân biệt.

Thuật toán đếm số giá trị khác nhau bằng \(R_{a,b}\) đối với một cặp \(a,b\) nào đó là trực tiếp: thử mọi cặp phân tử, tính tỉ số như đã giải thích trong lời giải Test Set 1 (nếu tỉ số đó tồn tại), rồi thêm nó vào một tập hợp các phân số để loại bỏ các giá trị trùng lặp. Thuật toán thực hiện số lần chèn vào tập hợp theo bậc hai, nên tổng độ phức tạp là bậc hai hoặc chỉ nhỉnh hơn bậc hai một chút, tùy vào cách cài đặt tập hợp được sử dụng.

Chúng tôi khuyến nghị 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 2019, Vòng 2 — New Elements: Part 1.