Dada una array arr[] de tamaño N . La tarea es encontrar si es posible hacer un árbol de búsqueda binaria con la array de elementos dada, de modo que el máximo común divisor de dos vértices conectados por una arista común sea > 1 . Si es posible, imprima Sí ; de lo contrario, imprima No.
Ejemplos:
Entrada: arr[] = {3, 6, 9, 18, 36, 108}
Salida: Sí
Este es uno de los posibles árboles de búsqueda binarios con una array dada.
Entrada: arr[] = {2, 17}
Salida: No
Enfoque: Sea DP(l, r, root) un DP que determine si es posible ensamblar un árbol con raíz en la raíz del subsegmento [l..r].
Es fácil ver que calcularlo requiere extraer tal raíz a la izquierda de [l..root – 1] y raíz a la derecha de [root + 1..right] tal que:
- mcd(una raíz , una raíz izquierda ) > 1
- gcd(una raíz , un derecho de raíz ) > 1
- DP(l, raíz-1, raíz izquierda ) = 1
- DP(raíz+1, r, raíz derecha ) = 1
Esto se puede hacer en O(r – l) siempre que tengamos todos los valores de DP(x, y, z) para todos los subsegmentos de [l..r]. Considerando un total de O(n 3 ) estados DP, la complejidad final es O(n 4 ) y eso es demasiado.
Convirtamos nuestro DP en DPnew(l, r, state) donde el estado puede ser 0 o 1. Inmediatamente resulta que DP(l, r, root) se hereda de DPnew(l, root-1, 1) y DPnuevo(raíz+1, r, 0). Ahora tenemos estados O(n 2 ), pero al mismo tiempo, todas las transiciones se realizan en tiempo lineal. Así la complejidad final es O(n 3 ) que es suficiente para pasar.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Maximum number of vertices
#define N 705
// To store is it possible at
// particular pace or not
int dp[N][N][2];
// Return 1 if from l to r, it is possible with
// the given state
int possibleWithState(int l, int r, int state, int a[])
{
// Base condition
if (l > r)
return 1;
// If it is already calculated
if (dp[l][r][state] != -1)
return dp[l][r][state];
// Choose the root
int root;
if (state == 1)
root = a[r + 1];
else
root = a[l - 1];
// Traverse in range l to r
for (int i = l; i <= r; i++) {
// If gcd is greater than one
// check for both sides
if (__gcd(a[i], root) > 1) {
int x = possibleWithState(l, i - 1, 1, a);
if (x != 1)
continue;
int y = possibleWithState(i + 1, r, 0, a);
if (x == 1 && y == 1)
return dp[l][r][state] = 1;
}
}
// If not possible
return dp[l][r][state] = 0;
}
// Function that return true if it is possible
// to make Binary Search Tree
bool isPossible(int a[], int n)
{
memset(dp, -1, sizeof dp);
// Sort the given array
sort(a, a + n);
// Check it is possible rooted at i
for (int i = 0; i < n; i++)
// Check at both sides
if (possibleWithState(0, i - 1, 1, a)
&& possibleWithState(i + 1, n - 1, 0, a)) {
return true;
}
return false;
}
// Driver code
int main()
{
int a[] = { 3, 6, 9, 18, 36, 108 };
int n = sizeof(a) / sizeof(a[0]);
if (isPossible(a, n))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static int __gcd(int a, int b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return __gcd(a - b, b);
return __gcd(a, b-a);
}
// Maximum number of vertices
static final int N = 705;
// To store is it possible at
// particular pace or not
static int dp[][][] = new int[N][N][2];
// Return 1 if from l to r, it is
// possible with the given state
static int possibleWithState(int l, int r,
int state, int a[])
{
// Base condition
if (l > r)
return 1;
// If it is already calculated
if (dp[l][r][state] != -1)
return dp[l][r][state];
// Choose the root
int root;
if (state == 1)
root = a[r + 1];
else
root = a[l - 1];
// Traverse in range l to r
for (int i = l; i <= r; i++)
{
// If gcd is greater than one
// check for both sides
if (__gcd(a[i], root) > 1)
{
int x = possibleWithState(l, i - 1, 1, a);
if (x != 1)
continue;
int y = possibleWithState(i + 1, r, 0, a);
if (x == 1 && y == 1)
return dp[l][r][state] = 1;
}
}
// If not possible
return dp[l][r][state] = 0;
}
// Function that return true if it is possible
// to make Binary Search Tree
static boolean isPossible(int a[], int n)
{
for(int i = 0; i < dp.length; i++)
for(int j = 0; j < dp[i].length; j++)
for(int k = 0; k < dp[i][j].length; k++)
dp[i][j][k]=-1;
// Sort the given array
Arrays.sort(a);
// Check it is possible rooted at i
for (int i = 0; i < n; i++)
// Check at both sides
if (possibleWithState(0, i - 1, 1, a) != 0 &&
possibleWithState(i + 1, n - 1, 0, a) != 0)
{
return true;
}
return false;
}
// Driver code
public static void main(String args[])
{
int a[] = { 3, 6, 9, 18, 36, 108 };
int n = a.length;
if (isPossible(a, n))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by
// Arnab Kundu
Python3
# Python3 implementation of the approach
import math
# Maximum number of vertices
N = 705
# To store is it possible at
# particular pace or not
dp = [[[-1 for z in range(2)]
for x in range(N)]
for y in range(N)]
# Return 1 if from l to r, it is
# possible with the given state
def possibleWithState(l, r, state, a):
# Base condition
if (l > r):
return 1
# If it is already calculated
if (dp[l][r][state] != -1):
return dp[l][r][state]
# Choose the root
root = 0
if (state == 1) :
root = a[r + 1]
else:
root = a[l - 1]
# Traverse in range l to r
for i in range(l, r + 1):
# If gcd is greater than one
# check for both sides
if (math.gcd(a[i], root) > 1):
x = possibleWithState(l, i - 1, 1, a)
if (x != 1):
continue
y = possibleWithState(i + 1, r, 0, a)
if (x == 1 and y == 1) :
return 1
# If not possible
return 0
# Function that return true if it is
# possible to make Binary Search Tree
def isPossible(a, n):
# Sort the given array
a.sort()
# Check it is possible rooted at i
for i in range(n):
# Check at both sides
if (possibleWithState(0, i - 1, 1, a) and
possibleWithState(i + 1, n - 1, 0, a)):
return True
return False
# Driver Code
if __name__ == '__main__':
a = [3, 6, 9, 18, 36, 108]
n = len(a)
if (isPossible(a, n)):
print("Yes")
else:
print("No")
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)
C#
// C# implementation of the approach
using System;
class GFG
{
static int __gcd(int a, int b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return __gcd(a - b, b);
return __gcd(a, b-a);
}
// Maximum number of vertices
static int N = 705;
// To store is it possible at
// particular pace or not
static int [,,]dp = new int[N, N, 2];
// Return 1 if from l to r, it is
// possible with the given state
static int possibleWithState(int l, int r,
int state, int []a)
{
// Base condition
if (l > r)
return 1;
// If it is already calculated
if (dp[l, r, state] != -1)
return dp[l, r, state];
// Choose the root
int root;
if (state == 1)
root = a[r + 1];
else
root = a[l - 1];
// Traverse in range l to r
for (int i = l; i <= r; i++)
{
// If gcd is greater than one
// check for both sides
if (__gcd(a[i], root) > 1)
{
int x = possibleWithState(l, i - 1, 1, a);
if (x != 1)
continue;
int y = possibleWithState(i + 1, r, 0, a);
if (x == 1 && y == 1)
return dp[l,r,state] = 1;
}
}
// If not possible
return dp[l,r,state] = 0;
}
// Function that return true
// if it is possible to make
// Binary Search Tree
static bool isPossible(int []a, int n)
{
for(int i = 0; i < dp.GetLength(0); i++)
for(int j = 0; j < dp.GetLength(1); j++)
for(int k = 0; k < dp.GetLength(2); k++)
dp[i, j, k]=-1;
// Sort the given array
Array.Sort(a);
// Check it is possible rooted at i
for (int i = 0; i < n; i++)
// Check at both sides
if (possibleWithState(0, i - 1, 1, a) != 0 &&
possibleWithState(i + 1, n - 1, 0, a) != 0)
{
return true;
}
return false;
}
// Driver code
public static void Main(String []args)
{
int []a = { 3, 6, 9, 18, 36, 108 };
int n = a.Length;
if (isPossible(a, n))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
function __gcd(a, b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return __gcd(a - b, b);
return __gcd(a, b-a);
}
// Maximum number of vertices
var N = 705;
// To store is it possible at
// particular pace or not
var dp = Array.from(Array(N), ()=>Array(N));
for(var i = 0; i<N; i++)
{
for(var j = 0; j<N; j++)
{
dp[i][j] = new Array(2).fill(-1);
}
}
// Return 1 if from l to r, it is
// possible with the given state
function possibleWithState(l, r, state,a)
{
// Base condition
if (l > r)
return 1;
// If it is already calculated
if (dp[l][r][state] != -1)
return dp[l][r][state];
// Choose the root
var root;
if (state == 1)
root = a[r + 1];
else
root = a[l - 1];
// Traverse in range l to r
for (var i = l; i <= r; i++)
{
// If gcd is greater than one
// check for both sides
if (__gcd(a[i], root) > 1)
{
var x = possibleWithState(l, i - 1, 1, a);
if (x != 1)
continue;
var y = possibleWithState(i + 1, r, 0, a);
if (x == 1 && y == 1)
return dp[l][r][state] = 1;
}
}
// If not possible
return dp[l][r][state] = 0;
}
// Function that return true
// if it is possible to make
// Binary Search Tree
function isPossible(a, n)
{
// Sort the given array
a.sort();
// Check it is possible rooted at i
for (var i = 0; i < n; i++)
// Check at both sides
if (possibleWithState(0, i - 1, 1, a) != 0 &&
possibleWithState(i + 1, n - 1, 0, a) != 0)
{
return true;
}
return false;
}
// Driver code
var a = [3, 6, 9, 18, 36, 108];
var n = a.length;
if (isPossible(a, n))
document.write("Yes");
else
document.write("No");
// This code is contributed by itsok.
</script>
Producción:
Yes
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA