Minimice la suma cuadrada de las arrays dadas intercambiando elementos en los mismos índices

 Dadas dos arrays arrA[] y arrB[] que contienen N enteros cada una. Realice la siguiente operación cualquier número de veces (posiblemente cero):

• Seleccione cualquier índice i (0 <= i <= N-1) y
• Intercambiar arrA[i] y arrB[i] .

La tarea es encontrar la suma mínima del cuadrado de las sumas de arreglos, es decir, si Sa y Sb son la suma de arreglos de arrA[] y arrB [] después del intercambio, entonces encuentre el valor mínimo posible de (Sa) ² + (Sb) ² .

Ejemplos:

Entrada: N = 4, arrA[ ] = { 3, 6, 6, 6 }, arrB[ ] = { 2, 7, 4, 1 }
Salida: 613
Explicación: 
Si realizamos la operación para i = 0 e i = 2, obtenemos las arrays resultantes como arrA[] = { 2, 6, 4, 6 } y arrB[] = { 3, 7, 6, 1 }. 
Por lo tanto, Sa = 18 y Sb = 17. 
Entonces, la suma de sus cuadrados es (18) ² + (17) ² = 613, que es el mínimo posible.

Entrada: N = 4, arrA[ ] = { 6, 7, 2, 4 }, arrB[ ] = { 2, 5, 3, 5 }
Salida: 578

Enfoque ingenuo: El enfoque ingenuo consiste en comprobar todos los casos posibles. Para cada índice: 

• O intercambie esos elementos de ese índice o no.
  • Calcular la suma de las arrays.
  • Encuentre el valor de la suma del cuadrado de las sumas de arrays.
• El mínimo de los valores es la respuesta.

Complejidad de Tiempo: O(2 ^N * N)
Espacio Auxiliar: O(1) 

Enfoque eficiente: El enfoque eficiente se basa en la siguiente idea:

Utilice la memorización para almacenar el resultado ya calculado hasta un índice y una suma de array que evitará el cálculo repetido y reducirá el tiempo total.

Siga los pasos mencionados a continuación para implementar la idea anterior:

• Cree una array dp[] para almacenar la suma calculada de los cuadrados de la suma de la array hasta algún índice i y las sumas de la array Sa y Sb .
• Para cada índice hay dos opciones: intercambiar los elementos o no.
• Realice esta operación de intercambio recursivamente y:
  • Si para algún índice el valor ya está calculado, devuelva ese valor.
  • De lo contrario, calcule la suma y almacene el valor mínimo posible para ese índice.
• Devuelve la suma mínima entre todos como respuesta.

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

// C++ code to implement the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Using map of vector and int in place of
// multidimensional array to store calculated
// values to prevent memory limitexceed error
map<vector<int>, int> dp;
 
// Function to find min total square of sum
// from both arrays
int min_total_square_sum(int arrA[], int arrB[],
                         int i, int Sa,
                         int Sb, int n)
{
    // Base case
    if (i >= n) {
        int temp = Sa * Sa + Sb * Sb;
 
        return temp;
    }
 
    vector<int> v = { i, Sa, Sb };
 
    // If already calculated directly
    // return the stored value
    if (dp.count(v)) {
        return dp[v];
    }
 
    // Case-1: when we don't swap the elements
    int t1 = min_total_square_sum(
        arrA, arrB, i + 1, Sa + arrA[i],
        Sb + arrB[i], n);
 
    // Case-2: when we swap the elements
    int t2 = min_total_square_sum(
        arrA, arrB, i + 1, Sa + arrB[i],
        Sb + arrA[i], n);
 
    // Returning minimum of the two cases
    return dp[v] = min(t1, t2);
}
 
// Driver code
int main()
{
    int N = 4;
    int arrA[] = { 6, 7, 2, 4 };
    int arrB[] = { 2, 5, 3, 5 };
 
    int Sa{ 0 }, Sb{ 0 };
 
    // Function call
    cout << min_total_square_sum(arrA, arrB,
                                 0, Sa, Sb, N);
    return 0;
}

import java.util.*;
import java.io.*;
 
class GFG{
 
    public static TreeMap<ArrayList<Integer>, Integer> dp = new TreeMap<ArrayList<Integer>, Integer>(new Comparator<ArrayList<Integer>>() {
        public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2){
            for(int i=0 ; i<2 ; i++){
                if(o1.get(i).equals(o2.get(i))) continue;
                return o1.get(i).compareTo(o2.get(i));
            }
            return o1.get(2).compareTo(o2.get(2));
        }
    });
 
    // Function to find remaining element
    public static int min_total_square_sum(ArrayList<Integer> arrA, ArrayList<Integer> arrB, int i,int Sa,int Sb, int n){
 
        // Base case
        if(i>=n){
            int temp = Sa * Sa + Sb * Sb;
            return temp;
        }
 
        ArrayList<Integer> v = new ArrayList<Integer>(
            List.of(i, Sa, Sb)
        );
         
        // if already calculated directly
        // return the stored value
        if(dp.containsKey(v)){
            return dp.get(v);
        }
 
        // Case-1: when we don't swap the elements
        int t1 = min_total_square_sum(arrA, arrB, i + 1, Sa + arrA.get(i), Sb + arrB.get(i), n);
 
        // Case-2: when we swap the elements
        int t2 = min_total_square_sum(arrA, arrB, i + 1, Sa + arrB.get(i), Sb + arrA.get(i), n);
 
        // Returning minimum of the two cases
        dp.put(v, Math.min(t1,t2));
        return dp.get(v);
    }
 
    // Driver code
    public static void main(String args[])
    {
        // Size of array
        int N = 4;
        ArrayList<Integer> arrA = new ArrayList<Integer>(
            List.of(6, 7, 2, 4)
        );
        ArrayList<Integer> arrB = new ArrayList<Integer>(
            List.of(2, 5, 3, 5)
        );
 
        int Sa = 0, Sb = 0;
 
        // Function call
        System.out.println(min_total_square_sum(arrA, arrB, 0, Sa, Sb, N));
    }
}
 
// This code is contributed by subhamgoyal2014.

# Python3 code to implement the above approach
 
# Using map of vector and int in place of
# multidimensional array to store calculated
# values to prevent memory limitexceed error
dp = {}
 
# Function to find min total square of sum
# from both arrays
def min_total_square_sum(arrA, arrB, i, Sa, Sb, n):
 
        # Base case
    if (i >= n):
        temp = Sa * Sa + Sb * Sb
        return temp
 
    v = (i, Sa, Sb)
 
    # If already calculated directly
    # return the stored value
    if (v in dp):
        return dp[v]
 
        # Case-1: when we don't swap the elements
    t1 = min_total_square_sum(arrA, arrB, i + 1, Sa + arrA[i],
                              Sb + arrB[i], n)
 
    # Case-2: when we swap the elements
    t2 = min_total_square_sum(arrA, arrB, i + 1, Sa + arrB[i],
                              Sb + arrA[i], n)
 
    # Returning minimum of the two cases
    dp[v] = min(t1, t2)
    return dp[v]
 
# Driver code
if __name__ == "__main__":
 
    N = 4
    arrA = [6, 7, 2, 4]
    arrB = [2, 5, 3, 5]
 
    Sa, Sb = 0, 0
 
    # Function call
    print(min_total_square_sum(arrA, arrB, 0, Sa, Sb, N))
 
    # This code is contributed by rakeshsahni

<script>
     // JavaScript code for the above approach
 
     // Using map of vector and int in place of
     // multidimensional array to store calculated
     // values to prevent memory limitexceed error
     let dp = new Map();
 
     // Function to find min total square of sum
     // from both arrays
     function min_total_square_sum(arrA, arrB,
         i, Sa, Sb, n)
     {
      
         // Base case
         if (i >= n) {
             let temp = Sa * Sa + Sb * Sb;
 
             return temp;
         }
 
         let v = [i, Sa, Sb];
 
         // If already calculated directly
         // return the stored value
         if (dp.has(v)) {
             return dp.get(vs);
         }
 
         // Case-1: when we don't swap the elements
         let t1 = min_total_square_sum(
             arrA, arrB, i + 1, Sa + arrA[i],
             Sb + arrB[i], n);
 
         // Case-2: when we swap the elements
         let t2 = min_total_square_sum(
             arrA, arrB, i + 1, Sa + arrB[i],
             Sb + arrA[i], n);
 
         // Returning minimum of the two cases
         dp.set(v, Math.min(t1, t2))
         return dp.get(v);
     }
 
     // Driver code
     let N = 4;
     let arrA = [6, 7, 2, 4];
     let arrB = [2, 5, 3, 5];
 
     let Sa = 0, Sb = 0;
 
     // Function call
     document.write(min_total_square_sum(arrA, arrB,
         0, Sa, Sb, N));
 
// This code is contributed by Potta Lokesh
 
 </script>

578

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