Concurso: Preselectivo para la IOI 2015, Etapa 1, Problemset 1
Autor: Freddy Román Cepeda
Fuente: Freddy Román Cepeda
Este problema requería manipular con cuidado la expresión que había que computar.
Recordemos que nos piden computar

Para resolver la primer subtarea bastaba con iterar sobre todas las parejas de puntos y calcular su distancia. Esto corre en tiempo cuadrático y no es suficiente para obtener todos los puntos.
La siguiente subtarea era una pista: se puede computar la distancia Manhattan de dos puntos considerando por separado sus coordenadas en y
. Ahora nos preocuparemos por calcular la siguiente expresión:

Donde son las coordenadas en
o
. El problema está en el valor absoluto. La manera más sencilla de deshacernos de él es ordenar la secuencia
, de tal manera que
. Entonces tenemos:

La primer igualdad es verdadera porque para cualquier
. La segunda es porque como ahora
está ordenado, como
, el valor absoluto no hace nada.
Podemos entonces separar la suma en dos términos:

Analicemos el primer término. Estamos sumando sobre todas las tantas veces haya una
menor que ella. Eso quiere decir que cada
la vamos a sumar
veces (nota que
la sumamos
veces).
El segundo término nos dice que sumaremos todas las tantas veces haya una
mayor a ella. Eso quiere decir que cada
la vamos a sumar
veces (nota que
la sumamos
veces).
Juntando esas ideas, entonces tenemos:




Y con eso terminamos: ahora tenemos una expresión que podemos computar fácilmente en tiempo lineal. Hay que tener cuidado al computar esto: La primera observación es que hay que estar tomando módulo después de cada operación porque en cualquier momento puede haber un overflow. Algunos competidores obtuvieron 60 puntos en este problema por no tomar esto en cuenta. La segunda observación es que el término no necesariamente cabe en un entero signado de 32 bits — hacía falta utilizar enteros de 64 bits para realizar este cálculo.
Aquí está mi código que implementa la solución anterior.