Editorial for The Hu Tao Fractal

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.

Authors: Yohello1, htoshiro

Subtask 1

It is sufficient to check if the 3x3 grid is a Hu-Tao Fractal by checking each of the numbers in the grid.
Time Complexity: O( $N^{2}$ )

Subtask 2 & 3

We can utilize a recursive approach to solve the remaining subtask.

Let $K$ be the greatest number so that $K$ is a power of 3, and $K \leq N$ . We check each 3x3 grid in the $K \cdot K$ grid for one of 3 states, which we store in a new $\frac{K}{3}\cdot\frac{K}{3}$ grid.

1. If the 3x3 grid is a Hu-Tao Fractal, we store the grid as 1.
2. If the 3x3 grid is COMPLETELY EMPTY, we store the grid as 0.
3. Otherwise, we store the grid as 2.

We then check this new grid in a similar fashion.

We continue checking the grid until we cannot find a Hu-Tao Fractal in the grid. Let $X$ be the number of times we simplified the grid. The largest Hu-Tao Fractal identifiable in this $K \cdot K$ grid will be $3^{X}$ . We then take the maximum of $3^X$ for all $K \cdot K$ grids.
Time Complexity: O( $N^{2}log_{3}N$ )

Comments

There are no comments at the moment.