## 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 to be the size of the largest square with as its lower-left corner. There are two cases in the recursion of .

• If then will be if the grid at is usable, and will be if the grid at is defective.
• If , then it is easy to see that is .
• If either or is , i.e., it is at the top row or right column, then is if the grid is usable, or otherwise.

It is easy to see that the dynamic programming runs in time, where is the size of the materials. Then we can scan for the largest value and count them to find the answer.

## Comments

• commented on Feb. 22, 2022, 8:52 p.m.

Fun fact: you can also AC using a sparse table and binary search in O(n^2logn) time.

https://dmoj.ca/submission/4369199