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$ $C$ and $C_w$ $C_{w}$ be the set of pixels colored by draw_circle_filled( $R$ $R$ ) and draw_circle_filled_wrong( $R$ $R$ ), the number of pixels that have different colors in these pictures would be the cardinality (size) of the symmetric difference of $C$ $C$ and $C_w$ $C_{w}$ , that is:

$\displaystyle |C \Delta C_w| = |(C \setminus C_w) \cup (C_w \setminus C)|$ $| C Δ C_{w} | = | (C ∖ C_{w}) \cup (C_{w} ∖ C) |$

Test Set 1

For test set 1, $R$ $R$ is small enough to build the sets of colored pixels from draw_circle_filled( $R$ $R$ ) and draw_circle_filled_wrong( $R$ $R$ ) with hash set of tuples. By implementing the pseudocode in the problem statement, the time complexity would be $\mathcal O(R^2)$ $O (R^{2})$ to get all colored pixels and $\mathcal O(R^2)$ $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$ $R$ , every pixel colored by draw_circle_filled_wrong( $R$ $R$ ) is also colored by draw_circle_filled( $R$ $R$ ), that is $C_w \subseteq C$ $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*}$ $\begin{aligned} | C Δ C_{w} | & = | (C ∖ C_{w}) \cup (C_{w} ∖ C) | \\ = | (C ∖ C_{w}) \cup \emptyset | \\ = | C | - | C \cap C_{w} | \\ = | C | - | C_{w} | \end{aligned}$

which means we can count the number of pixels colored by draw_circle_filled( $R$ $R$ ) and draw_circle_filled_wrong( $R$ $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$ $R$ )

To get the number of pixels colored by draw_circle_filled( $R$ $R$ ), we need to iterate through all possible values of $x$ $x$ and find $y_{min}$ $y_{m i n}$ and $y_{max}$ $y_{m a x}$ for each $x$ $x$ which satisfy $\text{round}(\sqrt{x^2 + y^2}) \le R$ $round (\sqrt{x^{2} + y^{2}}) \leq R$ for all $y_{min} \le y \le y_{max}$ $y_{m i n} \leq y \leq y_{m a x}$ . A solution for them is $y_{max} = \text{floor}(\sqrt{R + 0.5}^2 - x^2)$ $y_{m a x} = floor ({\sqrt{R + 0.5}}^{2} - x^{2})$ and $y_{min} = -y_{max}$ $y_{m i n} = - y_{m a x}$ . 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$ $| C | = \sum_{x = - R}^{R} floor (\sqrt{(R + 0.5)^{2} - x^{2}}) \times 2 + 1$

Time complexity: $\mathcal O(R)$ $O (R)$

Count pixels colored by `draw_circle_filled_wrong`( $R$ $R$ )

draw_circle_filled_wrong( $R$ $R$ ) is composed of draw_circle_perimeter( $r$ $r$ ) calls with $r$ $r$ from $0$ $0$ to $R$ $R$ . Notice that pixels colored by draw_circle_perimeter( $r_1$ $r_{1}$ ) and draw_circle_perimeter( $r_2$ $r_{2}$ ) never overlap if $r_1 \ne r_2$ $r_{1} \neq r_{2}$ . Based on this observation, we can count the number of pixels colored by each draw_circle_perimeter( $r$ $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$ $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$ $r \geq 1$ , the colored pixels in Q1 are symmetric to the line $x = y$ $x = y$ , and there are exactly $x_t$ $x_{t}$ colored pixels between y-axis and $(x_t, y_t)$ $(x_{t}, y_{t})$ , the closest point to line $x = y$ $x = y$ (above or on the line, $x_t \ge y_t$ $x_{t} \geq y_{t}$ ). Since $x = y$ $x = y$ is at $45^{\circ}$ $45^{\circ}$ to the x-axis, the integer $x_t$ $x_{t}$ would be either $\text{ceil}(r/\cos(45^{\circ}))$ $ceil (r / \cos (45^{\circ}))$ or $\text{floor}(r/\cos(45^{\circ}))$ $floor (r / \cos (45^{\circ}))$ . We can compute the corresponding $y_t = \text{round}(\sqrt{r^2 - x_t^2})$ $y_{t} = round (\sqrt{r^{2} - x_{t}^{2}})$ and choose the closer one above or on the line $x = y$ $x = y$ . Afterwards, the number of colored pixels in Q1 including x-axis would be $2 \times x_t + 1$ $2 \times x_{t} + 1$ , and minus 1 if $(x_t, y_t)$ $(x_{t}, y_{t})$ lies on the line $x = y$ $x = y$ since it is not mirrored in this case.

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

Proof: $C_w \subseteq C$ $C_{w} \subseteq C$

For every positive $R$ $R$ , $r$ $r$ and $x$ $x$ such that $0 \le r \le R$ $0 \leq r \leq R$ and $-r \le x \le r$ $- r \leq x \leq 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*}$ $\begin{aligned} round (\sqrt{x^{2} + round (\sqrt{r^{2} - x^{2}})^{2}}) \leq r \\ ⟺ & \sqrt{x^{2} + round (\sqrt{r^{2} - x^{2}})^{2}} - 0.5 \leq r \\ ⟺ & \sqrt{x^{2} + round (\sqrt{r^{2} - x^{2}})^{2}} \leq r + 0.5 \\ ⟺ & x^{2} + round (\sqrt{r^{2} - x^{2}})^{2} \leq r^{2} + r + 0.25 \\ ⟺ & x^{2} + (\sqrt{r^{2} - x^{2}} + 0.5)^{2} \leq r^{2} + r + 0.25 \\ ⟺ & r^{2} + \sqrt{r^{2} - x^{2}} + 0.25 \leq r^{2} + r + 0.25 \end{aligned}$

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

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

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

Proof: `draw_circle_perimeter`( $r_1$ $r_{1}$ ) and `draw_circle_perimeter`( $r_2$ $r_{2}$ ) never overlap

For the first coloring statement in draw_circle_perimeter( $r$ $r$ ), we want to prove that given a fixed $x$ $x$ , the inequality $y_1 = \text{round}(\sqrt{r_1^2 - x^2}) \ne y_2 = \text{round}(\sqrt{r_2^2 - x^2})$ $y_{1} = round (\sqrt{r_{1}^{2} - x^{2}}) \neq y_{2} = round (\sqrt{r_{2}^{2} - x^{2}})$ for any pair of integers $r_1$ $r_{1}$ and $r_2$ $r_{2}$ such that $r_1 > r_2 \ge 0$ $r_{1} > r_{2} \geq 0$ and $|x| \le r_2$ $| x | \leq 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*}$ $\begin{aligned} | \sqrt{r_{1}^{2} - x^{2}} - \sqrt{r_{2}^{2} - x^{2}} | \\ = \sqrt{r_{1}^{2} - x^{2}} - \sqrt{r_{2}^{2} - x^{2}} & r_{1} > r_{2} \\ \geq \sqrt{r_{1}^{2} - x^{2}} - \sqrt{(r_{1} - 1)^{2} - x^{2}} & r_{1} and r_{2} are integers \\ \geq (\sqrt{r_{1}^{2}} - \sqrt{x^{2}}) - (\sqrt{(r_{1} - 1)^{2}} - \sqrt{x^{2}}) & for any | x | \leq r_{1} - 1 \\ = r_{1} - x - (r_{1} - 1) + x \\ = 1 \end{aligned}$

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*}$ $\begin{aligned} round (\sqrt{r_{1}^{2} - x^{2}}) - round (\sqrt{r_{2}^{2} - x^{2}}) \\ \geq & round (\sqrt{r_{1}^{2} - x^{2}}) - round (\sqrt{(r_{1} - 1)^{2} - x^{2}}) \\ \geq & round (\sqrt{r_{1}^{2} - x^{2}}) - round (\sqrt{r_{1}^{2} - x^{2}} - 1) \\ \geq & 1 \end{aligned}$

Therefore $y_1 \ne y_2$ $y_{1} \neq y_{2}$ always holds for all $r_1 > r_2 \ge 0$ $r_{1} > r_{2} \geq 0$ given a fixed $x$ $x$ such that $|x| \le r_2$ $| x | \leq r_{2}$ . For the cases that $r_2 < |x| \le r_1$ $r_{2} < | x | \leq r_{1}$ , the pixels will never satisfy the coloring condition in draw_circle_perimeter( $r_2$ $r_{2}$ ).

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

Comments

There are no comments at the moment.