Concurso Nacional de Computación 2019 Día-2


Problems

Problem Points AC Rate Users Editorials
Wather 100p 12.0% 46 Editorial
Sherlock and Watson 100p 9.9% 36
Parovi 100p 7.2% 14 Editorial

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.


  • 18
    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