Coordinate compression in 2d matrix

Revision en1, by DuongForeverAlone, 2023-08-27 18:40:39

This is one of the problem in my college's site. It stated that given a 2d matrix A, and I need to output the number of distinct elements of the compressed version of A (we called it matrix B). The compression progress satisfy those conditions:

  1. if A[i][j] == A[i][k] then B[i][j] == B[i][k]
  2. if A[i][j] < A[i][k] then B[i][j] < B[i][k]
  3. if A[i][j] == A[k][j] then B[i][j] == B[k][j]
  4. if A[i][j] < A[k][j] then B[i][j] < B[k][j]

For example, considered A = [[8, 11, 16], [16, 21, 16]] then we will have B = [[1, 2, 3], [3, 4, 3]] and the answer is 4. Note that we only have to output the number of distinct elements in B. I wonder is it possible to actually compress the array A, since it is possible to do it in an 1D matrix (or an array), or there is some tricks to solve this problem without compressing?

I appreciate for every helps!

Tags matrix, coordinate compression

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English DuongForeverAlone 2023-08-27 18:44:24 0 (published)
en2 English DuongForeverAlone 2023-08-27 18:43:14 20 (saved to drafts)
en1 English DuongForeverAlone 2023-08-27 18:40:39 893 Initial revision (published)