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


Problems

Problem Points AC Rate Users
Wather 100p 1.7% 29 Editorial
Sherlock and Watson 100p 3.1% 23
Parovi 100p 0.8% 9 Editorial

Comments


  • -5
    Uzumaki_Jonathan  commented on Feb. 13, 2019, 10:07 p.m.

    yo pienso que esto fue una mala actitud por parte del jurado del concurso, deberian haber arreglado y revisado los casos de prueba antes del concurso, no durante ni despues.


  • 0
    aniervs  commented on Feb. 13, 2019, 6: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. 13, 2019, 7:06 p.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. 13, 2019, 7:51 p.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, 12: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, 1:43 p.m.

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


  • 1
    aniervs  commented on Feb. 13, 2019, 5: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, 9:02 a.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