Dada una matriz A de tamaño NxN Necesitamos encontrar el número de pares de inversión que contiene. El recuento de inversiones en una matriz se define como el número de pares que satisfacen las siguientes condiciones:
- incógnita1? incógnita2
- y1? y2
- Hacha2][y2]< A[x1][y1]
Restricciones:
- 1 ? Ayo? 109
- 1 ? norte? 103
Ejemplos:
For simplicity let's take a 2x2 matrix : A = {{7 5} {3 1}}; The inversion pairs are : (7 5) (3 1) (7 3) (5 1) and (7 1) Output : 5 Para resolver este problema necesitamos saber lo siguiente:
- Encontrar el número de pares de inversión en una matriz 1D usando el árbol indexado binario (BIT) https://www.geeksforgeeks.org/dsa/inversion-count-in-array-using-bit/
- PUNTO 2D https://www.geeksforgeeks.org/dsa/two-dimensional-binary-indexed-tree-or-fenwick-tree/
Como necesitamos encontrar el número de pares de inversión en una matriz, lo primero que debemos hacer es almacenar los elementos de la matriz en otra matriz, digamos v, y ordenar la matriz v para que podamos comparar los elementos de la matriz sin clasificar con v y encontrar el número de pares de inversión usando BIT. Pero se da que los valores de los elementos son muy grandes (109) por lo que no podemos utilizar los valores de los elementos de la matriz como índices en el TBI. Por lo tanto, necesitamos utilizar la posición de los elementos como índices en el BIT 2D.
Usaremos la tupla (-A[i][j] i j) para cada elemento de la matriz y la almacenaremos en una matriz, digamos 'v'. Luego necesitamos ordenar v según el valor de -A[i][j] en orden ascendente para que el elemento más grande de la matriz se almacene en el índice 0 y el más pequeño en el último índice de v. Ahora el problema se reduce a encontrar pares de inversión en una matriz 1D, la única excepción es que vamos a usar un BIT 2D.
Tenga en cuenta que aquí estamos usando valores negativos de A[i][j] simplemente porque vamos a recorrer v de izquierda a derecha, es decir, desde el número más grande de la matriz hasta el más pequeño (porque eso es lo que hacemos cuando encontramos pares de inversión en una matriz 1D usando BIT). También se pueden usar valores positivos y recorrer v de derecha a izquierda. El resultado final seguirá siendo el mismo.
Algoritmo:
1. Initialize inv_pair_cnt = 0 which will store the number of inversion pairs. 2. Store the tuple (-A[i][j] i j) in an array say v where A[i][j] is the element of the matrix A at position (i j). 3. Sort the array v according to the first element of the tuple i.e. according to the value of -A[i][j]. 4. Traverse the array v and do the following : - Initialize an array say 'pairs' to store the position (i j) of the tuples of v. - while the current tuple of v and all its adjacent tuples whose first value i.e. -A[i][j] is same do - Push the current tuple's position pair (i j) into 'pairs'. - Add to inv_pair_cnt the number of elements which are less than the current element(i.e. A[i][j]) and lie on the right side in the sorted array v by calling the query operation of BIT and passing i and j as arguments. - For each position pair (i j) stored in the array 'pairs' update the position (i j) in the 2D BIT by 1. 5. Finally inv_pair_cnt will contain the number of inversion pairs.
Implementación:
C++// C++ program to count the number of inversion // pairs in a 2D matrix #include
# Python3 program to count the number of inversion # pairs in a 2D matrix # for simplicity we are taking N as 4 N = 4 # Function to update a 2D BIT. It updates the # value of bit[l][r] by adding val to bit[l][r] def update(l r val bit): i = l while(i <= N): j = r while(j <= N): bit[i][j] += val j += j & -j i += i & -i # function to find cumulative sum upto # index (l r) in the 2D BIT def query(l r bit): ret = 0 i = l while(i > 0): j = r while(j > 0): ret += bit[i][j] j -= j & -j i -= i & -i return ret # function to count and return the number # of inversion pairs in the matrix def countInversionPairs(mat): # the 2D bit array and initialize it with 0. bit = [[0 for i in range(N + 1)] for j in range(N + 1)] # v will store the tuple (-mat[i][j] i j) v = [] # store the tuples in the vector v for i in range(N): for j in range(N): # Note that we are not using the pair # (0 0) because BIT update and query # operations are not done on index 0 v.append([-mat[i][j] [i + 1 j + 1]]) # sort the vector v according to the # first element of the tuple i.e. -mat[i][j] v.sort() # inv_pair_cnt will store the number of # inversion pairs inv_pair_cnt = 0 # traverse all the tuples of vector v i = 0 while (i < len(v)): curr = i # 'pairs' will store the position of each element # i.e. the pair (i j) of each tuple of the vector v pairs = [] # consider the current tuple in v and all its # adjacent tuples whose first value i.e. the # value of –mat[i][j] is same while (curr < len(v) and (v[curr][0] == v[i][0])): # push the position of the current element in 'pairs' pairs.append([v[curr][1][0] v[curr][1][1]]) # add the number of elements which are # less than the current element and lie on the right # side in the vector v inv_pair_cnt += query(v[curr][1][0] v[curr][1][1] bit) curr += 1 # traverse the 'pairs' vector for it in pairs: x = it[0] y = it[1] # update the position (x y) by 1 update(x y 1 bit) i = curr return inv_pair_cnt # Driver code mat = [[4 7 2 9 ][ 6 4 1 7 ] [ 5 3 8 1 ][3 2 5 6]] inv_pair_cnt = countInversionPairs(mat) print('The number of inversion pairs are :' inv_pair_cnt) # This code is contributed by shubhamsingh10
// C# program to count the number of inversion // Tuples in a 2D matrix using System; using System.Collections.Generic; class GFG { // for simplicity we are taking N as 4 static int N = 4; // Function to update a 2D BIT. It updates the // value of bit[l r] by adding val to bit[l r] static void update(int l int r int val int[] bit) { for (int x = l; x <= N; x += (x & -x)) for (int j = r; j <= N; j += j & -j) bit[x j] += val; } // function to find cumulative sum upto // index (l r) in the 2D BIT static int query(int l int r int[] bit) { int ret = 0; for (int x = l; x > 0; x -= (x & -x)) for (int j = r; j > 0; j -= (j & -j)) ret += bit[x j]; return ret; } // function to count and return the number // of inversion Tuples in the matrix static int countInversionTuples(int[] mat) { // the 2D bit array and initialize it with 0. int[ ] bit = new int[N + 1 N +1]; for (int x = 0; x <= N; x++) for (int y = 0; y <= N; y++) bit[x y] = 0; // v will store the tuple (-mat[i j] i j) List<Tuple<int Tuple<int int> > > v = new List<Tuple<int Tuple<int int> > >(); // store the tuples in the vector v for (int x = 0; x < N; ++x) for (int j = 0; j < N; ++j) // Note that we are not using the Tuple // (0 0) because BIT update and query // operations are not done on index 0 v.Add(Tuple.Create(-mat[x j] Tuple.Create(x+1 j+1))); // sort the vector v according to the // first element of the tuple i.e. -mat[i j] v.Sort(); // inv_Tuple_cnt will store the number of // inversion Tuples int inv_Tuple_cnt = 0; // traverse all the tuples of vector v int i = 0; while (i < v.Count) { int curr = i; // 'Tuples' will store the position of each element // i.e. the Tuple (i j) of each tuple of the vector v List<Tuple<int int>> Tuples = new List<Tuple<int int>>(); // consider the current tuple in v and all its // adjacent tuples whose first value i.e. the // value of –mat[i j] is same while (curr < v.Count && (v[curr].Item1 == v[i].Item1)) { // push the position of the current element in 'Tuples' Tuples.Add(Tuple.Create(v[curr].Item2.Item1 v[curr].Item2.Item2)); // add the number of elements which are // less than the current element and lie on the right // side in the vector v inv_Tuple_cnt += query(v[curr].Item2.Item1 v[curr].Item2.Item2 bit); curr++; } // traverse the 'Tuples' vector foreach (var it in Tuples) { int x = it.Item1; int y = it.Item2; // update the position (x y) by 1 update(x y 1 bit); } i = curr; } return inv_Tuple_cnt; } // Driver program public static void Main(string[] args) { int[ ] mat = { { 4 7 2 9 } { 6 4 1 7 } { 5 3 8 1 } { 3 2 5 6 } }; int inv_Tuple_cnt = countInversionTuples(mat); Console.WriteLine( 'The number of inversion Tuples are : ' + inv_Tuple_cnt); } } // This code is contributed by phasing17.
// JavaScript program to count the number of inversion // pairs in a 2D matrix // for simplicity we are taking N as 4 let N = 4 // Function to update a 2D BIT. It updates the // value of bit[l][r] by adding val to bit[l][r] function update(l r val bit) { let i = l while(i <= N) { let j = r while(j <= N) { bit[i][j] += val j += (j & -j) } i += (i & -i) } return bit } // function to find cumulative sum upto // index (l r) in the 2D BIT function query(l r bit) { let ret = 0 let i = l while(i > 0) { let j = r while(j > 0) { ret += bit[i][j] j -= (j & -j) } i -= (i & -i) } return ret } // function to count and return the number // of inversion pairs in the matrix function countInversionPairs(mat) { // the 2D bit array and initialize it with 0. let bit = new Array(N + 1) for (let i = 0; i <= N; i++) bit[i] = new Array(N + 1).fill(0) // v will store the tuple (-mat[i][j] i j) let v = [] // store the tuples in the vector v for (let i = 0; i < N; i++) for (var j = 0; j < N; j++) // Note that we are not using the pair // (0 0) because BIT update and query // operations are not done on index 0 v.push([-mat[i][j] [i + 1 j + 1]]) // sort the vector v according to the // first element of the tuple i.e. -mat[i][j] v.sort(function(a b) { return a[0] - b[0]}) // inv_pair_cnt will store the number of // inversion pairs let inv_pair_cnt = 0 // traverse all the tuples of vector v let i = 0 while (i < v.length) { let curr = i // 'pairs' will store the position of each element // i.e. the pair (i j) of each tuple of the vector v let pairs = [] // consider the current tuple in v and all its // adjacent tuples whose first value i.e. the // value of –mat[i][j] is same while (curr < v.length && (v[curr][0] == v[i][0])) { // push the position of the current element in 'pairs' pairs.push([v[curr][1][0] v[curr][1][1]]) // add the number of elements which are // less than the current element and lie on the right // side in the vector v inv_pair_cnt += query(v[curr][1][0] v[curr][1][1] bit) curr += 1 } // traverse the 'pairs' vector for (let it of pairs) { let x = it[0] let y = it[1] // update the position (x y) by 1 bit = update(x y 1 bit) } i = curr } return inv_pair_cnt } // Driver code let mat = [[4 7 2 9 ][ 6 4 1 7 ] [ 5 3 8 1 ][3 2 5 6]] let inv_pair_cnt = countInversionPairs(mat) console.log('The number of inversion pairs are ' inv_pair_cnt) // This code is contributed by phasing17
import java.util.*; class Main { static final int N = 4; static void update(int l int r int val int[][] bit) { for (int i = l; i <= N; i += i & -i) for (int j = r; j <= N; j += j & -j) bit[i][j] += val; } static long query(int l int r int[][] bit) { long ret = 0; for (int i = l; i > 0; i -= i & -i) for (int j = r; j > 0; j -= j & -j) ret += bit[i][j]; return ret; } static long countInversionPairs(int[][] mat) { int[][] bit = new int[N + 1][N + 1]; List<AbstractMap.SimpleEntry<Integer AbstractMap.SimpleEntry<Integer Integer>>> v = new ArrayList<>(); for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) v.add(new AbstractMap.SimpleEntry<Integer AbstractMap.SimpleEntry<Integer Integer>>(-mat[i][j] new AbstractMap.SimpleEntry<Integer Integer>(i + 1 j + 1))); Collections.sort(v new Comparator<AbstractMap.SimpleEntry<Integer AbstractMap.SimpleEntry<Integer Integer>>>() { @Override public int compare(AbstractMap.SimpleEntry<Integer AbstractMap.SimpleEntry<Integer Integer>> a AbstractMap.SimpleEntry<Integer AbstractMap.SimpleEntry<Integer Integer>> b) { return a.getKey().compareTo(b.getKey()); } }); long invPairCnt = 0; int i = 0; while (i < v.size()) { int curr = i; List<AbstractMap.SimpleEntry<Integer Integer>> pairs = new ArrayList<>(); while (curr < v.size() && (v.get(curr).getKey().equals(v.get(i).getKey()))) { pairs.add(v.get(curr).getValue()); invPairCnt += query(v.get(curr).getValue().getKey() v.get(curr).getValue().getValue() bit); curr++; } for (AbstractMap.SimpleEntry<Integer Integer> p : pairs) { int x = p.getKey(); int y = p.getValue(); update(x y 1 bit); } i = curr; } return invPairCnt; } public static void main(String[] args) { int[][] mat = {{4 7 2 9} {6 4 1 7} {5 3 8 1} {3 2 5 6}}; long invPairCnt = countInversionPairs(mat); System.out.println('The number of inversion pairs are: ' + invPairCnt); } } // This code is contributed by Prince Kumar
Producción
The number of inversion pairs are : 43
Complejidad del tiempo : O(log(NxN)) donde N es el tamaño de la matriz
Complejidad espacial : O(NxN)
Crear cuestionario