Editorial for Google Code Jam '22 Round 2 Problem B - Pixelated Circle


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Let C and C_w be the set of pixels colored by draw_circle_filled(R) and draw_circle_filled_wrong(R), the number of pixels that have different colors in these pictures would be the cardinality (size) of the symmetric difference of C and C_w, that is:

\displaystyle |C \Delta C_w| = |(C \setminus C_w) \cup (C_w \setminus C)|

Test Set 1

For test set 1, R is small enough to build the sets of colored pixels from draw_circle_filled(R) and draw_circle_filled_wrong(R) with hash set of tuples. By implementing the pseudocode in the problem statement, the time complexity would be \mathcal O(R^2) to get all colored pixels and \mathcal O(R^2) to compute the symmetric difference of the two sets.

Test Set 2

The key observation for optimizing the solution is that for any R, every pixel colored by draw_circle_filled_wrong(R) is also colored by draw_circle_filled(R), that is C_w \subseteq C. Therefore, we can simplify the size of symmetric difference to:

\displaystyle \begin{align*}
|C \Delta C_w| &= |(C \setminus C_w) \cup(C_w \setminus C) | \\
&= |(C \setminus C_w) \cup \emptyset | \\
&= |C| - |C\cap C_w| \\
&= |C| - |C_w|
\end{align*}

which means we can count the number of pixels colored by draw_circle_filled(R) and draw_circle_filled_wrong(R) separately, and the answer would be the difference between these two numbers. The proof of this observation is given at the end of this analysis.

Count pixels colored by draw_circle_filled(R)

To get the number of pixels colored by draw_circle_filled(R), we need to iterate through all possible values of x and find y_{min} and y_{max} for each x which satisfy \text{round}(\sqrt{x^2 + y^2}) \le R for all y_{min} \le y \le y_{max}. A solution for them is y_{max} = \text{floor}(\sqrt{R + 0.5}^2 - x^2) and y_{min} = -y_{max}. Therefore, we can get the number of colored pixels with a for-loop for the following equation:

\displaystyle |C| = \sum_{x=-R}^R \text{floor}(\sqrt{(R + 0.5)^2 - x^2}) \times 2 + 1

Time complexity: \mathcal O(R)

Count pixels colored by draw_circle_filled_wrong(R)

draw_circle_filled_wrong(R) is composed of draw_circle_perimeter(r) calls with r from 0 to R. Notice that pixels colored by draw_circle_perimeter(r_1) and draw_circle_perimeter(r_2) never overlap if r_1 \ne r_2. Based on this observation, we can count the number of pixels colored by each draw_circle_perimeter(r) separately and sum them up to get the total number of colored pixels. The proof of this observation is given at the end of this analysis.

Looking into function draw_circle_perimeter(r), we can break the colored pixels into 4 quadrants and count them separately. Since the colored pattern is symmetric to both x-axis and y-axis, we just need to count the pixels in Quadrant 1 (Q1), and the total count excluding the origin pixel would be that number times 4, and plus 1 to include the origin pixel.

For r \ge 1, the colored pixels in Q1 are symmetric to the line x = y, and there are exactly x_t colored pixels between y-axis and (x_t, y_t), the closest point to line x = y (above or on the line, x_t \ge y_t). Since x = y is at 45^{\circ} to the x-axis, the integer x_t would be either \text{ceil}(r/\cos(45^{\circ})) or \text{floor}(r/\cos(45^{\circ})). We can compute the corresponding y_t = \text{round}(\sqrt{r^2 - x_t^2}) and choose the closer one above or on the line x = y. Afterwards, the number of colored pixels in Q1 including x-axis would be 2 \times x_t + 1, and minus 1 if (x_t, y_t) lies on the line x = y since it is not mirrored in this case.

Time complexity: \mathcal O(1) for counting pixels colored by draw_circle_perimeter(r), and \mathcal O(R) for all colored pixels.

Proof: C_w \subseteq C

For every positive R, r and x such that 0 \le r \le R and -r \le x \le r, we want to prove that the following inequality always satisfies:

\displaystyle \begin{align*}
& \text{round}(\sqrt{x^2 + \text{round}(\sqrt{r^2 - x^2})^2}) \le r \\
\iff& \sqrt{x^2 + \text{round}(\sqrt{r^2 - x^2})^2} - 0.5 \le r \\
\iff& \sqrt{x^2 + \text{round}(\sqrt{r^2 - x^2})^2} \le r + 0.5 \\
\iff& x^2 + \text{round}(\sqrt{r^2 - x^2})^2 \le r^2 + r + 0.25 \\
\iff& x^2 + (\sqrt{r^2 - x^2} + 0.5)^2 \le r^2 + r + 0.25 \\
\iff& r^2 + \sqrt{r^2 - x^2} + 0.25 \le r^2 + r + 0.25 \\
\end{align*}

which always holds since \sqrt{r^2 - x^2} \le \sqrt{r^2} = r when |x| \le r and r \ge 0.

Secondly, y = \text{round}(\sqrt{r^2 - x^2}) \le \text{round}(\sqrt{r^2}) \le R. Therefore -R \le y \le R always holds.

The proof above shows that pixels colored by draw_circle_filled_wrong(r) with 0 \le r \le R also satisfy the coloring condition in draw_circle_filled(R), which implies C_w \subseteq C.

Proof: draw_circle_perimeter(r_1) and draw_circle_perimeter(r_2) never overlap

For the first coloring statement in draw_circle_perimeter(r), we want to prove that given a fixed x, the inequality y_1 = \text{round}(\sqrt{r_1^2 - x^2}) \ne y_2 = \text{round}(\sqrt{r_2^2 - x^2}) for any pair of integers r_1 and r_2 such that r_1 > r_2 \ge 0 and |x| \le r_2 is always true:

\displaystyle \begin{align*}
&\mathrel{\phantom{=}} \left|\sqrt{r_1^2 - x^2} - \sqrt{r_2^2 - x^2}\right| \\
&= \sqrt{r_1^2 - x^2} - \sqrt{r_2^2 - x^2} &\; r_1 > r_2 \\
&\ge \sqrt{r_1^2 - x^2} - \sqrt{(r_1 - 1)^2 - x^2} &\; r_1\text{ and }r_2\text{ are integers} \\
&\ge \left(\sqrt{r_1^2} - \sqrt{x^2}\right) - \left(\sqrt{(r_1 - 1)^2} - \sqrt{x^2}\right) &\; \text{for any }|x| \le r_1 - 1 \\
&= r_1 - x - (r_1 - 1) + x \\
&= 1
\end{align*}

Based on the proof above, we can further get:

\displaystyle \begin{align*}
& \text{round}(\sqrt{r_1^2 - x^2}) - \text{round}(\sqrt{r_2^2 - x^2}) \\
\ge\;& \text{round}(\sqrt{r_1^2 - x^2}) - \text{round}(\sqrt{(r_1 - 1)^2 - x^2}) \\
\ge\;& \text{round}(\sqrt{r_1^2 - x^2}) - \text{round}(\sqrt{r_1^2 - x^2} - 1) \\
\ge\;& 1
\end{align*}

Therefore y_1 \ne y_2 always holds for all r_1 > r_2 \ge 0 given a fixed x such that |x| \le r_2. For the cases that r_2 < |x| \le r_1, the pixels will never satisfy the coloring condition in draw_circle_perimeter(r_2).

We can further extend the proof above for the 2nd, 3rd, and 4th coloring statement in draw_circle_perimeter(r) and prove that pixels colored by draw_circle_perimeter(r_1) and draw_circle_perimeter(r_2) never overlap.


Comments

There are no comments at the moment.