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!
↵
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!
