nukosya's blog

how to find number of distinct values in submatrix?
By nukosya, 2 months ago, translation, In English

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!

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Is there a bound on the range of numbers the matrix can have?

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes , in problem it says that there is n^2 distinct numbers in mateix

    → Reply
»
2 months ago, # |
← Rev. 3   Vote: I like it -18 Vote: I do not like it

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$$$"?

Hints for the first problem
Hints for the second problem
→ Reply