RomeoFantastik's blog

Nice problem
By RomeoFantastik, 9 years ago, In English

Hi guys! I'm struggling with a problem and I hope you can help me. You have a matrix of n x m elements between 1 and 10 000( n <= 100 , m <= 100 ). You have to find the maximum area of a submatrix with at most k distinct elements. What's the best complexity you can get? O(n^3) ?

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

»
9 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

im not sure of this solution but YOLO
(O(n^2mlg^2mlgn)
we can use 2D fenwick tree that puts "ones" in the place of the last occurence of any number. then for any matrix which has dimensions r * c we can find if it has at most k distinct elements or not. r can be between 1 and n and then we can apply binary search on c to find the maximum area of the submatrix. it will be nlgm tries, you can check if it has at most k distinct elements with 2D fenwick tree by putting "ones" at the last occurence of any number. which is of O(nmlgmlgn) so it will be of O(n^2 m lg^2m lgn)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Your solution seems to be interesting, but I am having hard time to understand it because of complete lack of punctuation. :P

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Lol sorry I'll make it better

      → Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

The first thing that comes to my mind: Fix rowi and rowj, and check for possible coli and colj using 2-pointers. Also keep an array cnt[] of size 10000, where cnt[x] is number of x's in the current rectangle (which is determined by rowi, rowj, coli, colj). This gives a not so appealing complexity of O(R2 * C2 * 1) = O(108).

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

An O(n2·m2) solution:

Let's fix the highest and the lowest row. For each column (within current range of rows) compute prev[col] -- the last column (< col) contains at least one same number and then use two pointers.

One can improve it to O(n2·m):

Fix the highest row and iterate over the lowest in decreasing order. Now we are able to update prev[] in O(m).

UPD: sorry, I misread the problem, I'm gonna try to figure out what to do with k

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 7   Vote: I like it -8 Vote: I do not like it

    So, fix the highest row and iterate over the lowest in decreasing order.

    For each l maintain persistent dynamic segment tree of size 10^4 which stores amount of each number in [l, r] there r is the rightmost good column. One can get amount of distinct numbers as amount of zeros (= amount of the minimum, since 0 ≤ T[i]).

    How to update them when we add new row to the bottom in :

    for l < n - 1: take T[l + 1], add a[row][l] and keep removing a[row][r(l)] until we would have  ≤ k distinct numbers.

    UPD: sorry, this solution is actually

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      We need to remove a part of a column not just a[row][r(l)], or did I miss something?

      → Reply
»
9 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Can you get it in o(n^3) ?

→ Reply
»
9 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Is there any Online Judge with this problem?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is "submatrix" rectangular or can be sparse too? If rectangular, can it be separated by borders of matrix (e.g. columns 1, 5 in Nx5 matrix)?

→ Reply