Recently i solved a interesting problem. You have to find number of quadrat submatrix length of K, and number of distinct values of submatrix must be <= q. You have to solve this problem for each k from 1 to n. q <= 10, n <= 1500. After some thought, i understood that i can not solve this problem for q <= 1500. May you give some hints or solution for constant k. Shortly, i want to be able to find number of distinct values in submatrix. Thanks!
Is there a bound on the range of numbers the matrix can have?
yes , in problem it says that there is n^2 distinct numbers in mateix
bruh
I don't get well your problem, is the problem is "for a given $$$k$$$, find the number of distinct submatrix of length $$$k*k$$$ we can have" or is it "find the maximum/minimum number of distinct elements in a submatrix of length $$$k×k$$$"?
You can just use using hashing by hashing every submatrix of length $$$k$$$, the result will be the size of the set of hashed values. It's fine for a given $$$k$$$, but the complexity for each $$$k$$$ is $$$O(n*n^2)$$$, which is bad for $$$n = 1500$$$
You can use RMQ data structures like 2D sparse table or more complicated like segment and Fenwick. The complexity for $$$k$$$ from $$$1$$$ to $$$n$$$, is $$$O(n^2logn)$$$