MickyOr

Algunas soluciones - IEEEXtreme Bolivia

Oct 6th, 2018
255
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ===== Teams =====
  2. Facil
  3.  
  4. ===== Strings with Same Letters =====
  5. Facil
  6.  
  7. ===== Mohammed Refaat (Grafos) =====
  8. Nos dan un grafo con pesos en las aristas y nos piden el camino mas corto entre dos nodos. Para esto usamos el algoritmo de Dijkstra.
  9.  
  10. ===== Chess Knights (Grafos) =====
  11. Vemos cada casilla como un nodo, un nodo esta conectado a otro si se puede llegar a el con un movimiento del caballo. Con esto en mente, el problema se convierte a encontrar el tamaño del componente en el que se encuentra la casilla inicial; este problema se resuelve con DFS, BFS o Union Find.
  12.  
  13. ===== Triangles Area =====
  14. No resuelto :(
  15.  
  16. ===== Difficult Routes =====
  17. No resuelto, ni lo entendimos :(
  18.  
  19. ===== Make Psycho (DP) =====
  20. El problema mas frustrante que resolvimos durante el contest.
  21. Podemos dividir el problema en dos partes:
  22. 1) Eliminar todos los numeros ordinarios (no Psycho) de la lista que nos dan en la entrada
  23. 2) Con la nueva lista, decir si podemos formar un subconjunto tal que la suma de sus elementos sea igual a K
  24.  
  25. La primera parte es bastante sencilla, hacemos la verificacion de si un numero es Psycho usando una criba de Eratostenes o con fuerza bruta (el tamaño de entrada y los numeros son pequeños).
  26.  
  27. La segunda parte se puede resolver con programacion dinamica viendo las posibilidades de tomar o no tomar un elemento para el subconjunto resultado, la funcion top-down es la siguiente:
  28. bool f(int posicionEnLista, int suma)
  29. {
  30. // casos base
  31. si suma = 0, return verdadero
  32. si posicionEnLista == finalLista, return falso
  33. si suma < 0, return falso
  34. // memoizacion
  35. si ya visitamos este estado, devolver respuesta
  36. // resolver problemas mas pequeños recursivamente
  37. resultado = f(posicionEnLista+1, suma + lista[posicionEnLista]) | f(posicionEnLista+1, suma)
  38. return resultado
  39. }
  40.  
  41. Esto nos da una complejidad de O(n*k), con n = 100, k = 10^5 y 2000 casos, la solucion da TLE :(
  42. Al no tener idea de como resolver los problemas que faltaba ni de otra posible solucion para este problema, decidimos seguir intentando. Y despues de 9 intentos, logramos obtener el AC! Luego de intentar todo fueron dos optimizaciones las que hicieron el truco:
  43.  
  44. La primera fue generar todos los numeros psycho hasta 1100 (limite superior del problema) y declarar un arreglo con estos valores de forma explicita ya que solo hay 49
  45. ej: int psychoNumbers[49] = {4, 9, 16, 25, ...};
  46.  
  47. La segunda y mas importante es volver el DP a su forma bottom-up iterativa.
  48.  
  49. Aunque la complejidad sigue siendo O(n*k), el tiempo de ejecucion baja mucho..... ¯\_(ツ)_/¯
  50.  
  51. ===== Train Passengers =====
  52. Lees la capacidad y las rutas que hara el tren ahora lees 3 enteros por cada ruta la cantidad que salen, entran y se quedan tienes que verificar que la ruta no sea invalida.Pondremos un totaldepasajeros=0 y le restamos la cantidad de totaldepasajeros si esta es menor a 0 entonces es invalido (1era opcion) totaldepasajeros sumas la cantidad que entran si esta es mayor > la capacidad de entrada entonces es invalido (2da opcion) ahora si la cantidad de personas que entran<la cantidad de personas que se quedan invalido(3ra opcion) y al final verificas que totaldepasajeros=0 si no (el problema te pide que cuando llegue al final no tiene que tener pasajero ) invalido (4ta opcion)
  53.  
  54. ===== Easy One =====
  55. El mas facil
  56.  
  57. ===== Super Ants =====
  58. No resuelto :(
  59.  
  60. ===== Football Hooliganism (Greedy) =====
  61. Primero unimos todas las celdas de ancho 1 verticales poosibles
  62. 01 0A
  63. 01 =======> 0A
  64. 11 marcando celdas de 1's unidas con letras BA
  65. 10 B0
  66. 00 00
  67.  
  68. Llamaremos a cada conjunto de celdas consecutivas "segmento". La figura de arriba tiene 2 segmentos, A y B.
  69. Guardamos cada inicio y final de segmento.
  70. Cada segmento en el que inicio = final, es un confinamiento solitario.
  71. Ahora, para eliminar un confinamiento solitario debemos extender su celda hacia la derecha/izquierda, esto provoca que quitemos una posicion de un segmento (ya que es la que usaremos para eliminar el confinamiento solitario y todas las celdas pertenecen a un segmento).
  72.  
  73. Tenemos 3 posibilidades al eliminar una parte de un segmento:
  74. 1) Eliminamos el inicio o final de un segmento
  75. 2) Eliminamos una parte del medio y dividimos el segmento en dos partes
  76. 3) Si tambien es un confinamiento solitario, eliminamos todo el segmento
  77.  
  78. Por cada confinamiento solitario vemos estas tres posibilidades, si no generan un nuevo confinamiento solitario, alargamos la celda solitaria y eliminamos un (o dos en el tercer caso) confinamiento solitario.
  79.  
  80. La solucion seria: ConfinamientosSolitariosOriginales - ConfinamientosSolitariosArreglados
  81. Complejidad: O(n)
  82.  
  83. ===== deltree =====
  84. No leido
RAW Paste Data