Codeforces 311A The Closest Pair

http://codeforces.com/problemset/problem/311/A

Este es un problema interesante, porque nos pide analizar un problema ya resuelto, al contrario de resolverlo.

Haciendo un análisis del tiempo del algoritmo que presentan en el texto del problema, se puede encontrar que el for exterior se ejecuta n veces, y el interior se ejecuta (n − i) veces, si logramos que nunca ocurra el break que hay dentro.

Partiendo de esto podemos calcular que tot se incrementa cada vez que ocurre un ciclo, lo que es igual a formula

Asi podemos concluir que si tot ≤ k, no existe solución posible.

De lo contrario hay que encontrar un conjunto de puntos que impidan que ocurra el break. Para esto tenemos que hacer que la sentencia d ≤ p[j].x - p[i].x sea siempre falsa. En el caso evidente, podemos seleccionar todos los puntos con la misma coordenada x, y se cumple la condición ya que d tiene que ser mayor que cero porque todos los puntos son diferentes.

Con este análisis, el código se resume a comprobar si n(n-1) > k, y mostrar n diferentes puntos con la misma x coordenada.

Mi código en Codeforces http://codeforces.com/contest/311/submission/3788135

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