Coordinate compression in 2d matrix

Правка en3, от DuongForeverAlone, 2023-08-27 18:44:24

This is one of the problem in my college's site. It states 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 satisfies 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 is there any trick to solve this problem without compressing?

I appreciate for every helps!

Теги matrix, coordinate compression

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский DuongForeverAlone 2023-08-27 18:44:24 0 (published)
en2 Английский DuongForeverAlone 2023-08-27 18:43:14 20 (saved to drafts)
en1 Английский DuongForeverAlone 2023-08-27 18:40:39 893 Initial revision (published)