Codility Problema 3.c — TapeEquilibrium
Solución de problemas de lógica computacional de la pagina https://app.codility.com/
Ingles
A non-empty array A consisting of N integers is given. Array A represents numbers on a tape.
Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], …, A[P − 1] and A[P], A[P + 1], …, A[N − 1].
The difference between the two parts is the value of: |(A[0] + A[1] + … + A[P − 1]) − (A[P] + A[P + 1] + … + A[N − 1])|
In other words, it is the absolute difference between the sum of the first part and the sum of the second part.
For example, consider array A such that:
A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3We can split this tape in four places:
- P = 1, difference = |3 − 10| = 7
- P = 2, difference = |4 − 9| = 5
- P = 3, difference = |6 − 7| = 1
- P = 4, difference = |10 − 3| = 7
Write a function:
def solution(A)that, given a non-empty array A of N integers, returns the minimal difference that can be achieved.
For example, given:
A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3the function should return 1, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [2..100,000];
- each element of array A is an integer within the range [−1,000..1,000].
Español
Se proporciona una matriz A no vacía que consta de N números enteros. La matriz A representa números en una cinta.
Cualquier entero P, tal que 0 <P <N, divide esta cinta en dos partes no vacías: A [0], A [1], …, A [P — 1] y A [P], A [ P + 1], …, A [N — 1].
La diferencia entre las dos partes es el valor de: | (A [0] + A [1] + … + A [P — 1]) — (A [P] + A [P + 1] + .. . + A [N — 1]) |
En otras palabras, es la diferencia absoluta entre la suma de la primera parte y la suma de la segunda parte.
Por ejemplo, considere la matriz A tal que:
A [0] = 3 A [1] = 1 A [2] = 2 A [3] = 4 A [4] = 3Podemos dividir esta cinta en cuatro lugares:
- P = 1, diferencia = | 3–10 | = 7
- P = 2, diferencia = | 4–9 | = 5
- P = 3, diferencia = | 6–7 | = 1
- P = 4, diferencia = | 10–3 | = 7
Escribe una función:
def solución (A)que, dada una matriz A no vacía de N enteros, devuelve la diferencia mínima que se puede lograr.
Por ejemplo, dado:
A [0] = 3 A [1] = 1 A [2] = 2 A [3] = 4 A [4] = 3la función debe devolver 1, como se explicó anteriormente.
Escriba un algoritmo eficiente para las siguientes suposiciones:
- N es un número entero dentro del rango [ 2 .. 100.000 ];
- cada elemento de la matriz A es un número entero dentro del rango [ -1,000 .. 1,000 ].
Entendiendo el problema
Al igual que los primeros problemas de Codility, este no representa mayor dificultad para desarrollar su funcionalidad, sin embargo, las condiciones para que su rendimiento sea optimo son el real problema a resolver.
El problema busca hallar la diferencia mínima de las dos sublistas creadas de la lista dada, iterando cada uno, siendo así, mientras la una se incrementa según la cantidad de la lista en el iterador, la otra decrementa.
El ejemplo:
A [0] = 3 A [1] = 1 A [2] = 2 A [3] = 4 A [4] = 3
P = 1, diferencia = | 3–(1+2+4+3) | = 7
P = 2, diferencia = | (3+1)–(2+4+3) | = 5
P = 3, diferencia = | (3+1+2)–(4+3) | = 1
P = 4, diferencia = | (3+1+2+4)–(3)| = 7
La diferencia mínima es 1Entendiendo la Solución
Las soluciones mas artesanales son siempre las que primero aparecen para resolver este problema, sin embargo son las mas ineficientes en rendimiento. Por tal, se opta por analizar a alto nivel para luego proceder a codificarlo. La primera suma debe ser el primer valor de la lista, mientras la segunda suma sera la suma de la sublista desde el segundo valor hasta el último. La diferencia de estas sumas sera el valor referencia inicial para comparar con las siguientes diferencias y obtener así los valores mínimos.
Así, empieza el iterador desde el indice 2 (1 dependiendo el lenguaje de programación por el concepto de valor inicial 0 de una lista). Este iterador moverá cada valor dependiendo el indice pivote, así estos movimientos serán de la primera sumatoria a la segunda sumatoria. Con estas nuevas sumatorias, se calcula la diferencia de estos y se compara con la distancia referencial. Si esta diferencia es menor, se actualizara este valor, así hasta recorrer toda la lista. Esta solución permite englobar casi todo el calculo en un solo bucle for y sin listas auxiliares.
Código de Solución — Python
El código fuente de este problema y otros mas (HackerRank, Codility):
