Comments

• 
  

  0

  

  aniervs  commented on Feb. 13, 2019, 11:59 p.m.

  Creo que el tercer problema se puede resolver con el principio de inclusión-exclusión en O(n*2^n).

• 
  

  1

  

  DGC  commented on Feb. 14, 2019, 12:06 a.m.

  Tal vez, pero hay una solución con ~dp~ mucho más sencilla en ~O(c*n)~, donde ~c~ es la cantidad de pares válidos que es mucho menor que ~n^2~.

• 
  

  0

  

  aniervs  commented on Feb. 14, 2019, 12:51 a.m.

  Lo acabo de aceptar con inclusión-exclusión. Me podrías decir de qué va la dp?

• 
  

  2

  

  DGC  commented on Feb. 14, 2019, 5:29 a.m. ← edited →

  Mira cada par de números en el conjunto como un intervalo ~(a_i, b_i]~ tal que ~a_i < b_i~ es decir si esta el ~{2, 5}~ por ejemplo lo ves como un intervalo abierto en ~2~ y cerrado en ~5~ (~(2, 5]~), es fácil demostrar que si solapas todos los intervalos ~(a_i, b_i]~ que están en el conjunto entonces Jorge gana si y solo si todos los números del ~2 \le k \le N~ están cubiertos, por lo que ahora el problema es equivalente a calcular la cantidad de subconjuntos de los pares de números posibles, tal que si trazamos una recta desde ~a_i+1~ hasta ~b_i~ para todo par que pertenece al subconjunto todos los ~2 \le k \le N~ están cubiertos por al menos una recta y esto es fácil calcularlo con ~dp_i=~ la cantidad de subconjuntos que cubren los ~i~ primeros números. Solución

• 
  

  0

  

  aniervs  commented on Feb. 14, 2019, 6:43 p.m.

  OK. Excelente solución. Gracias por la explicación.

• 
  

  1

  

  aniervs  commented on Feb. 13, 2019, 10:23 p.m.

  Los problemas en general estaban más difíciles que los del día 1, la prueba tenía más nivel.

• 
  

  19

  

  leo  commented on Feb. 13, 2019, 2:02 p.m.

  Hola a todos, El problema A que les va a llegar de forma impresa con el nombre GAME no es el cotrrecto, es el WATHER que esta en el sitio, disculpen las molestias. Gracias y Exitos a todos