Nota: El análisis se irá desarrollando en el transcurso de la semana.
Básicamente se trabajó en : Codeforces Round #119 (Div. 1 & 2). y a la competencia pueden ingresar a traves de este link
Análisis:
P1. Permutations:
Dada una permutación de los enteros entre 1 y n se permite una operación: quitar el ultimo numero de la lista e insertarlo en cualquier parte de la lista, la pregunta es el numero mínimo de operaciones necesarias para convertir la permutación dada en otra permutación objetivo.
Supongamos que existe un numero en la posición i de la permutación dada y otro numero en la posición j. Si i < j en la permutación dada y i > j en la permutación objetivo, entonces j debe ser removido para poder llegar a la permutación objetivo, porque no hay otra forma de ponerlo antes que i sino sacarlo del final de la lista.
Ahora, supongamos que en vez de volver a meter los números a la permutación cada vez que los sacamos del final, los «guardamos» en alguna parte antes de decidir en donde meterlos. Cuando en la lista no quede ningún par i y j de la forma indicada arriba, entonces simplemente los podríamos sacar de donde los teniamos guardados y ponerlos en el orden correcto de la permutación objetivo.
Finalmente, observen que después de sacar todos los números hasta que no quede ningún par i, j de la forma indicada arriba, todos los otros numeros los debimos haber puesto antes de ese ultimo numero sacado de la lista, y por lo tanto pudimos haber seleccionado el lugar ideal para ponerlos, de tal forma que es como si hubiéramos podido guardarlos y ponerlos al final en el lugar perfecto.
En cuanto a la correctitud: dado que la ultima operación fue sacar un numero que debía ser sacado, el numero de operaciones es el menor numero de operaciones posibles, pues todos los numeros despues de el debian ser sacados para sacarlo.
Para implementarlo se necesita un mapa o una estructura similar que nos permita identificar en tiempo logaritmico o menos cual es el primer numero que esta en «desorden» (en relación a la permutación objetivo) que sera el numero con el menor j de la forma dada, donde i es algun numero anterior a el (porque al estar en desorden debe haber un numero i que en efecto este antes que el en la permutación dada y depues de el en la permutación objetivo).
P6. Cut Ribbon:
El problema consiste en que una persona desea cortar una cinta de longitud n, en varias partes de longitudes a,b,c. Además se desea obtener la mayor cantidad de partes posibles. Es decir, se busca maximizar:
x+y+z
donde se tienen 2 restricciones:
- ax + by + cz = n
- x,y,z >= 0
Con este planteamiento podemos ver que debido a la talla del problema podemos suponer todos los «x» y «y» posibles, además podemos calcular fácilmente el coeficiente c. Para todas las combinaciones posibles, escogemos la que maximice x+y+z.
P7. Counting Rhombi:
Tenemos 2 enteros «w» y «h«. La tarea es contar el número de rombos que cumplen con las siguientes propiedades:
- Sus vértices tienen que estar en coordenadas enteras.
- Todos los vértices del rombo deben estar, dentro, o en el borde del rectángulo denotado por w,h. Es decir cuatro puntos con coordenadas (0, 0), (w, 0), (w, h), (0, h).
- Un rombo debe tener todos sus lados iguales.
Inicialmente debemos fijarnos en las tallas, tanto w como h son máximo 4000. Con lo cual podremos garantizar que podríamos recorrer todos los puntos enteros para los cuales 0 ≤ xi ≤ w y 0 ≤ yi ≤ h.
Luego debemos hacer otra apreciación relevante, para dibujar un rombo válido, sólo podremos representar este mediante un rectángulo de tamaño wi , hi, donde tanto wi, hi deben ser números pares.
Con esto en mente, podemos proceder a suponer todos los wi y hi posibles, y para cada uno de ellos, vamos a contar cuántos rectángulos de wi* hi podemos dibujar dentro de w,h. Hay que tener en cuenta que todos los posibles subrectángulos se pueden sobrelapar.
En los siguientes links se encontrarán las implementaciones a las soluciones de los problemas.
P7. Counting Rhombi
solucion por Beto Martinez en C