Editorial for SAC '22 Code Challenge 5 P5 - Querying Rectangles

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.

Author: maxcruickshanks

Subtask 1

It suffices to construct a string for every subgrid, store it in a set, and then output that size.

Time Complexity: $\mathcal{O}(NMK^2 \log(NMK^2))$ ~\mathcal{O}(NMK^2 \log(NMK^2))~

Subtask 2

Realize that 2D hashing is possible, maintain a rolling hash for each subgrid, and insert that into a set to output the final size.

Time Complexity: $\mathcal{O}(NM \log(NM))$ ~\mathcal{O}(NM \log(NM))~

Comments

There are no comments at the moment.