Entrenamiento IV – 1 abril.

Se trabajaron las siguientes maratones.

  • Codeforces Beta Round #44 (Div. 2)
  • Codeforces Beta Round #2

Los standings de la maratón se pueden encontrar acá.

 

Análisis.

P1. Triangular numbers.

Es un problema sencillo, se trata de verificar si un número es «triangular» o no. (http://en.wikipedia.org/wiki/Triangular_number).

Como la talla es pequeña se pueden generar todos los números triangulares y verificar si es uno de ellos, también se puede despejar de la fórmula.

Solución C++ Manuel Pineda.

Solución Java Santiago Gutierrez.

Solución C++ Beto Martinez.

 

P3. Coins.

Para este problema, se puede contar cuántas veces aparece una letra al lado izquierdo (menor que la otra variable), con esto tenemos que  el más pequeño de todos debe aparecer 2 veces como menor, el intermedio 1 vez como menor, y el más grande 0 veces como menor.

También, teniendo en cuenta que la entrada es pequeña, podemos generar las posibles combinaciones de las letras, y comprobar si alguna de estas es válida para según la entrada.

Solución Java Diego Agudelo.

Solución C++ Manuel Pineda.

Solución C++ Beto Martinez.

3 Comments

Entrenamiento 29 marzo

Hoy se trabajó ésta maratón: http://ahmed-aly.com/Contest.jsp?ID=4268

Nota: En esta maratón todo se lee desde archivo

 

P1 – Boys and Girls

El problema consiste en que hay n chicos y m chicas. Se debe suponer que ambos (chicos y chicas) se encuentran a lo largo de una línea, y la idea es colocarlos lo más alternados posible.

Ejemplo:

Si n = 3 y m = 3 se deben organizar así:

GBGBGB

( ‘G‘: Girls y ‘B‘: Boys ) La salida va a ser de tamaño n+m

Cuando m = n habrá la misma cantidad de ‘G‘s  y  ‘B‘s y quedan perfectamente alternados, pero cuando m != n no es posible que todos queden alternados, lo que se hace en este caso es colocar alternadamente la mayor cantidad posible de parejas, es decir, si n > m se colocan m veces ‘BG‘ y luego n-m veces ‘B‘, por otro lado si m > n entonces se colocan n veces ‘GB‘ y luego m-n veces ‘G‘.

Solución (C++): Por Diego Martinez

Solución (Java): Por Diego Agudelo

Solución (C): Por Beto Martinez

 

P2 – Cards with Numbers

Se tienen  2n cartas, las cartas están indexadas de 1  a  2n cada carta  a i  se representa con un entero positivo (1  ≤  a i  ≤  5000 ), el objetivo de este problema es hacer un split de pares que tengan el mismo número. En la salida se imprime el indice de las parejas.

Ejemplo:

(Entrada)

3

20  30  10  30  20  10

(Salida)

1  5

2  4

3  6

El orden no importa. y pueden existir muchas soluciones válidas. Por ejemplo: es correcto  ( 1 , 5 )  ó  ( 5 , 1 ). Si no es posible hacer el split, se implime  ‘-1‘.

Una solución a este problema consiste en ordenar todas las cartas, pero se debe conservar el posición inicial de cada carta (En C++ se puede hacer con un arreglo de  pair<int,int> donde el primer elemento represente el valor de la carta y el segundo la posición inicial). Luego se verifica si es posible o no realizar el split; una forma de  darse cuenta es mirar si existe una cantidad impar de elementos repetidos, si es así entonces no se pude hacer el split, de lo contrario si es posible.

Para imprimir la respuesta se recorre el arreglo ordenado, de izquierda a derecha y se imprime:

array[ i ].second  array[ i+1 ].second

(Second: representa la posición inicial de la carta).

Nota: La entrada para este problema puede ser muy grande, es recomendable usar un método rápido de Entrada/Salida. En C++ usar printf y scanf en lugar de cin y cout, para evitar un Time Limit.

Solución (C++): Por Jhon Jimenez

Solución (C++): Por Beto Martinez

 

P3 – Physics Practical

Se tienen n enteros ( 2  ≤  n  ≤  10 5 ), cada entero c1, c2, …, cn ( 1  ≤  ci  ≤  5000 ), en el problema se pide «eliminar» la menor cantidad posible de números tal que,  X (El ci más pequeño) y el Y (El ci más grande) cumplan la siguiente desigualdad  y  ≤  2 · x . Es decir, dados los n números, lo que se debe hacer es hacer que se cumpla la desigualdad de arriba, y eliminando la menor cantidad posible de elementos.

Ejemplo:

(Entrada)
6
4 5 3 8 3 7

(Salida)

2

Para que se cumpla la desigualdad, podría eliminar el cuarto y el sexto elemento que corresponden al 7 y al 8, de esa forma dentría x = 3; y = 5. Por lo tanto se cumple 5 ≤ 2·3 . Se llega a la solución «eliminando» 2 elementos.

Pero también podría eliminar el tercer y quinto elemento 3 y 3 respectivamente; también sería una solución válida x = 4; y = 8 y se cumple 8 ≤ 2·4 eliminando 2 elementos.

Una estrategía de solución consiste en ordenar los elementos de menor a mayor. Luego para cada Ci comenzando desde la izquierda, se va a suponer ese Ci como un posible X y desde Ci+1 hasta Cn se va a buscar un Y el cual es el primer elemento (De derecha a izquierda) que cumpla la desigualdad y  ≤  2 · x . Los indices del X y Y me van a decir la cantidad de elementos «eliminados».

Ejemplo:
3  3  4  5  7  8 (arreglo v elementos ordenados)
0  1  2  3  4  5  (posiciones)

Iteración 1:
x1 = v[0] => x1 = 3
y1 = v[3] => y1 = 5

Para determinar cuántos elementos debimos eliminar para x1 me moví de izquierda a derecha 0 posiciones y
para y1 me moví de derecha a izquierda 2 posiciones,entonces Eliminados = 0 + 2.

Eliminados1 = 0 + 2 = 2

Iteración 2:
x2 = v[1] => x2 = 3
y2 = v[3] => y2 = 5

Eliminados2 = 1 + 2 = 3
Iteración 3:
x3 = v[2] => x3 = 4
y3 = v[5] => y3 = 8

Eliminados3 = 2 + 0 = 2
Iteración 4:
x4 = v[3] => x4 = 5
y4 = v[5] => y4 = 8

Eliminados4 = 3 + 0 = 3

Iteración 5:
x5 = v[4] => x5 = 7
y5 = v[5] => y5 = 8

Eliminados5 = 4 + 0 = 4

Iteración 6:
x6 = v[5] => x6 = 8
y6 = v[5] => y6 = 8

Eliminados6 = 5 + 0 = 5
Para la respuesta del problema se debe escoger el «Eliminados» de menor cantidad, el cual es igual a 2.

Solución (C++  ): Por Jhon Jimenez

Solución (C++): Por Diego Martinez

 

Análisis: Jhon Jimenez

Add a comment

Entrenamiento 28 marzo.

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

Add a comment

Regionals 2010 :: North America – Greater NY

Hoy sólo trabajamos algunos problemas, debido a que fue un entrenamiento individual y sólo duró 3 horas.

Pueden encontrar la competencia acá: http://ahmed-aly.com/Standings.jsp?ID=4230

Análisis.

P1. Penney Game

Es el problema más fácil de la maratón, consiste en contar cuantas veces aparece una de las siguientes sub cadenas «TTT, TTH, THT, THH, HTT, HTH, HHT and HHH», se puede resolver con una complejidad lineal recorriendo toda la cadena, y mirando grupos de 3 caracteres, para saber a qué conjunto sumarle.

P2. Nim-B Sum

Aunque el enunciado del problema es un poco confuso, la frase  » Write a program to compute NimSum(B, X, Y)». Nos da paso para hacer una rutina que resuelva dicho problema, ya que se dice que las reglas para calcular la «NimSum» son:

  1. Write each of X and Y in base B.
  2. Each digit in base B of the Nim-B sum is the sum modulo B of the corresponding digits in the base B representation of X and Y.

Luego de tener los numeros X y Y en la base B, podemos pasar a hacer lo que nos dice la segunda regla para calcular «NimSum». Para lo cual, sumamos cada digito de A Y B que esten el el mismo indice, y luego sacamos el modulo en base B a dicha suma, es decir:

(A[i] + B[i])%base
Lo que se hace es usar el algoritmo para pasar de cualquier base a decimal cada componente.

P5.  Non-Decreasing Digits

El problema se puede resolver por conteo, o por programación dinámica.
Podemos definir una funcion cuyo objetivo es contar cuantos numeros existen de longitud «a»  con numeros crecientes, mayores o iguales a b.
Para esto podemos hacer una funcion que intente «poner»  todos los números (denotados como i) mayores o iguales a b.
Con esta idea, vemos que ahora tenemos que solucionar un subproblema, llamar a la funcion para una longitud «a – 1» y todos los números mayores o iguales a i.
El caso base es cuando la longitud es 1 en cuyo caso la solución es 1.

En los siguientes links podrán encontrar algunas implementaciones de las soluciones.

P1:

solución por carlos Arias en C++

solución por Andres Mosquera en java.

solución por Beto Martinez en C

P1 , P2 , P3:

soluciones en C++ por Manuel Pineda.

Análisis y códigos: Manuel Pineda, Carlos Arias, Andrés Mosquera, Beto Martinez

Add a comment

Entrenamientos virtuales UTP.

La idea es realizar entrenamientos virtuales en la página http://ahmed-aly.com/,  allí se pueden crear contest con problemas de muchos sitios como UVa, livearchive, codeforces, topcoder,…

Por cada uno de los entrenamientos socializaremos las soluciones de todos los participantes y trataremos de realizar un análisis basado en nuestras experiencias.

Cualquier persona que esté interesada puede participar, sólo debe tener cuenta los sitios mencionados. Todos nosotros estamos dispuestos a ayudar a las personas que deseen empezar con las maratones de programación.

Add a comment