Dada una array de números y una constante k, minimice el tamaño de la array con las siguientes reglas para eliminar elementos.
- Se pueden eliminar exactamente tres elementos de una sola vez.
- Los tres elementos eliminados deben ser adyacentes en la array, es decir, arr[i], arr[i+1], arr[i+2]. Y el segundo elemento debe ser k mayor que el primero y el tercer elemento debe ser k mayor que el segundo, es decir, arr[i+1] – arr[i] = k y arr[i+2]-arr[i+1] = k.
Ejemplo:
Input: arr[] = {2, 3, 4, 5, 6, 4}, k = 1
Output: 0
We can actually remove all elements.
First remove 4, 5, 6 => We get {2, 3, 4}
Now remove 2, 3, 4 => We get empty array {}
Input: arr[] = {2, 3, 4, 7, 6, 4}, k = 1
Output: 3
We can only remove 2 3 4
Fuente: https://code.google.com/codejam/contest/4214486/dashboard#s=p2
Le recomendamos encarecidamente que minimice su navegador y pruebe esto primero.
Para cada elemento arr[i] hay dos posibilidades.
1) O bien no se elimina el elemento.
2) Se elimina el elemento OR (si sigue las reglas de eliminación). Cuando se elimina un elemento, hay de nuevo dos posibilidades.
…..a) Puede eliminarse directamente, es decir, la inicial arr[i+1] es arr[i]+k y arr[i+2] es arr[i] + 2*k.
…..b) Existen x e y tales que arr[x] – arr[i] = k, arr[y] – arr[x] = k, y subarreglos “arr[i+1…x-1]” & “arr[x+1…y-1]” se puede eliminar por completo.
A continuación se muestra el algoritmo recursivo basado en la idea anterior.
// Returns size of minimum possible size of arr[low..high]
// after removing elements according to given rules
findMinSize(arr[], low, high, k)
// If there are less than 3 elements in arr[low..high]
1) If high-low+1 < 3, return high-low+1
// Consider the case when 'arr[low]' is not considered as
// part of any triplet to be removed. Initialize result
// using this case
2) result = 1 + findMinSize(arr, low+1, high)
// Case when 'arr[low]' is part of some triplet and removed
// Try all possible triplets that have arr[low]
3) For all i from low+1 to high
For all j from i+1 to high
Update result if all of the following conditions are met
a) arr[i] - arr[low] = k
b) arr[j] - arr[i] = k
c) findMinSize(arr, low+1, i-1, k) returns 0
d) findMinSize(arr, i+1, j-1, k) also returns 0
e) Result calculated for this triplet (low, i, j)
is smaller than existing result.
4) Return result
La complejidad temporal de la solución anterior es exponencial. Si dibujamos el árbol de recurrencia completo, podemos observar que muchos subproblemas se resuelven una y otra vez. Dado que los mismos subproblemas se vuelven a llamar, este problema tiene la propiedad Superposición de subproblemas. Al igual que otros problemas típicos de programación dinámica (DP) , los cálculos de los mismos subproblemas se pueden evitar mediante la construcción de una array temporal dp[][] para almacenar los resultados de los subproblemas. A continuación se muestra una solución basada en programación dinámica
A continuación se muestra la implementación de la idea anterior. La implementación se basa en la memorización, es decir, es recursiva y utiliza una tabla de búsqueda dp[][] para comprobar si un subproblema ya está resuelto o no.
C++
// C++ program to find size of minimum possible array after
// removing elements according to given rules
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
// dp[i][j] denotes the minimum number of elements left in
// the subarray arr[i..j].
int dp[MAX][MAX];
int minSizeRec(int arr[], int low, int high, int k)
{
// If already evaluated
if (dp[low][high] != -1)
return dp[low][high];
// If size of array is less than 3
if ( (high-low + 1) < 3)
return high-low +1;
// Initialize result as the case when first element is
// separated (not removed using given rules)
int res = 1 + minSizeRec(arr, low+1, high, k);
// Now consider all cases when first element forms a triplet
// and removed. Check for all possible triplets (low, i, j)
for (int i = low+1; i<=high-1; i++)
{
for (int j = i+1; j <= high; j++ )
{
// Check if this triplet follows the given rules of
// removal. And elements between 'low' and 'i' , and
// between 'i' and 'j' can be recursively removed.
if (arr[i] == (arr[low] + k) &&
arr[j] == (arr[low] + 2*k) &&
minSizeRec(arr, low+1, i-1, k) == 0 &&
minSizeRec(arr, i+1, j-1, k) == 0)
{
res = min(res, minSizeRec(arr, j+1, high, k));
}
}
}
// Insert value in table and return result
return (dp[low][high] = res);
}
// This function mainly initializes dp table and calls
// recursive function minSizeRec
int minSize(int arr[], int n, int k)
{
memset(dp, -1, sizeof(dp));
return minSizeRec(arr, 0, n-1, k);
}
// Driver program to test above function
int main()
{
int arr[] = {2, 3, 4, 5, 6, 4};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 1;
cout << minSize(arr, n, k) << endl;
return 0;
}
Java
// Java program to find size of
// minimum possible array after
// removing elements according
// to given rules
class GFG
{
static int MAX = 1000;
// dp[i][j] denotes the minimum
// number of elements left in
// the subarray arr[i..j].
static int dp[][] = new int[MAX][MAX];
static int minSizeRec(int arr[], int low,
int high, int k)
{
// If already evaluated
if (dp[low][high] != -1)
{
return dp[low][high];
}
// If size of array is less than 3
if ((high - low + 1) < 3)
{
return high - low + 1;
}
// Initialize result as the
// case when first element is
// separated (not removed
// using given rules)
int res = 1 + minSizeRec(arr,
low + 1, high, k);
// Now consider all cases when
// first element forms a triplet
// and removed. Check for all
// possible triplets (low, i, j)
for (int i = low + 1; i <= high - 1; i++)
{
for (int j = i + 1; j <= high; j++)
{
// Check if this triplet
// follows the given rules of
// removal. And elements
// between 'low' and 'i' , and
// between 'i' and 'j' can
// be recursively removed.
if (arr[i] == (arr[low] + k) &&
arr[j] == (arr[low] + 2 * k) &&
minSizeRec(arr, low + 1, i - 1, k) == 0 &&
minSizeRec(arr, i + 1, j - 1, k) == 0)
{
res = Math.min(res, minSizeRec(arr, j + 1, high, k));
}
}
}
// Insert value in table and return result
return (dp[low][high] = res);
}
// This function mainly initializes
// dp table and calls recursive
// function minSizeRec
static int minSize(int arr[], int n, int k)
{
for (int i = 0; i < MAX; i++)
{
for (int j = 0; j < MAX; j++)
{
dp[i][j] = -1;
}
}
return minSizeRec(arr, 0, n - 1, k);
}
// Driver code
public static void main(String[] args)
{
int arr[] = {2, 3, 4, 5, 6, 4};
int n = arr.length;
int k = 1;
System.out.println(minSize(arr, n, k));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find size of # minimum possible array after # removing elements according to given rules MAX=1000 dp=[[-1 for i in range(MAX)] for i in range(MAX)] # dp[i][j] denotes the minimum number of elements left in # the subarray arr[i..j]. def minSizeRec(arr,low,high,k): # If already evaluated if dp[low][high] != -1: return dp[low][high] # If size of array is less than 3 if (high-low + 1) < 3: return (high-low + 1) # Initialize result as the case when first element is # separated (not removed using given rules) res = 1 + minSizeRec(arr, low+1, high, k) # Now consider all cases when # first element forms a triplet # and removed. Check for all possible # triplets (low, i, j) for i in range(low+1,high): for j in range(i+1,high+1): # Check if this triplet follows the given rules of # removal. And elements between 'low' and 'i' , and # between 'i' and 'j' can be recursively removed. if (arr[i]==(arr[low]+k) and arr[j] == (arr[low] + 2*k) and minSizeRec(arr, low+1, i-1, k) == 0 and minSizeRec(arr, i+1, j-1, k) == 0): res=min(res,minSizeRec(arr,j+1,high,k) ) # Insert value in table and return result dp[low][high] = res return res # This function mainly initializes dp table and calls # recursive function minSizeRec def minSize(arr,n,k): dp=[[-1 for i in range(MAX)] for i in range(MAX)] return minSizeRec(arr, 0, n-1, k) # Driver program to test above function if __name__=='__main__': arr=[2, 3, 4, 5, 6, 4] n=len(arr) k=1 print(minSize(arr,n,k)) # this code is contributed by sahilshelangia
C#
// C# program to find size of
// minimum possible array after
// removing elements according
// to given rules
using System;
class GFG
{
static int MAX = 1000;
// dp[i,j] denotes the minimum
// number of elements left in
// the subarray arr[i..j].
static int [,]dp = new int[MAX, MAX];
static int minSizeRec(int []arr, int low,
int high, int k)
{
// If already evaluated
if (dp[low, high] != -1)
{
return dp[low, high];
}
// If size of array is less than 3
if ((high - low + 1) < 3)
{
return high - low + 1;
}
// Initialize result as the
// case when first element is
// separated (not removed
// using given rules)
int res = 1 + minSizeRec(arr,
low + 1, high, k);
// Now consider all cases when
// first element forms a triplet
// and removed. Check for all
// possible triplets (low, i, j)
for (int i = low + 1; i <= high - 1; i++)
{
for (int j = i + 1; j <= high; j++)
{
// Check if this triplet
// follows the given rules of
// removal. And elements
// between 'low' and 'i' , and
// between 'i' and 'j' can
// be recursively removed.
if (arr[i] == (arr[low] + k) &&
arr[j] == (arr[low] + 2 * k) &&
minSizeRec(arr, low + 1, i - 1, k) == 0 &&
minSizeRec(arr, i + 1, j - 1, k) == 0)
{
res = Math.Min(res, minSizeRec(arr, j + 1, high, k));
}
}
}
// Insert value in table and return result
return (dp[low, high] = res);
}
// This function mainly initializes
// dp table and calls recursive
// function minSizeRec
static int minSize(int []arr, int n, int k)
{
for (int i = 0; i < MAX; i++)
{
for (int j = 0; j < MAX; j++)
{
dp[i, j] = -1;
}
}
return minSizeRec(arr, 0, n - 1, k);
}
// Driver code
public static void Main(String[] args)
{
int []arr = {2, 3, 4, 5, 6, 4};
int n = arr.Length;
int k = 1;
Console.WriteLine(minSize(arr, n, k));
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find size of
// minimum possible array after
// removing elements according
// to given rules
let MAX = 1000;
// dp[i][j] denotes the minimum
// number of elements left in
// the subarray arr[i..j].
let dp = new Array(MAX);
for(let i = 0; i < MAX; i++)
{
dp[i] = new Array(MAX);
for(let j = 0; j < MAX; j++)
{
dp[i][j] = 0;
}
}
function minSizeRec(arr, low, high, k)
{
// If already evaluated
if (dp[low][high] != -1)
{
return dp[low][high];
}
// If size of array is less than 3
if ((high - low + 1) < 3)
{
return high - low + 1;
}
// Initialize result as the
// case when first element is
// separated (not removed
// using given rules)
let res = 1 + minSizeRec(arr, low + 1, high, k);
// Now consider all cases when
// first element forms a triplet
// and removed. Check for all
// possible triplets (low, i, j)
for (let i = low + 1; i <= high - 1; i++)
{
for (let j = i + 1; j <= high; j++)
{
// Check if this triplet
// follows the given rules of
// removal. And elements
// between 'low' and 'i' , and
// between 'i' and 'j' can
// be recursively removed.
if (arr[i] == (arr[low] + k) &&
arr[j] == (arr[low] + 2 * k) &&
minSizeRec(arr, low + 1, i - 1, k) == 0 &&
minSizeRec(arr, i + 1, j - 1, k) == 0)
{
res = Math.min(res, minSizeRec(arr, j + 1, high, k));
}
}
}
// Insert value in table and return result
return (dp[low][high] = res);
}
// This function mainly initializes
// dp table and calls recursive
// function minSizeRec
function minSize(arr, n, k)
{
for (let i = 0; i < MAX; i++)
{
for (let j = 0; j < MAX; j++)
{
dp[i][j] = -1;
}
}
return minSizeRec(arr, 0, n - 1, k);
}
let arr = [2, 3, 4, 5, 6, 4];
let n = arr.length;
let k = 1;
document.write(minSize(arr, n, k));
// This code is contributed by mukesh07.
</script>
Producción:
0
Este artículo es una contribución de Ekta Goel . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA