Retos - 006: Mínimo producto escalar

Nivel de dificultad aproximado (1 a 5): 3  

Enunciado del problema

Dados dos vectores v1=(x1,x2,...,xn) y v2=(y1,y2,...,yn), su producto escalar es un número, que se calcula como x1y1+x2y2+...+xnyn.

Supongamos que puedes permutar las coordenadas de cada vector como desee. Debes escoger dos permutaciones de tal manera que el producto escalar de los dos nuevos vectores sea el menor posible, y mostrar ese producto escalar mínimo.

La primera línea del archivo de entrada contiene el número de casos de prueba. Para cada caso de prueba, la primera línea contiene n número entero, que es la cantidad de coordenadas de cada vector. Las dos líneas siguientes contienen n enteros cada una, que son las coordenadas de v1 y v2, respectivamente.

Para cada caso de prueba, la salida será una línea "Case #X: Y", donde X es el número de caso de prueba (contando a partir de 1), e Y es el producto escalar mínimo de todas las permutaciones de los dos vectores dados.

Límites

En cuanto a los posibles valores de entrada, en el "conjunto de datos pequeño", habrá 1.000 casos, de no más de 8 coordenadas, con valores entre -1.000 y 1.000; en el "conjunto grande", habrá 10 casos, de entre 100 y 800 coordenadas, con valores entre -100.000 y 100.000;

Nota: el programa no debe avisar al usuario con mensajes como "Introduzca un número". Debe leer directamente el número que introduzca el usuario y la respuesta debe ser exactamente como se puede comprobar en el ejemplo ("Case #n: ...").

Entradas y salidas de ejemplo 
Ejemplo de entrada:
2
3
1 3 -5
-2 4 1
5
1 2 3 4 5
1 0 1 0 1

Salida correspondiente
Case #1: -25
Case #2: 6
Procedencia del reto

Original en: Google Code Jam 2008 - Fase 1A, problema A

Aporta tu solución

Aportar una solución

Tu nombre (si quieres que aparezca):
Tu web/blog (si quieres que incluyamos un enlace a ella):
Tu e-mail (no se mostrará; si quieres que te avisemos cuando esté publicado):
¿Eres humano? ¿Cuánto es 3 menos dos?
Lenguaje
Fuente:

Ejemplo de solución en C# 

// Ejemplo de solución para el reto 006
// (Google Code Jam 2008 - Fase 1A, problema A)
// Por Cris F
 
// Mínimo producto escalar de dos vectores
// 10-05-2012
 
using System;
 
public class ProductoMinimoEscalar
{
    public static void InicializarVector(string lineaLeida, ref long[] v)
    {
        char[] delimitador = { ' ' };
        string[] vectorEnString = lineaLeida.Split(delimitador);
        for (int i = 0; i < vectorEnString.Length; i++)
        {
            v[i] = Convert.ToInt64(vectorEnString[i]);
        }
    }
 
 
    public static long CalcularMinimoProductoEscalar(ref long []v1, ref long[] v2)
    {
        long productoEscalar=0;
        Array.Sort(v1);
        Array.Sort(v2);
        Array.Reverse(v2);
        for (int i = 0; i < v1.Length; i++)
            productoEscalar += v1[i] * v2[i];
        return productoEscalar;
    }
 
 
    static void Main(string[] args)
    {
        int numeroCasos, numeroCoordenadas;
        long menorProductoEscalar;
 
        numeroCasos = Convert.ToInt32(Console.ReadLine());
 
        for (int i = 0; i < numeroCasos; i++)
        {
            numeroCoordenadas = Convert.ToInt32(Console.ReadLine());
 
            long[] vector1 = new long[numeroCoordenadas];
            InicializarVector(Console.ReadLine(), ref vector1);
 
            long[] vector2 = new long[numeroCoordenadas];
            InicializarVector(Console.ReadLine(), ref vector2);
 
            menorProductoEscalar = CalcularMinimoProductoEscalar(ref vector1, ref vector2);
            Console.WriteLine("Case #{0}: {1}",i+1,menorProductoEscalar);
        }
    }
}
 

Ejemplo de solución en Java 

// Ejemplo de solución para el reto 006
// Mínimo producto escalar de dos vectores
// Por Eduardo Antonio Espinoza Llontop
// 12-Feb-2015
 
import java.util.Scanner;
public class ProductoMinimoEscalar {
    public static void main(String[] args) {
        Scanner br=new Scanner(System.in);
        int numcasos=Integer.parseInt(br.next());
        int[][] vectores=new int[20][9];
        for (int i = 0; i < numcasos; i++) {
            vectores[2*i][0]=Integer.parseInt(br.next());
            for (int j = 0; j < vectores[2*i][0]; j++) {
                vectores[2*i][j+1]=Integer.parseInt(br.next());
            }
            vectores[2*i+1][0]=vectores[2*i][0];
            for (int j = 0; j < vectores[2*i+1][0]; j++) {
                vectores[2*i+1][j+1]=Integer.parseInt(br.next());
            }
        }
        for (int i = 0; i < numcasos; i++) {
            for (int j = 2; j <= vectores[2*i][0]+1; j++) {
                for (int k = 1; k <= vectores[2*i][0]-j+1; k++) {
                    if(vectores[2*i][k]>vectores[2*i][k+1]){
                        int aux=vectores[2*i][k];
                        vectores[2*i][k]=vectores[2*i][k+1];
                        vectores[2*i][k+1]=aux;
                    }
                }
            }
            for (int j = 2; j <= vectores[2*i+1][0]+1; j++) {
                for (int k = 1; k <= vectores[2*i+1][0]-j+1; k++) {
                    if(vectores[2*i+1][k]<vectores[2*i+1][k+1]){
                        int aux=vectores[2*i+1][k];
                        vectores[2*i+1][k]=vectores[2*i+1][k+1];
                        vectores[2*i+1][k+1]=aux;
                    }
                }
            }
            int suma=0;
            for (int j = 1; j < vectores[2*i+1][0]+1; j++) {
                suma=suma+(vectores[2*i][j]*vectores[2*i+1][j]);
            }
            System.out.println("Caso #"+(i+1)+": "+suma);
        }
    }
}