P1. Quicksort no tiene la misma complejidad en el caso promedio. Para los
    que no lo recordaban o no fueron a clase, el peor caso es cuando el
    pivote es el minimo o el maximo, obteniendo:

       Q(n) = O(n) + Q(n-1)   => Q(n) = O(n^2)

    Si los elementos estan uniformementes distribuidos, la particion
    es mucho mejor. En el mejor caso tenemos:

       Q(n) = O(n) + 2 Q(n/2)  => Q(n) = O(n log n)

    que es la complejidad promedio también.

    El tamaño del problema N es el tamaño de la matriz A que es n^2.
    Luego n = sqrt(N).  (0.6 puntos)

	En el programa tenemos que en el peor caso la comparación siempre
    es verdadera:

         T(n) = n*( 1 + Q(n)) = O(n^3) = O(N^(3/2))    (0.7 puntos)

    En el caso promedio la mitad de las veces es verdadera:

         T(n) = n*( 1 + Q(n)/2) = O(n^2 log n) = O(N log N)   (0.7 puntos)

P2. Como no sabemos el numero de listas ni de votantes tenemos que usar una
    estructura de datos dinámica de buen rendimiento para ir contando. 

   Solución simple: Usar un árbol de búsqueda binaria balanceado para ir
   insertando los votos y contando las listas, actualizando n, el número de
   votos. Al final, recorremos el árbol para ver si existen listas (a lo más 2)
   que tienen más de n/3 votos. Si no las hay, reportamos 0 listas.

   Insertar n elementos comenzando en un árbol vacío toma  en el peor caso
   O(n log n) (cuando todas las listas son distintas). El recorrido final
   es O(n), asi que la complejidad es O(n log n).  (1 punto)

   Este algoritmo tal como está no es en línea pues en ningún momento
   sabemos cuales son las listas que tienen más de 1/3 del total parcial
   de los votos. Si mantenemos los dos valores máximos y los comparamos
   con el n/3 parcial queda en línea. Si supieramos el número de listas
   (solución off-line), podríamos calcular con un arreglo el número de
   votos por lista y luego obtener los dos más grandes y verificar si son
   mayores a n/3. Esta solución es O(n). Por lo tanto, la competitividad
   de esta solución simple es O(log n).  (0.5 puntos)

   Solución eficiente: la idea es ir eliminando candidatos a ser las dos 
   listas más votadas. Para esto podemos usar la siguiente observación:
   si tenemos tres votos distintos, podemos eliminarlos y las listas sobre
   n/3 siguen siendo sobre n/3 en el conjunto restante (si es que existen).
   Luego tendremos dos candidatos a ser las listas más votadas, C1 y C2,
   las cuales han aparecido M1 y M2 veces. Al final, debemos verificar que
   realmente C1 y/o C2 tienen mas de 1/3 de los votos. Para esto iremos 
   almacenando los votos en una lista enlazada simple. El algoritmo es:

       - C1 y C2 son las dos primeras preferencias que aparecen, y tendremos
         un valor para M1>=1 y M2=1, agregando esos votos a la lista
         enlazada L. 
       - n = M1+M2;

       - While( voto != 0 ) {
            Agregar( L, voto);  n++;
            if( M1 > 0 && voto == C1 ) M1++;   // el voto está repetido
            else if( M2 > 0 && voto == C2) M2++;
            else if( M2 == 0 ) { // no tenemos candidato 2
                C2 = voto;
                M2 = 1;
            }
            else if( M1 == 0 ) { // no tenemos candidato 1
                C1 = voto;
                M1 = 1;
            }     
            else {   // tenemos dos candidatos y voto no es igual a ellos
                     // eliminamos tres elementos
                M1--; M2--;
            }

        - Contar en la lista enlazada cuantos votos tienen C1 y C2,
          retornando los que tienen más de n/3;

Este algoritmo es lineal en el While y en el conteo final, es decir
T(n)=O(n). (1.5 puntos).

Este algoritmo no es en línea por el chequeo final y dada la propiedad que
usamos no se puede hacer fuera de línea (porque al eliminar elementos
perdemos información). Así que no podemos calcular la competitividad.
(0.5 puntos).

P3. Este problema se puede resolver analizando todos los casos
posibles (vía exploración exhaustiva o recursividad), pero el 
resultado es de complejidad exponencial lo que no es eficiente
(0.5 puntos en este caso).

Notar que si todos los anchos fueran iguales, la solución óptima sería
ordenar todos los libros, encontrar el número máximo de repisas k que
podemos colocar y luego dividir los libros ya en orden en conjuntos de
tamaño n/k. Encontrar k no es trivial, pero a lo más k puede ser H y
podemos hacer búsqueda binaria en k. A esto le podemos agregar el cálculo
del ancho (Soluciones simples pero correctas valdrán hasta 1 punto).

Como los anchos son distintos y queremos minimizar el ancho, si el
libro más alto de una repisa es L, sabemos que los libros en ella
son todos más pequeños y que el resto de los libros tendrá que
caber en un mueble de altura H-L. Luego si fijamos el orden de los
libros por altura podemos elegir el k óptimo tal que ponemos los
n-k libros más grandes en la primera repisa y luego resolvemos
un subproblema de tamaño n-k en un mueble de altura H-hn. Es decir,
escogemos

      C(n,H) = min k ( max(C(n-k,H-hn), sum( ai, i=n-k+1..n ))

Las condiciones de borde son C(0,i) = 0, C(i>1,j<=0)=INFINITO (no caben).
 
Usando programación dinámica usamos una matriz de tamaño n*H y
calculamos C(i,j) para todo i y j hasta llegar a n y H. En cada
paso necesitamos calcular una suma de a lo más O(n) elementos
que podemos también ir calculando con programación dinámica en
un arreglo de modo que cueste O(1) y calcular el mínimo de a lo 
más n elementos. Luego el algoritmo toma tiempo O(H n^2).

Aunque hay ejemplos donde está solución no es óptima (lo es si
los anchos son iguales y en ese caso el segundo término de
C(n,H) es k), se aceptará una solución de este tipo como válida. (2 puntos)