Dados dos arreglos A[] y B[] , y un entero K , la tarea es encontrar el número de formas de seleccionar dos subarreglos del mismo tamaño, uno de A y otro de B de modo que los subarreglos tengan al menos K pares de elementos iguales. (es decir, el número de pares (A[i], B[j]) en los dos subarreglos seleccionados tal que A[i] = B[j] >= K).
Ejemplos:
Entrada: A[] = {1, 2}, B[] = {1, 2, 3}, K = 1
Salida: 4
Las formas de seleccionar dos subarreglos son:
- [1], [1]
- [2], [2]
- [1, 2], [1, 2]
- [1, 2], [2, 3]
Entrada: A[] = {3, 2, 5, 21, 15, 2, 6}, B[] = {2, 1, 4, 3, 6, 7, 9}, K = 2
Salida: 7
Acercarse:
- En lugar de tratar con las dos arrays por separado, combinémoslas en forma de una array binaria tal que:
mat[i][j] = 0, if A[i] != B[j]
= 1, if A[i] = B[j]
- Ahora bien, si consideramos cualquier subarray de esta array, digamos de tamaño P × Q, es básicamente una combinación de un subarreglo de A de tamaño P y un subarreglo de B de tamaño Q. Como solo queremos verificar los subarreglos de igual tamaño, consideraremos solo subarrays cuadradas.
- Consideremos una subarray cuadrada con la esquina superior izquierda como (i, j) y la esquina inferior derecha como (i + tamaño, j + tamaño). Esto es equivalente a considerar los subarreglos A[i: i + tamaño] y B[j: j + tamaño]. Se puede observar que si estos dos subarreglos tendrán x pares de elementos iguales, entonces la subarray tendrá x 1 en ella.
- Así que recorra todos los elementos de la array (i, j) y considérelos como la esquina inferior derecha del cuadrado. Ahora, una forma es atravesar todos los tamaños posibles de la subarray y encontrar los tamaños que tienen suma >= k, pero esto será menos eficiente. Se puede observar que, por ejemplo, si una subarray S x S con (i, j) como esquina inferior derecha tiene suma >= k, entonces todas las subarrays cuadradas con tamaño >= S y (i, j) como esquina inferior derecha seguirán el propiedad.
- Entonces, en lugar de iterar para todos los tamaños en cada (i, j), solo aplicaremos la búsqueda binaria sobre el tamaño de la subarray cuadrada y encontraremos el tamaño más pequeño S tal que tenga suma >= K, y luego simplemente sumaremos las arrays con mayores longitudes de los lados. Se puede consultar
este artículo para ver cómo se evalúan las sumas de subarrays en tiempo constante usando sumas de prefijos 2D.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to count the
// number of ways to select equal
// sized subarrays such that they
// have atleast K common elements
#include <bits/stdc++.h>
using namespace std;
// 2D prefix sum for submatrix
// sum query for matrix
int prefix_2D[2005][2005];
// Function to find the prefix sum
// of the matrix from i and j
int subMatrixSum(int i, int j, int len)
{
return prefix_2D[i][j] -
prefix_2D[i][j - len] -
prefix_2D[i - len][j] +
prefix_2D[i - len][j - len];
}
// Function to count the number of ways
// to select equal sized subarrays such
// that they have atleast K common elements
int numberOfWays(int a[], int b[], int n,
int m, int k)
{
// Combining the two arrays
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i - 1] == b[j - 1])
prefix_2D[i][j] = 1;
else
prefix_2D[i][j] = 0;
}
}
// Calculating the 2D prefix sum
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
prefix_2D[i][j] += prefix_2D[i][j - 1];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
prefix_2D[i][j] += prefix_2D[i - 1][j];
}
}
int answer = 0;
// iterating through all
// the elements of matrix
// and considering them to
// be the bottom right
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// applying binary search
// over side length
int low = 1;
int high = min(i, j);
while (low < high) {
int mid = (low + high) >> 1;
// if sum of this submatrix >=k then
// new search space will be [low, mid]
if (subMatrixSum(i, j, mid) >= k) {
high = mid;
}
// else new search space
// will be [mid+1, high]
else {
low = mid + 1;
}
}
// Adding the total submatrices
if (subMatrixSum(i, j, low) >= k) {
answer += (min(i, j) - low + 1);
}
}
}
return answer;
}
// Driver Code
int main()
{
int N = 2, M = 3;
int A[N] = { 1, 2 };
int B[M] = { 1, 2, 3 };
int K = 1;
cout << numberOfWays(A, B, N, M, K);
return 0;
}
Java
// Java implementation to count the
// number of ways to select equal
// sized subarrays such that they
// have atleast K common elements
class GFG{
// 2D prefix sum for submatrix
// sum query for matrix
static int [][]prefix_2D = new int[2005][2005];
// Function to find the prefix sum
// of the matrix from i and j
static int subMatrixSum(int i, int j, int len)
{
return prefix_2D[i][j] -
prefix_2D[i][j - len] -
prefix_2D[i - len][j] +
prefix_2D[i - len][j - len];
}
// Function to count the number of ways
// to select equal sized subarrays such
// that they have atleast K common elements
static int numberOfWays(int a[], int b[], int n,
int m, int k)
{
// Combining the two arrays
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if (a[i - 1] == b[j - 1])
prefix_2D[i][j] = 1;
else
prefix_2D[i][j] = 0;
}
}
// Calculating the 2D prefix sum
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
prefix_2D[i][j] += prefix_2D[i][j - 1];
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
prefix_2D[i][j] += prefix_2D[i - 1][j];
}
}
int answer = 0;
// Iterating through all
// the elements of matrix
// and considering them to
// be the bottom right
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
// Applying binary search
// over side length
int low = 1;
int high = Math.min(i, j);
while (low < high)
{
int mid = (low + high) >> 1;
// If sum of this submatrix >=k then
// new search space will be [low, mid]
if (subMatrixSum(i, j, mid) >= k)
{
high = mid;
}
// Else new search space
// will be [mid+1, high]
else
{
low = mid + 1;
}
}
// Adding the total submatrices
if (subMatrixSum(i, j, low) >= k)
{
answer += (Math.min(i, j) - low + 1);
}
}
}
return answer;
}
// Driver Code
public static void main(String[] args)
{
int N = 2, M = 3;
int A[] = { 1, 2 };
int B[] = { 1, 2, 3 };
int K = 1;
System.out.print(numberOfWays(A, B, N, M, K));
}
}
// This code is contributed by Princi Singh
Python3
# Python3 implementation to count the # number of ways to select equal # sized subarrays such that they # have atleast K common element # 2D prefix sum for submatrix # sum query for matrix prefix_2D = [[0 for x in range (2005)] for y in range (2005)] # Function to find the prefix sum # of the matrix from i and j def subMatrixSum(i, j, length): return (prefix_2D[i][j] - prefix_2D[i][j - length] - prefix_2D[i - length][j] + prefix_2D[i - length][j - length]) # Function to count the number of ways # to select equal sized subarrays such # that they have atleast K common elements def numberOfWays(a, b, n, m, k): # Combining the two arrays for i in range (1, n + 1): for j in range (1, m + 1): if (a[i - 1] == b[j - 1]): prefix_2D[i][j] = 1 else: prefix_2D[i][j] = 0 # Calculating the 2D prefix sum for i in range (1, n + 1): for j in range (1, m + 1): prefix_2D[i][j] += prefix_2D[i][j - 1] for i in range (1, n + 1): for j in range (1, m + 1): prefix_2D[i][j] += prefix_2D[i - 1][j] answer = 0 # iterating through all # the elements of matrix # and considering them to # be the bottom right for i in range (1, n +1): for j in range (1, m + 1): # applying binary search # over side length low = 1 high = min(i, j) while (low < high): mid = (low + high) >> 1 # if sum of this submatrix >=k then # new search space will be [low, mid] if (subMatrixSum(i, j, mid) >= k): high = mid # else new search space # will be [mid+1, high] else: low = mid + 1 # Adding the total submatrices if (subMatrixSum(i, j, low) >= k): answer += (min(i, j) - low + 1) return answer # Driver Code if __name__ == "__main__": N = 2 M = 3 A = [1, 2] B = [1, 2, 3] K = 1 print (numberOfWays(A, B, N, M, K)) # This code is contributed by Chitranayal
C#
// C# implementation to count the
// number of ways to select equal
// sized subarrays such that they
// have atleast K common elements
using System;
class GFG{
// 2D prefix sum for submatrix
// sum query for matrix
static int [,]prefix_2D = new int[2005, 2005];
// Function to find the prefix sum
// of the matrix from i and j
static int subMatrixSum(int i, int j, int len)
{
return prefix_2D[i, j] -
prefix_2D[i, j - len] -
prefix_2D[i - len, j] +
prefix_2D[i - len, j - len];
}
// Function to count the number of ways
// to select equal sized subarrays such
// that they have atleast K common elements
static int numberOfWays(int []a, int []b, int n,
int m, int k)
{
// Combining the two arrays
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if (a[i - 1] == b[j - 1])
prefix_2D[i, j] = 1;
else
prefix_2D[i, j] = 0;
}
}
// Calculating the 2D prefix sum
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
prefix_2D[i, j] += prefix_2D[i, j - 1];
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
prefix_2D[i, j] += prefix_2D[i - 1, j];
}
}
int answer = 0;
// Iterating through all
// the elements of matrix
// and considering them to
// be the bottom right
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
// Applying binary search
// over side length
int low = 1;
int high = Math.Min(i, j);
while (low < high)
{
int mid = (low + high) >> 1;
// If sum of this submatrix >=k then
// new search space will be [low, mid]
if (subMatrixSum(i, j, mid) >= k)
{
high = mid;
}
// Else new search space
// will be [mid+1, high]
else
{
low = mid + 1;
}
}
// Adding the total submatrices
if (subMatrixSum(i, j, low) >= k)
{
answer += (Math.Min(i, j) - low + 1);
}
}
}
return answer;
}
// Driver Code
public static void Main(String[] args)
{
int N = 2, M = 3;
int []A = { 1, 2 };
int []B = { 1, 2, 3 };
int K = 1;
Console.Write(numberOfWays(A, B, N, M, K));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// javascript implementation to count the
// number of ways to select equal
// sized subarrays such that they
// have atleast K common elements
// 2D prefix sum for submatrix
// sum query for matrix
var prefix_2D = Array(2005);
// Function to find the prefix sum
// of the matrix from i and j
function subMatrixSum(i , j , len) {
return prefix_2D[i][j] - prefix_2D[i][j - len] - prefix_2D[i - len][j] + prefix_2D[i - len][j - len];
}
// Function to count the number of ways
// to select equal sized subarrays such
// that they have atleast K common elements
function numberOfWays(a , b , n , m , k) {
// Combining the two arrays
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
if (a[i - 1] == b[j - 1])
prefix_2D[i][j] = 1;
else
prefix_2D[i][j] = 0;
}
}
// Calculating the 2D prefix sum
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
prefix_2D[i][j] += prefix_2D[i][j - 1];
}
}
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
prefix_2D[i][j] += prefix_2D[i - 1][j];
}
}
var answer = 0;
// Iterating through all
// the elements of matrix
// and considering them to
// be the bottom right
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
// Applying binary search
// over side length
var low = 1;
var high = Math.min(i, j);
while (low < high) {
var mid = (low + high) >> 1;
// If sum of this submatrix >=k then
// new search space will be [low, mid]
if (subMatrixSum(i, j, mid) >= k) {
high = mid;
}
// Else new search space
// will be [mid+1, high]
else {
low = mid + 1;
}
}
// Adding the total submatrices
if (subMatrixSum(i, j, low) >= k) {
answer += (Math.min(i, j) - low + 1);
}
}
}
return answer;
}
// Driver Code
var N = 2, M = 3;
var A = [ 1, 2 ];
var B = [ 1, 2, 3 ];
for(i = 0;i<205;i++)
prefix_2D[i] = Array(205).fill(0);
var K = 1;
document.write(numberOfWays(A, B, N, M, K));
// This code contributed by Rajput-Ji
</script>
Producción:
4
Complejidad de tiempo: O(N * M * log(max(N, M)))