Pasante/FTE del Instituto de Investigación de Semiconductores de Samsung (Software SSIR) | Conjunto-2

Hay N Globos marcados con el valor Bi (donde B(i…N)). 
El usuario recibirá un arma con N balas y el usuario debe disparar N veces. 
Cuando cualquier globo explota, sus globos adyacentes se vuelven uno al lado del otro. 
El usuario debe obtener los puntos más altos para obtener el premio y la puntuación comienza en 0. 
A continuación se muestra la condición para calcular la puntuación. 
Cuando el globo Bi explota, la puntuación será un producto de Bi-1 y Bi+1 (puntuación = Bi-1 * Bi+1). 
Cuando el globo Bi explota y solo queda el globo presente, la puntuación será Bi-1. 
Cuando el globo Bi explota y solo está presente el globo correcto, la puntuación será Bi+1. 
Cuando el Globo Bi explote y no haya Globos izquierdo y derecho presentes, la puntuación será Bi. 
Escriba un programa para obtener el máximo de puntos.
 

Example: 
Input: B[] = {1, 2, 3, 4}
Output: 20
Explanation:
For max score:
3 explodes, score= 4*2=8 (product of adjacent balloons) 
2 explodes score= 4*1 + 8 = 12 (product of adjacent balloons) 
1 explodes score=  4 + 12= 16  (only 4 is left on the left side)
4 explodes score = 4 + 16 = 20 (no balloons left so add 4)
score =20
other combinations will result in lesser scores.

Análisis: 
1) El objetivo es encontrar la puntuación máxima 
2) La puntuación máxima depende de los puntos del vecino, sin embargo, no hay una manera fácil de encontrar qué secuencia da la puntuación máxima, por lo que la única forma es encontrar todas las secuencias posibles de las que se pueda obtener el máximo. eso. 
3) Como el orden importa en secuencia para la entrada N, ¡podemos tener N! secuencias, es decir. nPn formas (primer globo N formas, segundo N-1 formas…último globo 1 formas N*(N-1)(N-2)..2*1= N!
Complejidad: 
generar toda la secuencia O(N!) 
Para obtener el puntaje para 1 secuencia, para cada globo en secuencia, necesitamos vecinos izquierdo y derecho, en el peor de los casos, se necesita un recorrido completo en la array, por lo que la complejidad es O (N * N) 
La complejidad total es O (N!) * O (N * N) ) (nota: el cálculo se ha realizado al final de cada secuencia) 
50 TC, N 50 * es O(N! * N*N) => 50 * 100 * 10! => 5000 * 3628800 => 1.5 * 10^10 esto no se puede ejecutar en 3 segundos dados (10^9 instrucciones por segundo). 
Por lo tanto, debe buscar el pseudocódigo de optimización
para generar todas las secuencias: 
 

INPUT[N]
CHOICE[N] <= -1 //initialize to -1
Permute(0)
Permute(Position)
{
   // stop condition
   If ( all balloon shot )
   {
     Compute the score for this sequence in CHOICE[]
     If score better than previous then store
   }
 
   For i:0~N-1
   {
     If (ith balloon not selected // CHOICE[i]==-1)
     {
        Select ith balloon  // CHOICE[Position]= i 
        Permute (Position+1)
        Unselect ith balloon// CHOICE[Position]= -1
     }
   }
}

Optimización: 
Podemos ver en el algoritmo anterior que se llevan a cabo 2 operaciones principales 
(1) generar todas las secuencias O(N!) 
(2) calcular la puntuación para cada secuencia O(N*N) 
No podemos optimizar el algoritmo generar todas las secuencias sin embargo podemos reducir aún más la parte informática. 
Optimización de la parte de computación 
Si podemos optimizar la búsqueda del vecino a O(1), podemos reducir la parte de computación a O(N), lo que hace que nuestro algoritmo se ejecute en 1,5 * 10^9, lo que se puede lograr en 3 segundos. 
Alternativamente, podemos calcular el puntaje para cada globo elegido para disparar «sobre la marcha» aquí encontrar vecino es extra cuando cada vez que se elige globo que puede ser O (N) y también reducir 1.5 * 10 ^ 9
Algoritmo para obtener vecinos: 
método ingenuo por O(N): 
Vecino(elegido) 
Para Izquierda: elegido-1~0 si el globo Izquierdo no se elige romper; 
Para la derecha: elegido + 1 ~ N-1 si el globo derecho no se elige romper; 
if(Derecha==N) 
Derecha=-1; 
Volver Izquierda y derecha;
Forma optimizada por O (1) 1. 
Mantenga 2 arrays izquierda [] y derecha [] que contienen vecinos de cada globo. 
2. Inicialmente, los vecinos son conocidos, ya que el i-ésimo globo a la izquierda es i-1 y el derecho es i+1, excepto que el primer globo no tendrá izquierda y el último no tendrá derecha. 
3. Cuando se elige el globo, podemos obtener su derecha e izquierda mediante O(1) 
4. Cuando se dispara un globo, actualice el vecino izquierdo [i+1] = izquierdo [i] derecho [i-1] = derecho [i] 
Nota : 
En lugar de llamar a la nueva función para obtener la izquierda y la derecha, calcular  la izquierda y la derecha dentro de la fracción
recursiva  reducirá muchas instrucciones ocultas, ya que llamar al compilador de funciones nuevas agregará muchas instrucciones que se pueden reducir  . puntuación variable a la función recursiva  Cuando se elige un globo para disparar, obtenga los vecinos izquierdo y derecho  Calcule la puntuación obtenida al disparar el globo elegido  Agregue esto a la puntuación dada y pase al siguiente nivel  Pseudocódigo: 

 
Permute(Position, score)
{
   // stop condition
   If( all balloon shot )
   {
     If score better than previous then store
   }
 
   For i:0~N-1
   {
      If (ith balloon not selected // CHOICE[i]==-1)
      {
         Select ith balloon  // CHOICE[Position]= i 
         Gain = Compute the gain by shooting ith balloon 
         Permute (Position+1, score+ Gain)
         Unselect ith balloon// CHOICE[Position]= -1
      }
   }
} 

Enfoque alternativo optimizado (divide y vencerás) y programación dinámica
El problema al principio no parece un problema de divide y vencerás. 
Motivo: si seleccionamos un globo (para reventar), nuestra array se dividirá en dos sub-arrays. Pero estos dos subconjuntos no serán subproblemas independientes. 
Ejemplo 
Considere 5 globos B1, .., B5. Bursting B3 divide la array en dos sub-arrays {B1, B2} y {B4, B5}. Pero estos dos subconjuntos no son independientes entre sí, es decir. la puntuación para la explosión de B4 depende del orden de explosión de {B1, B2}. 
Idea clave 
1. Para dividir el problema en dos mitades, debemos asegurarnos de que cualquier acción (explosión del globo) en una mitad no afecte la puntuación de la otra mitad. 
2. Si arreglamos un globo y nos aseguramos de no reventarlo hasta que reventamos todos los globos a la izquierda y todo el globo a la derecha, entonces podemos dividir el problema en dos subproblemas.
Ejemplo 
Considere el caso anterior de cinco globos. Ahora, en lugar de reventar B3, arreglamos que reventaremos B3 después de todos los globos, lo que hace que {B1, B2} y {B4, B5} sean independientes entre sí, es decir, la puntuación para reventar B4 ahora es independiente de {B1, B2}. 
 

Otra forma de visualizar el enfoque de divide y vencerás es pensar en el problema al revés. El problema paralelo sería dar un conjunto de n globos desinflados cada uno con una puntuación, elige el orden en el que vas a inflar el globo. La puntuación por inflar el globo es igual al producto de la puntuación unida a los globos ubicados a la izquierda ya la derecha del mencionado globo.
A continuación se muestra la solución recursiva:
 

#include <iostream>
using namespace std;
 
// recursive function to generate scores
int getmaxscore(int arr[], int l, int r, int n)
{
    int mscore = 0;
    for (int i = l + 1; i < r; i++) {
 
        // to permute through all cases
        int cs = getmaxscore(arr, l, i, n) + getmaxscore(arr, i, r, n);
        if (l == 0 && r == n)
            cs = cs + arr[i];
        else
            cs = cs + (arr[l] * arr[r]);
 
        if (cs > mscore)
            mscore = cs;
    }
    return mscore;
}
 
int main() // driver function
{
    int n = 4; // no of balloons
 
    // assigning scores to each balloon 1-based indexing
    // arr[0]=1 because to calculate score when no
    //             balloons are left after popping
    // arr[5]=1 because to calculate score when no
    //             balloons are left after popping
    // scores of balloons are assigned from 1 to 4 i.e 1 to n
    int arr[] = { 1, 1, 2, 3, 4, 1 };
 
    /* for input input arr[n+2],
      arr[0]=1 && arr[n+1]=1
      cin>>n;
      for(int i=1;i<=n;i++)
         cin>>arr[i]; */
 
    cout << getmaxscore(arr, 0, n + 1, n + 1) << "\n";
 
    return 0;
}

Output:
20