Phân tích: Safety in Numbers

Giới thiệu

Giống một số bài trước trong Code Jam 2012, bài toán này được lấy cảm hứng từ việc tác giả xem khá nhiều chương trình Dancing With the Stars. Khác với các bài trước, bài này không cần chỉnh sửa gì để dùng trong Code Jam (dù chúng tôi không biết chương trình xử lý trường hợp hòa như thế nào): đây chính xác là hệ thống tính điểm của họ.

Các ví dụ mẫu

Khi giải bài Code Jam, đôi khi bắt đầu bằng việc hiểu các ví dụ mẫu sẽ rất hữu ích. Hãy bắt đầu từ đó.

Trường hợp #1

Trong trường hợp đầu tiên, nếu thí sinh thứ nhất nhận \(1/3\) số phiếu của khán giả thì tổng điểm của người đó là \(30\). Số phiếu còn lại chỉ có thể được phân phối theo một cách: \(2/3\) dành cho thí sinh thứ hai. Khi ấy thí sinh thứ hai cũng có \(30\) điểm, tạo thành một trận hòa và giúp thí sinh #1 an toàn. Bất kỳ số điểm nào thấp hơn đều khiến thí sinh đó bị loại. Ta có thể tính tương tự cho thí sinh thứ hai.

Trường hợp #4

Bây giờ xét một trường hợp có nhiều hơn hai thí sinh. Trong trường hợp mẫu thứ tư, ba thí sinh có điểm giám khảo lần lượt là \(24\), \(30\) và \(21\). Đầu ra mẫu khẳng định thí sinh thứ nhất an toàn nếu nhận \(34{,}666667\%\) số phiếu. Điều đó có thực sự đúng không?

Tỉ lệ phiếu ấy cho thí sinh #1 tổng cộng \(50\) điểm. Để cô ấy bị loại, tất cả thí sinh khác đều phải có hơn \(50\) điểm. Một chút tính toán cho thấy thí sinh thứ hai cần hơn \(26{,}66666\ldots\%\) số phiếu để vượt \(50\) điểm, còn thí sinh thứ ba cần hơn \(38{,}66666\ldots\%\). Tổng hai con số đó là \(65{,}333333\%\), tức đúng \(100\%\) khi cộng với phần của thí sinh thứ nhất.

Vì vậy, để cả hai cùng vượt thí sinh thứ nhất, họ cần nhiều phiếu hơn \(65{,}333333\%\) còn lại; điều này là không thể, nên thí sinh thứ nhất không thể bị loại. Nếu giảm tỉ lệ của cô ấy dù chỉ một chút, tất cả những người còn lại có thể vượt cô ấy và cô ấy sẽ bị loại. Do đó \(34{,}666667\%\) là đúng.

\(N\) lần tìm kiếm nhị phân

Bài toán dẫn rất tự nhiên đến tìm kiếm nhị phân. Trước hết, chọn thử một tỉ lệ phiếu. Với tỉ lệ đó, thí sinh có an toàn không? Nếu có, tỉ lệ an toàn nhỏ nhất phải thấp hơn; nếu không, tỉ lệ an toàn nhỏ nhất phải cao hơn. Lặp phép tìm kiếm ấy cho từng trong \(N\) thí sinh, ta thu được mọi đáp án.

Các con số ấy cộng lại bằng 1!

Có một điều hơi bất ngờ: khi tính độc lập tỉ lệ an toàn nhỏ nhất cho từng thí sinh, dường như các tỉ lệ thu được cộng lại bằng \(1\). Suy nghĩ một chút sẽ cho thấy tại sao.

Nếu mỗi thí sinh có một tỉ lệ “an toàn” nhỏ nhất, ta cũng có thể nói người đó có một tổng điểm “an toàn” nhỏ nhất — chẳng hạn \(50\) đối với thí sinh #1 trong trường hợp #4. Nhìn lại ví dụ cuối, tổng điểm an toàn là giá trị \(x\) sao cho nếu mọi thí sinh đều có tổng điểm bằng \(x\), ta sẽ dùng hết \(100\%\) phiếu khán giả. Những tỉ lệ phiếu cần để đưa từng người tới tổng điểm ấy đương nhiên cộng lại thành \(100\%\).

Điều này gần đúng hoàn toàn, nhưng có một ngoại lệ. Xét trường hợp 4 30 0 0 0. Tổng điểm an toàn rõ ràng không thể lớn hơn \(30\), vì không phải mọi thí sinh đều có thể đạt tới \(30\). Do đó, ta phải xử lý riêng những thí sinh có điểm giám khảo đã lớn hơn tổng điểm an toàn. Với lưu ý này, tổng điểm an toàn là giá trị \(x\) sao cho ta dùng hết \(100\%\) phiếu nếu mỗi thí sinh hoặc có tổng điểm bằng \(x\), hoặc nhận \(0\%\) phiếu và có điểm giám khảo lớn hơn \(x\).

Một cách tìm kiếm nhị phân khác

Giờ ta biết cách viết một lần tìm kiếm nhị phân duy nhất để tìm tổng điểm “an toàn”. Đó là tổng điểm sao cho mọi thí sinh có điểm giám khảo cao hơn nó nhận \(0\%\) phiếu; các thí sinh còn lại nhận đúng tỉ lệ đưa họ tới tổng điểm đó; và tổng các tỉ lệ phiếu bằng \(100\%\).

Để tìm tổng điểm an toàn, thử một tổng điểm ứng viên rồi tính tổng tỉ lệ phiếu cần thiết. Nếu tổng lớn hơn \(100\%\), ta cần một tổng điểm thấp hơn; nếu không, ta cần một tổng điểm cao hơn. Như một người chuẩn bị đề đã nói: “Hãy tìm kiếm nhị phân con số mà mọi thí sinh không thể đồng thời có được, thế là xong!”

Lời giải tuyến tính

Sau khi editorial này được xuất bản lần đầu, nhiều thí sinh đã viết cho chúng tôi rằng họ hoàn toàn không dùng tìm kiếm nhị phân. Có thể tránh nó bằng một vòng lặp cùng một ít toán học để tính tổng điểm “an toàn”. Trước hết, sắp xếp danh sách điểm giám khảo. Sau đó, với \(i\) từ \(0\) đến \(N-1\), liên tục tính: nếu phân phối toàn bộ phiếu khán giả cho \(i\) người đầu tiên để họ có cùng tổng điểm, tổng điểm ấy là bao nhiêu? Nếu nó nhỏ hơn điểm của thí sinh \(i+1\), hoặc nếu \(i+1=N\), thì đó chính là tổng điểm “an toàn”.

Độ chính xác

Đầu ra của bài toán là số dấu phẩy động. Bất kỳ số nào cũng được chấp nhận miễn là sai số tuyệt đối hoặc tương đối so với đáp án đúng không quá \(10^{-5}\). Điều đó nghĩa là gì?

• Sai số tuyệt đối: nếu đáp án đúng là \(y\) và bạn in \(x\), kết quả đúng khi \(|y-x|<10^{-5}\).
• Sai số tương đối: nếu đáp án đúng là \(y\) và bạn in \(x\), kết quả đúng khi \(|1-\min(y/x,x/y)|<10^{-5}\).

Chúng tôi đã làm một số thí sinh bối rối vì số chữ số thập phân trong đầu ra mẫu không nhất quán. Mục đích là minh họa rằng số chữ số thập phân bạn in không quan trọng, miễn đáp án đúng. Đáng tiếc, dù một số người nhận được một bài học bất ngờ về quy tắc này, nhiều người khác lại bối rối. Trong tương lai, chúng tôi sẽ cân nhắc kỹ hơn cách trình bày các bài có đầu ra dấu phẩy động.

Giải tập dữ liệu nhỏ

Thực ra có một cách tiếp cận đủ cho tập nhỏ nhưng không đủ cho tập lớn, dành cho người chưa quen tìm kiếm nhị phân. Vì mỗi đáp án chỉ cần cách giá trị đúng không quá \(10^{-5}\) và đáp án nằm giữa \(0\) và \(100\), chỉ cần kiểm tra vài triệu giá trị cho tỉ lệ nhỏ nhất giúp mỗi người tránh bị loại.

Hãy kiểm tra \(0\), \(0{,}00001\), \(0{,}00002\), \(0{,}00003\), ..., \(9{,}99999\), \(10\): một triệu giá trị. Sau đó, do với các đáp án lớn hơn \(10\) ta có thể dùng sai số tương đối \(10^{-5}\), kiểm tra \(10{,}0001\), \(10{,}0002\), ..., \(99{,}9999\), \(100\): thêm \(900000\) giá trị. Kiểm tra tổng cộng \(1{,}9\) triệu giá trị giúp tránh cài đặt tìm kiếm nhị phân; tuy vậy, thành thật mà nói, cài tìm kiếm nhị phân có lẽ còn dễ hơn — và nó chỉ cần kiểm tra \(\log_2(10^5)=17\) giá trị!

Ngoài ra, phương pháp này chỉ có thể thay thế lần tìm kiếm nhị phân đầu tiên nói trên, không thể thay thế lần thứ hai. Tổng điểm an toàn gần đáp án đúng trong phạm vi \(10^{-5}\) là chưa đủ; chính các con số ta in ra mới phải gần đến mức đó.

Vì sao nhiều người làm sai?

Có \(5608\) người tải dữ liệu nhỏ của bài này nhưng chỉ \(2687\) người giải đúng — một tỉ lệ thành công thấp bất thường. Vậy họ đã sai ở đâu?

Một số người in tỉ lệ âm cho những thí sinh có điểm lớn hơn “tổng điểm an toàn”; có lẽ điều đó cũng làm tổng điểm an toàn của họ dịch chuyển. Khi nhận kết quả sai, họ có thể kiểm tra đầu ra và thấy mình đã in số âm. Trong Code Jam, bạn có quyền xem tệp đầu vào và đầu ra đang được chấm; hãy tận dụng điều đó!

Những người khác giả định sai rằng một số giá trị suy ra phải là số nguyên. Một thí sinh như vậy cho kết quả đúng ở các ví dụ mẫu nhưng in 0.0 33.0 33.0 33.0 cho trường hợp 4 10 0 0 0. Một số khác gặp lỗi chia số nguyên: trong nhiều ngôn ngữ, số nguyên chia số nguyên luôn trả về số nguyên. Muốn tránh điều đó, phải ép một toán hạng sang số dấu phẩy động — hoặc chỉ cần cộng 0.0, về bản chất là cùng một việc.

Một số người có thể mắc lỗi lúc đầu, sửa được lỗi, nhưng lại nộp đầu ra dành cho tệp đầu vào khác. Mỗi khi thử nộp lại, cần chạy chương trình trên chính tệp đầu vào vừa tải xuống, nếu không bạn sẽ có đáp án sai! Chúng tôi đang tìm cách giúp người dùng phát hiện vấn đề này dễ hơn.

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