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

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))$ $O (N M K^{2} \log (N M K^{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))$ $O (N M \log (N M))$

Comments

There are no comments at the moment.