Editorial for IOI '14 Practice Task 1 - Square - Olympiads Online Judge

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) \neq 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)$ $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

2

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)$ $O (n^{2} \log n)$ time.

https://dmoj.ca/submission/4369199