Codeforces 289B

http://codeforces.com/problemset/problem/289/B

En problemas como estos, generalmente la primera parte de la solución es encontrar el caso donde no se puede resolver. Dado que solo podemos sumar o restar d a los elementos de la matriz, si encontramos al menos 2 elementos cuya diferencia no sea múltiplo de d, es imposible igualar esos elementos.

En el caso donde existe la solución  podemos transformar un poco el problema, y convertir la matriz en un arreglo común  ordenado ascendentemente. Luego de esto, la solución optima seria restar d a los números mayores y sumar d a los menores hasta llegar a un punto común donde todos los elementos sean iguales. Cual es este punto común? El elemento que esta en el centro del arreglo.

Esta es la mejor solución ya que si escogemos un valor mayor que el valor central, los elementos menores van a necesitar mayor cantidad de operaciones para igualar, y si escogemos un valor menor que el central, se necesitan mas operaciones para igualar los elementos mayores.

Despues de encontrar cual es el elemento central, la solución es la suma de |aic| / d para cada elemento ai en el arreglo.

Mi solucion en Codeforces http://codeforces.com/contest/289/submission/3463481

Anuncios

Comentar

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s