Phân tích: Pixelated Circle

Gọi \(C\) và \(C_w\) lần lượt là tập pixel được tô bởi draw_circle_filled(R) và draw_circle_filled_wrong(R). Số pixel khác màu giữa hai ảnh là kích thước của hiệu đối xứng:

Test Set 1

Trong Test Set 1, \(R\) đủ nhỏ để xây dựng hai tập pixel đã tô bằng các bảng băm chứa cặp tọa độ. Cài đặt trực tiếp giả mã trong đề tốn \(O(R^2)\) để tìm toàn bộ pixel được tô và thêm \(O(R^2)\) để tính hiệu đối xứng của hai tập.

Test Set 2

Quan sát then chốt để tối ưu là với mọi \(R\), mọi pixel được draw_circle_filled_wrong(R) tô cũng được draw_circle_filled(R) tô, tức \(C_w\subseteq C\). Do đó:

Như vậy, ta có thể đếm riêng số pixel được hai thủ tục tô rồi lấy hiệu. Chứng minh của quan sát này nằm ở cuối phần phân tích.

Đếm pixel được draw_circle_filled(R) tô

Để tìm số pixel được draw_circle_filled(R) tô, ta duyệt mọi \(x\) và tìm \(y_{\min},y_{\max}\) sao cho \(\operatorname{round}(\sqrt{x^2+y^2})\le R\) với mọi \(y_{\min}\le y\le y_{\max}\). Một nghiệm là
\(y_{\max}=\left\lfloor\sqrt{(R+0.5)^2-x^2}\right\rfloor\) và \(y_{\min}=-y_{\max}\). Vì vậy, số pixel tô được là

Độ phức tạp thời gian là \(O(R)\).

Đếm pixel được draw_circle_filled_wrong(R) tô

draw_circle_filled_wrong(R) gồm các lời gọi draw_circle_perimeter(r) với \(r\) từ \(0\) đến \(R\). Các pixel do draw_circle_perimeter(r_1) và draw_circle_perimeter(r_2) tô không bao giờ trùng nhau nếu \(r_1\ne r_2\). Vì vậy, ta đếm riêng số pixel của từng đường tròn rồi cộng lại. Chứng minh quan sát này cũng nằm ở cuối phần phân tích.

Xét draw_circle_perimeter(r), ta có thể chia các pixel tô được thành bốn góc phần tư và đếm riêng. Mẫu tô đối xứng qua cả trục \(x\) lẫn trục \(y\), nên chỉ cần đếm pixel ở góc phần tư thứ nhất (Q1). Tổng số pixel ngoài gốc bằng bốn lần số đó; sau cùng cộng \(1\) cho pixel gốc.

Với \(r\ge1\), các pixel ở Q1 đối xứng qua đường \(x=y\). Có đúng \(x_t\) pixel nằm giữa trục \(y\) và điểm \((x_t,y_t)\) gần đường \(x=y\) nhất, nằm phía trên hoặc trên chính đường đó, với \(x_t\ge y_t\). Vì \(x=y\) tạo góc \(45^\circ\) với trục \(x\), số nguyên \(x_t\) là một trong hai giá trị \(\left\lceil r/\cos45^\circ\right\rceil\) hoặc \(\left\lfloor r/\cos45^\circ\right\rfloor\). Ta tính \(y_t=\operatorname{round}(\sqrt{r^2-x_t^2})\) tương ứng và chọn điểm gần đường \(x=y\) nhất nằm phía trên hoặc trên đường. Khi đó số pixel ở Q1, kể cả trục \(x\), là \(2x_t+1\); nếu \((x_t,y_t)\) nằm đúng trên \(x=y\) thì trừ \(1\) vì điểm ấy không được phản chiếu thành một điểm khác.

Đếm pixel của một draw_circle_perimeter(r) tốn \(O(1)\), nên đếm toàn bộ pixel của cách vẽ sai tốn \(O(R)\).

Chứng minh \(C_w\subseteq C\)

Với mọi \(R>0\), \(0\le r\le R\) và \(-r\le x\le r\), ta cần chứng minh bất đẳng thức sau luôn đúng:

Bất đẳng thức cuối luôn đúng vì \(\sqrt{r^2-x^2}\le\sqrt{r^2}=r\) khi \(|x|\le r\) và \(r\ge0\).

Mặt khác, \(y=\operatorname{round}(\sqrt{r^2-x^2})\le\operatorname{round}(\sqrt{r^2})\le R\), nên \(-R\le y\le R\) luôn đúng.

Hai điều trên cho thấy mọi pixel được draw_circle_filled_wrong(r) tô với \(0\le r\le R\) cũng thỏa điều kiện tô của draw_circle_filled(R). Suy ra \(C_w\subseteq C\).

Chứng minh các đường tròn bán kính khác nhau không tô trùng pixel

Xét câu lệnh tô đầu tiên trong draw_circle_perimeter(r). Với \(x\) cố định, ta chứng minh \(y_1=\operatorname{round}(\sqrt{r_1^2-x^2})\ne y_2=\operatorname{round}(\sqrt{r_2^2-x^2})\) cho mọi cặp số nguyên \(r_1>r_2\ge0\) và \(|x|\le r_2\):

Từ đó tiếp tục suy ra

Vì vậy \(y_1\ne y_2\) luôn đúng khi \(r_1>r_2\ge0\) và \(|x|\le r_2\). Nếu \(r_2<|x|\le r_1\), pixel đang xét thậm chí không thể thỏa điều kiện tô của draw_circle_perimeter(r_2).

Lập luận trên áp dụng tương tự cho câu lệnh tô thứ hai, thứ ba và thứ tư trong draw_circle_perimeter(r), qua đó chứng minh hai lời gọi với bán kính khác nhau không bao giờ tô trùng pixel.

Dữ liệu kiểm thử

Google khuyến nghị bạn luyện gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

Phân tích chính thức của Google Code Jam 2022, Vòng 2, bài Pixelated Circle.