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!
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Dec/22/2024 19:34:07 (i1).
Desktop version, switch to mobile version.
Supported by
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)$$$