Cuente formas de eliminar pares de una array de modo que los elementos restantes se puedan agrupar en pares verticales u horizontales

Dado un entero K y una array cuadrada mat[][] de tamaño N * N con elementos del rango [1, K] , la tarea es contar formas de eliminar pares de elementos de array distintos de modo que los elementos restantes se puedan organizar en pares vertical u horizontalmente.

Ejemplos:

Entrada: mat[][] = {{1, 2}, {3, 4}}, K = 4
Salida: 4
Explicación:
elimine la fila {1, 2}. Por lo tanto, los elementos restantes son {3, 4}, que se pueden organizar en un grupo horizontal de 2.
De manera similar, eliminar los pares (1, 3), (3, 4) y (2, 4) también puede formar tales arreglos.

Entrada: mat[][] = {{1, 2, 3}, {2, 2, 2}, {1, 2, 2}}, K = 3
Salida: 0

Enfoque: La idea se basa en las siguientes observaciones:

• Si N es impar, no importa qué par se elimine, la array restante no se puede cubrir con las arrays más pequeñas. Esto se debe a que, al eliminar cualquier par de la array, los elementos restantes serán impares, no es posible cubrirlos con una array de tamaño 2×1 o 1×2.
• Para otros casos, cubrir la array restante después de eliminar un par (a, b) solo es posible si la suma del índice de fila, i y el índice de columna, j de a es par y la de b es impar o viceversa.

Siga los pasos a continuación para resolver el problema:

• Si el tamaño de la array es impar , imprima 0 ya que no puede haber arreglos posibles.
• De lo contrario, verifique lo siguiente:
  • Inicialice una variable ans como 0 para almacenar el número de pares necesarios.
  • Inicializar una array auxiliar, dp[][] de tamaño K×2 , dp[i][0] indicando el número de ocurrencias de i en la array mat[][] cuya suma del índice de fila y el índice de columna es par, y dp[i][1] que indica el número de ocurrencias de i en mat[][] cuya suma del índice de fila y el índice de columna es impar.
  • Recorra la array mat [][] filas usando el índice de fila i y el índice de columna j y si la suma de i y j es par, entonces incremente dp[mat[i][j] – 1][0] en 1, de lo contrario, incremente dp[mat[i][j] – 1][1] en 1 .
  • Iterar sobre el rango [0, K – 1] usando la variable i e iterar anidado en el rango [i + 1, K – 1] usando la variable j :
    • Agregue el valor de dp[i][0] * dp[j][1] a ans ya que el valor de ambos bloques difiere y (i + j) y el valor de uno es impar y el valor (i + j) del otro incluso.
    • Agregue el valor de dp[i][1] * dp[j][0] a ans ya que el valor de ambos bloques difiere y (i + j) el valor de uno es par y (i + j) el valor del otro es impar
• Después de los pasos anteriores, imprima el valor de ans como resultado.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count ways to remove pairs
// such that the remaining elements can
// be arranged in pairs vertically or horizontally
void numberofpairs(vector<vector<int> > v,
                   int k)
{
    // Store the size of matrix
    int n = v.size();
 
    // If N is odd, then no
    // such pair exists
    if (n % 2 == 1) {
        cout << 0;
        return;
    }
 
    // Store the number of
    // required pairs
    int ans = 0;
 
    // Initialize an auxiliary
    // matrix and fill it with 0s
    int dp[k][2];
 
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < 2; j++) {
            dp[i][j] = 0;
        }
    }
 
    // Traverse the matrix v[][]
    for (int i = 0; i < n; i++) {
 
        for (int j = 0; j < n; j++) {
 
            // Check if i+j is odd or even
            if ((i + j) % 2 == 0)
 
                // Increment the value
                // dp[v[i][j]-1][0] by 1
                dp[v[i][j] - 1][0]++;
            else
 
                // Increment the value
                // dp[v[i][j]-1][1] by 1
                dp[v[i][j] - 1][1]++;
        }
    }
 
    // Iterate in range[0, k-1] using i
    for (int i = 0; i < k; i++) {
 
        // Iterate in range[i+1, k-1] using j
        for (int j = i + 1; j < k; j++) {
 
            // Update the ans
            ans += dp[i][0] * dp[j][1];
            ans += dp[i][1] * dp[j][0];
        }
    }
 
    // Print the answer
    cout << ans;
}
 
// Driver Code
int main()
{
    vector<vector<int> > mat = { { 1, 2 }, { 3, 4 } };
    int K = 4;
    numberofpairs(mat, K);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
class GFG{
 
// Function to count ways to remove pairs
// such that the remaining elements can
// be arranged in pairs vertically or horizontally
static void numberofpairs(int[][] v, int k)
{
   
    // Store the size of matrix
    int n = v.length;
 
    // If N is odd, then no
    // such pair exists
    if (n % 2 == 1) {
        System.out.println(0);
        return;
    }
 
    // Store the number of
    // required pairs
    int ans = 0;
 
    // Initialize an auxiliary
    // matrix and fill it with 0s
    int dp[][] = new int[k][2];
 
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < 2; j++) {
            dp[i][j] = 0;
        }
    }
 
    // Traverse the matrix v[][]
    for (int i = 0; i < n; i++) {
 
        for (int j = 0; j < n; j++) {
 
            // Check if i+j is odd or even
            if ((i + j) % 2 == 0)
 
                // Increment the value
                // dp[v[i][j]-1][0] by 1
                dp[v[i][j] - 1][0]++;
            else
 
                // Increment the value
                // dp[v[i][j]-1][1] by 1
                dp[v[i][j] - 1][1]++;
        }
    }
 
    // Iterate in range[0, k-1] using i
    for (int i = 0; i < k; i++) {
 
        // Iterate in range[i+1, k-1] using j
        for (int j = i + 1; j < k; j++) {
 
            // Update the ans
            ans += dp[i][0] * dp[j][1];
            ans += dp[i][1] * dp[j][0];
        }
    }
 
    // Print the answer
    System.out.println(ans);
}
 
// Driver Code
public static void main(String[] args)
{
    int[][] mat = { { 1, 2 }, { 3, 4 } };
    int K = 4;
    numberofpairs(mat, K);
}
}
 
// This code is contributed by susmitakundogoaldanga.

# Python3 program for the above approach
 
# Function to count ways to remove pairs
# such that the remaining elements can
# be arranged in pairs vertically or horizontally
def numberofpairs(v, k) :
 
    # Store the size of matrix
    n = len(v)
  
    # If N is odd, then no
    # such pair exists
    if (n % 2 == 1) :
        print(0)
        return
  
    # Store the number of
    # required pairs
    ans = 0
  
    # Initialize an auxiliary
    # matrix and fill it with 0s
    dp = [[0 for i in range(2)] for j in range(k)]
  
    for i in range(k) :
        for j in range(2) :
            dp[i][j] = 0
  
    # Traverse the matrix v[][]
    for i in range(n) :
        for j in range(n) :
  
            # Check if i+j is odd or even
            if ((i + j) % 2 == 0) :
  
                # Increment the value
                # dp[v[i][j]-1][0] by 1
                dp[v[i][j] - 1][0] += 1
            else :
  
                # Increment the value
                # dp[v[i][j]-1][1] by 1
                dp[v[i][j] - 1][1] += 1
  
    # Iterate in range[0, k-1] using i
    for i in range(k) :
  
        # Iterate in range[i+1, k-1] using j
        for j in range(i + 1, k) :
  
            # Update the ans
            ans += dp[i][0] * dp[j][1]
            ans += dp[i][1] * dp[j][0]
  
    # Print the answer
    print(ans)
     
    # Driver code
mat = [ [ 1, 2 ], [ 3, 4 ] ]
K = 4
numberofpairs(mat, K)
 
# This code is contributed by divyeshrabdiya07.

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
     
    // Function to count ways to remove pairs
    // such that the remaining elements can
    // be arranged in pairs vertically or horizontally
    static void numberofpairs(List<List<int> > v,
                       int k)
    {
       
        // Store the size of matrix
        int n = v.Count;
      
        // If N is odd, then no
        // such pair exists
        if (n % 2 == 1) {
            Console.Write(0);
            return;
        }
      
        // Store the number of
        // required pairs
        int ans = 0;
      
        // Initialize an auxiliary
        // matrix and fill it with 0s
        int[,] dp = new int[k, 2];
      
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < 2; j++) {
                dp[i, j] = 0;
            }
        }
      
        // Traverse the matrix v[][]
        for (int i = 0; i < n; i++) {
      
            for (int j = 0; j < n; j++) {
      
                // Check if i+j is odd or even
                if ((i + j) % 2 == 0)
      
                    // Increment the value
                    // dp[v[i][j]-1][0] by 1
                    dp[v[i][j] - 1, 0]++;
                else
      
                    // Increment the value
                    // dp[v[i][j]-1][1] by 1
                    dp[v[i][j] - 1, 1]++;
            }
        }
      
        // Iterate in range[0, k-1] using i
        for (int i = 0; i < k; i++) {
      
            // Iterate in range[i+1, k-1] using j
            for (int j = i + 1; j < k; j++) {
      
                // Update the ans
                ans += dp[i, 0] * dp[j, 1];
                ans += dp[i, 1] * dp[j, 0];
            }
        }
      
        // Print the answer
        Console.Write(ans);
    }
 
  // Driver code
  static void Main()
  {
    List<List<int> > mat = new List<List<int>>();
    mat.Add(new List<int>(new int[]{1, 2}));
    mat.Add(new List<int>(new int[]{3, 4}));
    int K = 4;
    numberofpairs(mat, K);
  }
}
 
// This code is contributed by divyesh072019.

<script>
 
    // Javascript program for the above approach
     
    // Function to count ways to remove pairs
    // such that the remaining elements can
    // be arranged in pairs
    // vertically or horizontally
    function numberofpairs(v, k)
    {
 
        // Store the size of matrix
        let n = v.length;
 
        // If N is odd, then no
        // such pair exists
        if (n % 2 == 1) {
            document.write(0);
            return;
        }
 
        // Store the number of
        // required pairs
        let ans = 0;
 
        // Initialize an auxiliary
        // matrix and fill it with 0s
        let dp = new Array(k);
 
        for (let i = 0; i < k; i++) {
            dp[i] = new Array(2);
            for (let j = 0; j < 2; j++) {
                dp[i][j] = 0;
            }
        }
 
        // Traverse the matrix v[][]
        for (let i = 0; i < n; i++) {
 
            for (let j = 0; j < n; j++) {
 
                // Check if i+j is odd or even
                if ((i + j) % 2 == 0)
 
                    // Increment the value
                    // dp[v[i][j]-1][0] by 1
                    dp[v[i][j] - 1][0]++;
                else
 
                    // Increment the value
                    // dp[v[i][j]-1][1] by 1
                    dp[v[i][j] - 1][1]++;
            }
        }
 
        // Iterate in range[0, k-1] using i
        for (let i = 0; i < k; i++) {
 
            // Iterate in range[i+1, k-1] using j
            for (let j = i + 1; j < k; j++) {
 
                // Update the ans
                ans += dp[i][0] * dp[j][1];
                ans += dp[i][1] * dp[j][0];
            }
        }
 
        // Print the answer
        document.write(ans + "</br>");
    }
     
    let mat = [ [ 1, 2 ], [ 3, 4 ] ];
    let K = 4;
    numberofpairs(mat, K);
 
</script>

4

Complejidad de Tiempo: O(N ² + K ² )
Espacio Auxiliar: O(K)