Phân tích: Aerobics

Chìa khóa của bài toán này nằm ở việc nhận ra rằng thực sự có rất nhiều không gian trên tấm thảm để tận dụng, và nhiều cách tiếp cận khác nhau sẽ hoạt động hiệu quả.

Đối với tập dữ liệu nhỏ, việc đặt các hình tròn dọc theo một trong các cạnh dài hơn, và nếu hết chỗ thì đặt dọc theo cạnh đối diện sẽ thành công. Việc phân tích chính xác tại sao chúng vừa vặn khá tẻ nhạt, vì vậy chúng ta sẽ bỏ qua để mô tả hai giải pháp có thể xử lý được cả tập dữ liệu lớn.

Giải pháp ngẫu nhiên

Tập dữ liệu lớn là một trường hợp thú vị hơn. Chúng tôi sẽ mô tả hai giải pháp để giải quyết vấn đề này. Giải pháp đầu tiên là ngẫu nhiên. (Nếu bạn đã giải bài toán Equal Sums ở Vòng 1B, bạn sẽ thấy các thuật toán ngẫu nhiên hữu ích như thế nào!).

Chúng ta sẽ sắp xếp các hình tròn theo thứ tự bán kính giảm dần. Sau đó, lấy từng hình tròn một và với mỗi hình tròn, thử đặt nó lên thảm tại một điểm ngẫu nhiên (nghĩa là đặt tâm của hình tròn tại một điểm ngẫu nhiên trên thảm). Sau đó, chúng ta kiểm tra xem nó có va chạm với bất kỳ hình tròn nào đã đặt trước đó hay không (bằng cách kiểm tra trực tiếp tất cả các hình tròn đó). Nếu có va chạm, chúng ta thử một điểm ngẫu nhiên khác và lặp lại cho đến khi tìm được điểm phù hợp. Khi đã đặt được tất cả các hình tròn, chúng ta hoàn thành.

Tất nhiên, nếu chúng ta đặt được tất cả các hình tròn, chúng ta đã tìm thấy một giải pháp chính xác. Phần khó hiểu là tại sao chúng ta luôn tìm thấy một vị trí tốt để đặt hình tròn mới trong một khoảng thời gian hợp lý. Để thấy điều này, hãy xem xét tập hợp các "điểm xấu" - những điểm mà chúng ta không thể đặt tâm của hình tròn mới vì nó sẽ gây ra va chạm. Nếu chúng ta đang đặt hình tròn \(j\) với bán kính \(r_j\), thì nó sẽ va chạm với một hình tròn \(i\) đã đặt trước đó khi và chỉ khi khoảng cách từ tâm mới đến tâm của hình tròn \(i\) nhỏ hơn \(r_i + r_j\). Điều này có nghĩa là các "điểm xấu" đơn giản là một tập hợp các hình tròn có bán kính \(r_i + r_j\).

Tổng diện tích của tập hợp các điểm xấu là bao nhiêu? Vì tập hợp này là một nhóm các hình tròn, diện tích tối đa là tổng diện tích của các hình tròn đó. (Nó có thể ít hơn vì các hình tròn có thể chồng lên nhau, nhưng không thể nhiều hơn). Vì chúng ta đang đặt các hình tròn theo thứ tự bán kính giảm dần, ta biết \(r_j \le r_i\), do đó diện tích của hình tròn "xấu" thứ \(i\) tối đa là \(\pi \cdot (2r_i)^2 = 4\pi r_i^2\). Đây là lúc chúng ta sử dụng dữ kiện tấm thảm rất lớn - chúng ta thấy rằng tổng diện tích xấu luôn chiếm tối đa 80% tấm thảm. Do đó, chúng ta có ít nhất 1/5 cơ hội chọn được một tâm tốt trong mỗi lần thử. Đặc biệt, luôn có thể tìm thấy một tâm tốt và chỉ mất vài lần thử.

Đối với mỗi lần thử, chúng ta phải thực hiện \(O(N)\) phép kiểm tra đơn giản, và kỳ vọng thực hiện tối đa \(5N\) lần thử, vì vậy độ phức tạp thời gian kỳ vọng của thuật toán này là \(O(N^2)\) - đủ nhanh.

Giải pháp xác định

Như thường lệ, nếu chúng ta sẵn sàng xử lý mã nguồn phức tạp hơn một chút, chúng ta có thể loại bỏ tính ngẫu nhiên trong giải pháp, tận dụng tất cả không gian dư thừa theo một cách khác. Một cách đơn giản để thực hiện như sau.

Với mỗi hình tròn bán kính \(R\), chúng ta gắn một hình chữ nhật kích thước \(4R \times 2R\) như hình minh họa bên dưới:

Cạnh trên của hình chữ nhật đi qua tâm của hình tròn. Cạnh dưới, cạnh trái và cạnh phải đều cách tâm hình tròn một khoảng \(2R\).

Bây giờ chúng ta đặt từng hình tròn một, bắt đầu từ những hình có bán kính lớn hơn. Chúng ta luôn đặt mỗi hình tròn vào điểm cao nhất (và nếu có lựa chọn, thì là điểm bên trái nhất) không bị bao phủ bởi bất kỳ hình chữ nhật nào đã vẽ trước đó.

Một lập luận tương tự như lập luận được sử dụng trong giải pháp ngẫu nhiên chứng minh rằng nếu chúng ta đặt một hình tròn như vậy, nó sẽ không va chạm với bất kỳ hình tròn nào đã đặt trước đó. Vì chúng ta đặt mỗi điểm vào điểm cao nhất còn trống, tâm của các hình tròn đã đặt trước đó chắc chắn nằm phía trên hình tròn cuối cùng được đặt, và do đó nếu hình tròn mới của chúng ta va chạm với một trong những hình trước đó, nó sẽ phải nằm trong hình chữ nhật mà chúng ta đã liên kết với nó.

Bây giờ hãy lưu ý rằng diện tích của tất cả các hình chữ nhật chúng ta đặt là tổng của \(8R^2 = 8 / \pi\) lần tổng diện tích của các hình tròn - con số này dễ dàng nhỏ hơn diện tích của tấm thảm. Điều này có nghĩa là chúng ta luôn có thể đặt hình tròn tiếp theo trong phạm vi tấm thảm.

Giải pháp này hơi khó cài đặt hơn giải pháp trước (vì chúng ta phải tìm điểm trống cao nhất, thay vì chỉ chọn một điểm ngẫu nhiên), nhưng vẫn dễ hơn so với việc cố gắng xếp chồng các hình tròn thực sự (thay vì thay thế chúng bằng các hình chữ nhật).

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