Editorial for IOI '14 Practice Task 1 - Square

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.

This problem can be solved by dynamic programming. We define a function $s(x, y)$ ~s(x, y)~ to be the size of the largest square with $(i, j)$ ~(i, j)~ as its lower-left corner. There are two cases in the recursion of $s$ ~s~.

If $s(x+1, y) = s(x, y+1) = m$ ~s(x+1, y) = s(x, y+1) = m~ then $s(x, y)$ ~s(x, y)~ will be $m+1$ ~m+1~ if the grid at $(x+m, y+m)$ ~(x+m, y+m)~ is usable, and $s(x, y)$ ~s(x, y)~ will be $m$ ~m~ if the grid at $(x+m, y+m)$ ~(x+m, y+m)~ is defective.
If $s(x+1, y) \ne s(x, y+1)$ ~s(x+1, y) \ne s(x, y+1)~, then it is easy to see that $s(x, y)$ ~s(x, y)~ is $\min(s(x+1, y), s(x, y+1))+1$ ~\min(s(x+1, y), s(x, y+1))+1~.
If either $x$ ~x~ or $y$ ~y~ is $n-1$ ~n-1~, i.e., it is at the top row or right column, then $s(x, y)$ ~s(x, y)~ is $1$ ~1~ if the grid is usable, or $0$ ~0~ otherwise.

It is easy to see that the dynamic programming runs in $\mathcal O(n^2)$ ~\mathcal O(n^2)~ time, where $n$ ~n~ is the size of the materials. Then we can scan $s$ ~s~ for the largest value and count them to find the answer.

Comments

1

Mystical commented on Feb. 22, 2022, 8:52 p.m. ← edited →

Fun fact: you can also AC using a sparse table and binary search in $\mathcal{O}(n^2 \log n)$ ~\mathcal{O}(n^2 \log n)~ time.

https://dmoj.ca/submission/4369199