Desafío Ryckeboer #1: 3SUM

Problemas
#1

Desafíos “Ryckeboer”

Inspirado en los Desafíos “Dal Lago”, llegan los Desafíos “Ryckeboer” :mage:, cuyo nombre hace referencia al honorable miembro del jurado, Hugo Ryckeboer, quien sin duda es uno de los grandes responsables de que a lo largo de todos estos años los problemas presentados en la Olimpíada sean tanto desafiantes como interesantes.

Estos desafíos están pensados para los usuarios más experimentados del foro y aunque su dificultad irá variando, deberían ser considerablemente más difíciles que los desafíos “Dal Lago”.

Motivado por el problema planteado a la hora de presentar el uso de Sets en C++ :face_with_monocle:

Dados N números enteros y un número adicional X, ver si hay dos números que juntos sumen X.

Inaugura como primer problema en la serie de Desafíos a venir, la siguiente “variante” del problema anterior…

Desafío “Ryckeboer” #1:

Dado un conjunto \mathcal{A} de n números enteros, y un número arbitrario x fijo, decidir si existen tres números en el conjunto dado que sumen x.

Ejemplo:

Si el conjunto dado es \Large \mathcal{A} =\left \{6,1,3,5,4 \right \}, y se toma \Large x = 8, entonces la respuesta es positiva. Pues podemos escribir a 8 como 8 = 1+3+4, todos ellos elementos del conjunto. Por otro lado, si tomamos \Large x = 4, la respuesta es negativa, pues ningún subconjunto de 3 elementos suma 4 (aunque 4 sea un elemento de \mathcal{A} y 4 = 1+3)

Complejidad esperada: \mathcal{O}(n^2)

Pista

Resolver el problema de 2SUM (el problema motivador) en \mathcal{O}(n) si los números del conjunto están en un arreglo ordenado. Y luego usarlo como subrutina para resolver 3SUM (el problema del desafío) en \mathcal{O}(n^2).

Aclaraciones

  1. La idea es proponer posibles soluciones y discutirlas.
  2. No hace falta poner “código”. Alcanza con la idea del algoritmo.
4 Me gusta
COMPETENCIA 11 de Febrero : Lista de problemas - CodeForces
#2

Jajaja copada la idea!!! :muscle: :clap:

1 me gusta
#3

La idea que usé para esta solución fue la de mantener un número fijo mientras buscaba formar con otros dos la suma faltante. Es decir, teniendo unos iteradores i, j y k , mantuve i fijo mientras trataba de formar x-A_i con los elementos no usados(siendo A_i el i-gésimo elemento del conjunto A).
Si ordenamos el conjunto y variamos i de a uno y comenzando por el primer elemento de A, el problema se vuelve, para cada valor de i, un 2SUM con todos los elementos de índices mayores a i.
Con 2SUm, hablo de este problema:

Para el 2SUM, existe una solución en \mathcal{O(n)} si tenemos el conjunto ordenado. Sigue una breve explicación de esta.
Teniendo dos índices a y b que indican al primer y al último elemento del conjunto(A_a = A_0 y A_b = A_{n-1}). Si la suma de ellos es mayor al valor esperado, en vez de tomar el último valor tomaremos el anterior(b = b-1), y si es menor, en vez del primero tomamos el siguiente(a = a+1). Así continuamos hasta que encontremos el valor(A_a+A_b = x) o hasta a \geq b. Con esto nos cercioramos de encontrar el par si es que este existe.

Volviendo al problema de 3SUM. Dado que el iterador i recorre casi todo A, y por cada valor de este debemos realizar una operación de \mathcal{O(n)} , la complejidad del algoritmo resulta en \mathcal{O(n^2)} . Si bien también debemos ordenar el conjunto al comienzo, esto nos lleva \mathcal{O(n * \log n)} , y todo junto tomaría \mathcal{O(n * \log n + n^2)} , lo cual en definitiva tratamos como \mathcal{O(n^2)} .

Implementación en C++

Tomando un vector A como entrada y teniendo x como una variable.

        sort(A.begin(), A.end());
        int i, j, k;
        for(i = 0; i < A.size()-2; i++){
            j = i + 1;
            k = A.size()-1;
            while(j < k){
                if( A[i]+A[j]+A[k] > x ){
                    k--;
                }else if( A[i]+A[j]+A[k] < x ){
                    j++;
                }else{
                    cout << "Es Posible" << '\n';
                    break;
                }
            }
        }

Cualquier duda, si algo no se entendió bien o si encuentran algún error, son bienvenidos a responder.

3 Me gusta
#4

Genial :smiley:

Como premio, y honrando a la persona que le da el nombre a estos desafíos (y para ponerle un poco de humor también) te ganaste la prestigiosa “Insignia Ryckeboer” :medal_military:

InsigniaRyckeboer
InsigniaRyckeboer1200×600 536 KB

1 me gusta
#5

¡Excelente explicación! Me gusta mucho que hayas hecho la explicación con el código correspondiente.
Como comentario, ojo con el break cuando encontras la solución, fijate que solo sale del while, y el for podría encontrar otra solución.
También notemos que ahí buscás 3SUM con 3 números distintos. Podríamos no pedir que los números sean distintos ( a + a + a = x ) y sería casi igual el código.

2 Me gusta
#6

Jajaja, muchas gracias. La usaré con orgullo :face_with_monocle:

#7

Cierto, lo de las varias soluciones lo había visto, anteriormente era en realidad un flag lo que indicaba si era posible o no, así que que hubiera varias soluciones no afectaba, pero como está, tenés razón. Y lo de cuáles pueden ser los números, no lo había considerado, muchas gracias, estaré atento al enunciado :smiley:
¡Muchas gracias por sus respuestas!

1 me gusta