Sumas Adyacentes « Lobishomen, página personal

Sumas Adyacentes

Publicado por lobishomen en Julio 3, 2008

Este fue un problema que apareció en la OMI 2008 y hubo algunos errores en los casos de prueba, así que muchos se quedaron con la incertidumbre de cómo se resolvía.

Brevemente, el problema hablaba de que dada una secuencia de enteros positivos:

$B=(b_1, b_2, b_3, ..., b_{n-1})$

Había que encontrar una secuencia de enteros

$A=(a_1, a_2, a_3, ..., a_n)$

Bajo las siguientes condiciones:

$b_i=a_{i}+a_{i+1}$
A sea no descendente
$a_1$ sea el máximo valor posible sujeto a las primeras 2 condiciones.
El programa funcione en tiempo lineal

Solución

Para resolver este problema vamos a llamar Z a una secuencia tal que:

$Z=(z_1, z_2, ..., z_n)$
$b_i=z_{i}+z_{i+1}$
$z_1=0$

Es muy fácil encontrar una secuencia Z que cumpla con las características, ya que luego de unas sencillas operaciones algebraicas se puede concluir que $z_i=b_i-z_{i-1}$ para i>0, y eso es suficiente para encontrar Z en tiempo lineal.

Ahora, sea $K=a_1$ , nótese que:

$A=(z_1+K, z_2-K, z_3+K, z_4-K, z_5+K, ... )$

Esto es porque por construcción $z_{i}+z_{i+1}=b_{i}$ entonces $z_{i}+K+z_{i+1}-K=b_{i}$ .

Está claro que si se le asigna a K un valor arbitrario la primera condición siempre se cumple, pero la segunda no siempre.

De una manera mas precisa la condición 2 significa que:

$a_1 \le a_2 \le a_3 \le ... \le a_n$

Podemos modificar la condición por este equivalente

$z_1+K \le z_2-K \le z_3+K \le ...$

Y nuevamente esta condición se puede separar en otras 2 condiciones, por lo cual hay que encontrar el valor máximo para K tal que:

$z_{2i-1}+K \le z_{2i}-K$ para toda i tal que $2i \le n$
$z_{2i}-K \le z_{2i+1}+K$ para toda i tal que $2i+1 \le n$

Despejando la K de las desigualdades anteriores tenemos que:

$K \le \frac{z_{2i}+z_{2i-1}}{2}$ para toda i tal que $2i \le n$
$\frac{z_{2i}+z_{2i+1}}{2} \le K$ para toda i tal que $2i+1 \le n$

El primer despeje indica una cota superior para K y el segundo despeje indica una inferior para K. Podríamos pensar que la cota inferior no es necesaria, pero si lo es, ya que si la conta inferior es mayor a la cota superior es evidente que no hay solución.

Dado que la condición 1 se cumple si y solo si $A=(z_1+K, z_2-K, z_3+K, z_4-K, z_5+K, ... )$ , la condición 2 se cumple si y solo sí K está sujeta a la cota superior e inferior y la condición 3 se cumple si y solo sí se cumplen las dos anterior y K es la parte entera de la cota superior entonces el problema se resuelve encontrando Z(tiempo lineal), luego encontrando las cotas(tiempo lineal) e imprimiendo la solución(tiempo líneal).

Espero que esta descripción de la solución sea suficiente para aclarar las dudas con respecto a este problema.

Esta entrada fue publicada el Julio 3, 2008 a 8:50 pm y está archivada en Olimpiada de Informática. Puedes seguir los comentarios a esta entrada a través de RSS 2.0 feed. Puedes deja un comentario, o trackback desde tu propio sitio.