Cuente secuencias de corchetes regulares distintas que no son N periódicas

Posted on by Rudeus Greyrat

Dado un número entero N , la tarea es encontrar el número de secuencias de corchetes distintas que se pueden formar usando 2 * N corchetes de modo que la secuencia no sea N-periódica .

Se dice que una secuencia de corchetes str de longitud 2 * N es N-periódica si la secuencia se puede dividir en dos substrings iguales que tienen la misma secuencia de corchetes regular .
Una secuencia de paréntesis regular es una secuencia de la siguiente manera:

  • Una string vacía es una secuencia de paréntesis regular.
  • Si s & t son secuencias de corchetes regulares, entonces s + t es una secuencia de corchetes regulares.

Ejemplos:

Entrada: N = 3 
Salida: 5 
Explicación: 
Habrá 5 secuencias de paréntesis regulares distintas de longitud 2 * N =()()(),()(()), (())(), (()() ), ((())) 
Ahora, ninguna de las secuencias es N-periódica. Por lo tanto, la salida es 5.

Entrada: N = 4 
Salida: 12 
Explicación: 
Habrá 14 secuencias de paréntesis regulares distintas de longitud 2*N que son 
()()()(),()()(()),()(())( ),()(()()),()((())), (())()(), (())(()), (()())(), (()()()), (()(())), ((()))(), ((())()), ((()())), (((()))) 
De estas 14 secuencias regulares, dos de ellas son N periódicas, que son 
()()()() y (())(()). Tienen un período de N. 
Por lo tanto, las distintas secuencias de paréntesis regulares de longitud 2 * N que no son N-periódicas son 14 – 2 = 12.

Enfoque: La idea es calcular el número total de secuencias de corchetes regulares posibles de longitud 2 * N y luego restarle el número de secuencias de corchetes que son N-periódicas . A continuación se muestran los pasos:

  1. Para encontrar el número de secuencias de paréntesis regulares de longitud 2*N , usa la fórmula del número catalán .
  2. Para que una secuencia de longitud 2*N sea N periódica, N debe ser par porque si N es impar, entonces la secuencia de longitud 2*N no puede ser una secuencia regular y tener un período de N al mismo tiempo.
  3. Dado que la concatenación de dos secuencias de corchetes no regulares similares no puede hacer que una secuencia sea regular, ambas subsecuencias de longitud N deben ser regulares.
  4. Reduzca el número de secuencias de corchetes regulares de longitud N (si N es par) del número de secuencias de corchetes regulares de longitud 2*N para obtener el resultado deseado.

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function that finds the value of
// Binomial Coefficient C(n, k)
unsigned long int
binomialCoeff(unsigned int n,
              unsigned int k)
{
    unsigned long int res = 1;
 
    // Since C(n, k) = C(n, n - k)
    if (k > n - k)
        k = n - k;
 
    // Calculate the value of
    // [n*(n - 1)*---*(n - k + 1)] /
    // [k*(k - 1)*---*1]
    for (int i = 0; i < k; ++i) {
        res *= (n - i);
        res /= (i + 1);
    }
 
    // Return the C(n, k)
    return res;
}
 
// Binomial coefficient based function to
// find nth catalan number in O(n) time
unsigned long int catalan(unsigned int n)
{
    // Calculate value of 2nCn
    unsigned long int c
        = binomialCoeff(2 * n, n);
 
    // Return C(2n, n)/(n+1)
    return c / (n + 1);
}
 
// Function to find possible ways to
// put balanced  parenthesis in an
// expression of length n
unsigned long int findWays(unsigned n)
{
    // If n is odd, not possible to
    // create any valid parentheses
    if (n & 1)
        return 0;
 
    // Otherwise return n/2th
    // Catalan Number
    return catalan(n / 2);
}
 
void countNonNPeriodic(int N)
{
 
    // Difference between counting ways
    // of 2*N and N is the result
    cout << findWays(2 * N)
                - findWays(N);
}
 
// Driver Code
int main()
{
    // Given value of N
    int N = 4;
 
    // Function Call
    countNonNPeriodic(N);
 
    return 0;
}

Java

// Java program for above approach
import java.io.*;
 
class GFG{
     
// Function that finds the value of
// Binomial Coefficient C(n, k)
static long binomialCoeff(int n, int k)
{
    long res = 1;
 
    // Since C(n, k) = C(n, n - k)
    if (k > n - k)
        k = n - k;
 
    // Calculate the value of
    // [n*(n - 1)*---*(n - k + 1)] /
    // [k*(k - 1)*---*1]
    for(int i = 0; i < k; ++i)
    {
        res *= (n - i);
        res /= (i + 1);
    }
 
    // Return the C(n, k)
    return res;
}
 
// Binomial coefficient based function to
// find nth catalan number in O(n) time
static long catalan(int n)
{
     
    // Calculate value of 2nCn
    long c = binomialCoeff(2 * n, n);
 
    // Return C(2n, n)/(n+1)
    return c / (n + 1);
}
 
// Function to find possible ways to
// put balanced parenthesis in an
// expression of length n
static long findWays(int n)
{
     
    // If n is odd, not possible to
    // create any valid parentheses
    if ((n & 1) == 1)
        return 0;
 
    // Otherwise return n/2th
    // Catalan Number
    return catalan(n / 2);
}
 
static void countNonNPeriodic(int N)
{
     
    // Difference between counting ways
    // of 2*N and N is the result
    System.out.println(findWays(2 * N) -
                       findWays(N));
}
 
// Driver code
public static void main (String[] args)
{
     
    // Given value of N
    int N = 4;
     
    // Function call
    countNonNPeriodic(N);
}
}
 
// This code is contributed by offbeat

Python3

# Python3 program for
# the above approach
 
# Function that finds the value of
# Binomial Coefficient C(n, k)
def binomialCoeff(n, k):
    res = 1
  
    # Since C(n, k) = C(n, n - k)
    if (k > n - k):
        k = n - k
  
    # Calculate the value of
    # [n*(n - 1)*---*(n - k + 1)] /
    # [k*(k - 1)*---*1]
    for i in range(k):
     
        res = res * (n - i)
        res = res // (i + 1)
  
    # Return the C(n, k)
    return res
  
# Binomial coefficient based function to
# find nth catalan number in O(n) time
def catalan(n):
      
    # Calculate value of 2nCn
    c = binomialCoeff(2 * n, n)
  
    # Return C(2n, n)/(n+1)
    return c // (n + 1)
  
# Function to find possible ways to
# put balanced parenthesis in an
# expression of length n
def findWays(n):
 
    # If n is odd, not possible to
    # create any valid parentheses
    if ((n & 1) == 1):
        return 0
       
    # Otherwise return n/2th
    # Catalan Number
    return catalan(n // 2)
   
def countNonNPeriodic(N):
      
    # Difference between counting ways
    # of 2*N and N is the result
    print(findWays(2 * N) - findWays(N))
 
# Driver code
# Given value of N
N = 4
      
# Function call
countNonNPeriodic(N)
 
# This code is contributed by divyeshrabadiya07

C#

// C# program for above approach
using System;
using System.Collections.Generic; 
 
class GFG{
   
// Function that finds the value of
// Binomial Coefficient C(n, k)
static long binomialCoeff(int n, int k)
{
    long res = 1;
  
    // Since C(n, k) = C(n, n - k)
    if (k > n - k)
        k = n - k;
  
    // Calculate the value of
    // [n*(n - 1)*---*(n - k + 1)] /
    // [k*(k - 1)*---*1]
    for(int i = 0; i < k; ++i)
    {
        res *= (n - i);
        res /= (i + 1);
    }
  
    // Return the C(n, k)
    return res;
}
  
// Binomial coefficient based function to
// find nth catalan number in O(n) time
static long catalan(int n)
{
      
    // Calculate value of 2nCn
    long c = binomialCoeff(2 * n, n);
  
    // Return C(2n, n)/(n+1)
    return c / (n + 1);
}
  
// Function to find possible ways to
// put balanced parenthesis in an
// expression of length n
static long findWays(int n)
{
      
    // If n is odd, not possible to
    // create any valid parentheses
    if ((n & 1) == 1)
        return 0;
  
    // Otherwise return n/2th
    // Catalan Number
    return catalan(n / 2);
}
  
static void countNonNPeriodic(int N)
{
      
    // Difference between counting ways
    // of 2*N and N is the result
    Console.Write(findWays(2 * N) -
                  findWays(N));
}
   
// Driver Code
public static void Main(string[] args)
{
      
    // Given value of N
    int N = 4;
      
    // Function call
    countNonNPeriodic(N);
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
 
// Javascript program for the above approach
 
// Function that finds the value of
// Binomial Coefficient C(n, k)
function binomialCoeff(n, k)
{
    let res = 1;
 
    // Since C(n, k) = C(n, n - k)
    if (k > n - k)
        k = n - k;
 
    // Calculate the value of
    // [n*(n - 1)*---*(n - k + 1)] /
    // [k*(k - 1)*---*1]
    for (let i = 0; i < k; ++i) {
        res *= (n - i);
        res /= (i + 1);
    }
 
    // Return the C(n, k)
    return res;
}
 
// Binomial coefficient based function to
// find nth catalan number in O(n) time
function catalan(n)
{
    // Calculate value of 2nCn
    let c = binomialCoeff(2 * n, n);
 
    // Return C(2n, n)/(n+1)
    return c / (n + 1);
}
 
// Function to find possible ways to
// put balanced parenthesis in an
// expression of length n
function findWays(n)
{
    // If n is odd, not possible to
    // create any valid parentheses
    if (n & 1)
        return 0;
 
    // Otherwise return n/2th
    // Catalan Number
    return catalan(n / 2);
}
 
function countNonNPeriodic(N)
{
 
    // Difference between counting ways
    // of 2*N and N is the result
    document.write(findWays(2 * N)
                - findWays(N));
}
 
// Driver Code
 
    // Given value of N
    let N = 4;
 
    // Function Call
    countNonNPeriodic(N);
 
 
// This code is contributed by Mayank Tyagi
 
</script>
Producción: 

12

Complejidad temporal: O(N) 
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por architaggarwal023 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *