Phân tích: Interesting Ranges

1. Kết quả có thể lớn đến mức nào?

Đầu tiên, hãy xem xét một cận trên thô cho kết quả. Cụ thể, nếu \(L=1\) và \(R=N\), có \(N(N+1)/2\) đoạn con của \([L, R]\). Không phải tất cả chúng đều chứa một số lượng chẵn các số đối xứng, nhưng một phần đáng kể (khoảng một nửa) sẽ thỏa mãn.

Vì vậy, ngay cả với tập dữ liệu nhỏ (Small dataset), chúng ta có thể nhận được hơn \(10^{25}\) đoạn con; rõ ràng ta không thể liệt kê từng đoạn một. Chúng ta phải tìm cách xử lý chúng theo nhóm.

2. Tối ưu hóa thứ nhất

Ý tưởng đầu tiên cần thiết để giải quyết tập dữ liệu nhỏ giúp chúng ta giảm số lượng đoạn cần xem xét từ \(O(N^2)\) xuống \(O(N)\). Để đạt được điều đó, chúng ta dựa trên quan sát sau: đoạn \([L, R]\) có thể được biểu diễn dưới dạng \([0, R]\) trừ đi \([0, L-1]\); do đó nó chứa một số lượng chẵn các số đối xứng khi và chỉ khi \([0, L-1]\) và \([0, R]\) cùng chứa một số lượng chẵn hoặc cùng chứa một số lượng lẻ các số đối xứng.

Nhưng điều đó giúp ích gì? Giả sử chúng ta biết đoạn \([0, X]\) nào chứa số lượng chẵn các số đối xứng (gọi là "đoạn 0-chẵn") và đoạn nào chứa số lượng lẻ ("đoạn 0-lẻ"). Ta biết rằng mỗi đoạn thú vị tương ứng với đúng một cặp đoạn 0-chẵn hoặc một cặp đoạn 0-lẻ. Điều này cũng đúng theo chiều ngược lại: mỗi cặp gồm hai đoạn 0-chẵn phân biệt tương ứng với đúng một đoạn thú vị, và tương tự với các đoạn 0-lẻ! (khi \(X\) nằm trong khoảng từ \(L-1\) đến \(R\), bao gồm cả hai đầu).

Điều đó có nghĩa là nếu có \(A\) đoạn 0-chẵn và \(B\) đoạn 0-lẻ trong phạm vi từ \(L-1\) đến \(R\), thì câu trả lời là \(A(A-1)/2 + B(B-1)/2\).

3. Tối ưu hóa thứ hai

Nhưng chúng ta thậm chí không thể chi trả thời gian chạy \(O(N)\) vì \(N\) lên tới \(10^{13}\) ngay cả trong tập dữ liệu nhỏ! Vì vậy, chúng ta phải thực hiện một tối ưu hóa khác.

Hãy viết ra một chuỗi vô hạn các số 0 và 1, với ký tự thứ \(X\) (bắt đầu từ 0) bằng 0 nếu \([0, X]\) chứa một số lượng chẵn các số đối xứng, và bằng 1 nếu \([0, X]\) chứa một số lượng lẻ các số đối xứng. Những gì chúng ta cần tìm trong bài toán này là có bao nhiêu số 0 (số \(A\) ở trên) và bao nhiêu số 1 (số \(B\) ở trên) trong chuỗi con bắt đầu từ ký tự thứ \((L-1)\) và kết thúc ở ký tự thứ \(R\).

Chuỗi này trông như thế này: 1010101010011111111111000000000001111111111100...

Bây giờ chúng ta có thể nhận thấy tối ưu hóa thứ hai: các số 0 và 1 có xu hướng đi thành các khối lớn trong chuỗi này. Cụ thể hơn, 1 chuyển thành 0 hoặc ngược lại chỉ khi chúng ta đi qua một số đối xứng. Và chỉ có \(O(\sqrt{N})\) số đối xứng lên đến \(N\) - vì vậy số lượng các nhóm số 0 hoặc số 1 liên tiếp trong \(N\) ký tự đầu tiên là \(O(\sqrt{N})\).

Tất cả các nhóm ngoại trừ có thể là hai nhóm ở biên đều nằm hoàn toàn trong đoạn \([L-1, R]\). Vì vậy, chúng ta chỉ cần tổng hợp tất cả chúng và xử lý cẩn thận các nhóm ở biên, và ta có một thuật toán \(O(\sqrt{N})\) đủ để giải quyết tập dữ liệu nhỏ.

Chúng ta cũng có thể giảm số lượng nhóm biên cần xem xét từ hai xuống một bằng cách dựa trên thực tế là số lượng số 0/1 trong \([L-1, R]\) bằng số lượng số 0/1 trong \([0, R]\) trừ đi số lượng số 0/1 trong \([0, L-2]\).

4. Tối ưu hóa thứ ba

Vậy còn tập dữ liệu lớn thì sao? \(\sqrt{10^{100}} = 10^{50}\), vì vậy chúng ta vẫn chưa đạt được yêu cầu.

Ý tưởng tối ưu hóa cuối cùng vẫn dựa trên chuỗi vô hạn các số 0 và 1 ở trên. Bạn có thể đã nhận thấy rằng nhiều khối số 1 và số 0 có cùng độ dài. Ví dụ, khối số 1 từ 11 đến 21 có độ dài 11, và khối số 0 từ 22 đến 32, số 1 từ 33 đến 43, số 0 từ 44 đến 54, v.v. cũng vậy.

Điều này là do thực tế là một số đối xứng được xác định duy nhất bởi nửa đầu của nó. Ví dụ, xét số đối xứng có 6 chữ số 127721. Số đối xứng 6 chữ số tiếp theo là gì? 128821. Tiếp theo là 129921, 130031, và cứ thế. Như bạn có thể thấy, trong hầu hết các trường hợp, sự khác biệt giữa hai số đối xứng 6 chữ số liên tiếp là 1100 (thay đổi +1 ở hai chữ số giữa). Và sự khác biệt giữa hai số đối xứng liên tiếp chính là độ dài của khối các số 1/0!

Nhưng cũng có một số khối có độ dài khác với thông thường. Ví dụ, khối số 0 từ 88 đến 98 vẫn có 11 số, nhưng khối số 1 từ 99 đến 100 chỉ có hai số; sau đó là vài khối 10 số (số 0 từ 101 đến 110; số 1 từ 111 đến 120; ...; số 0 từ 181 đến 190), sau đó chúng ta có một khối 11 số 1 từ 191 đến 201.

Giải thích trên về các số đối xứng liên tiếp cho phép chúng ta hiểu tại sao lại có những khối có độ dài bất thường như vậy. Nó xảy ra trong hai trường hợp: khi số lượng chữ số của số đối xứng thay đổi, và khi chữ số giữa của số đối xứng bắt đầu khối là 9. Một vài khối độ dài bất thường đầu tiên là: số 0 từ 9 đến 10, số 1 từ 99 đến 100, số 1 từ 191 đến 201, số 1 từ 292 đến 302, ..., số 1 từ 898 đến 908, số 1 từ 999 đến 1000, số 1 từ 1991 đến 2001, số 1 từ 2992 đến 3002, và cứ thế.

Và đây là bước cuối cùng. Tất cả các khối độ dài bất thường như vậy ngoại trừ khối từ 9 đến 10 đều gồm toàn số 1! Hay nói cách khác, tất cả các khối số 0 đều có cùng độ dài trong phạm vi các số đối xứng có cùng số lượng chữ số, ngoại trừ khối từ 9 đến 10.

Tại sao? Bởi vì có mười khối giữa hai số đối xứng liên tiếp có chữ số 9 ở giữa (với ngoại lệ duy nhất là 9 và 99), và mười là một số chẵn. Đó là lý do tại sao mỗi khi chúng ta có số 9 ở giữa, chúng ta bắt đầu một khối số 1.

Và điều đó cho phép chúng ta tính toán trong một bước tổng số lượng số 0 trong phần chuỗi vô hạn tương ứng với một số lượng chữ số nhất định của số đối xứng. Điều đó có nghĩa là chúng ta có thể tính toán tổng số lượng số 0 trong bất kỳ đoạn nào trong \(O(\text{số chữ số của số đối xứng lớn nhất})\) bước. Tất nhiên, chúng ta phải cẩn thận ở gần \(L\) và \(R\).

Còn số lượng số 1 thì sao? Nó bằng tổng độ dài trừ đi số lượng số 0 🙂

5. Tính toán Modulo

Với các số trong dữ liệu vào khá lớn, các tính toán trên phải được thực hiện cẩn thận.

Một số ngôn ngữ lập trình cho phép tính toán dễ dàng với các số lớn tùy ý. Nhưng nếu chúng ta sử dụng một ngôn ngữ không có tính năng này thì sao? May mắn thay, chúng ta được yêu cầu tìm câu trả lời modulo một số \(M\) (tương đối) nhỏ.

Điều đó cho phép chúng ta thực hiện hầu hết các phép tính modulo \(M\), và do đó chỉ sử dụng các số nhỏ trong các phép tính đó. Các phép tính chúng ta cần để tìm câu trả lời là: cộng, nhân, trừ và chia cho 2. Ba phép tính đầu tiên được thực hiện theo cách tiêu chuẩn. Phép tính thứ tư khả thi do thực tế là modulo được sử dụng trong bài toán là số lẻ. Khi chúng ta chia một số \(X\) cho 2 modulo \(M\), chúng ta nhận được \(X/2\) nếu \(X\) chẵn, và \((X+M)/2\) khi \(X\) lẻ.

Nguồn

Bản dịch dựa trên phân tích chính thức của Google Code Jam 2009 - Round 3 - Interesting Ranges, thuộc kho Google Coding Competitions (Apache-2.0).