Codeforces Round #450 (Div 2, mañana lunes 11/12 13.05 hs)

Jueces Online Codeforces
#1

Hola!

Vengo a comentar que mañana a las 13.05 va a haber una competencia en la página http://codeforces.com . Dura dos horas.

Este post va medio seguido a otro reciente sobre competencias y páginas online: Otras competencias de programación

Para los que no conoces codeforces, este tipo de competencias en general tiene 5 problemas, ordenados en orden de dificultad. Puede ir a http://codeforces.com/contests y ver competencias anteriores.

Yo (que de paso me presento, soy Sebastián Cherny y participé de OIA hasta egresar en el año 2013), probablemente participe mañana de la competencia, aunque el horario no me queda del todo conveniente.

De todas formas, quería intentar ver si lxs oiaforistas se copaban con hacer esto de un post por competencia online interesante, en la que participemos varios de acá y después discutamos los problemas que no salieron, contemos soluciones, o ideas de problemas que estuvieron cerca, o lo que sea.

Entonces, veamos cómo resulta.

Algo que también podemos hacer es dejar los usernames (de esta página y de otras en las que participen), y avisar si piensan participar o algo así. En codeforces por ejemplo se pueden agregar usuarios de amigos para ver cómo les está yendo durante una competencia. Mi usuario es sebach, acá, en codeforces y creo que todas las páginas.

Adiós!

4 Me gusta
Csacademy Contest #61 (miercoles 13/12, 12hs)
#2

Algo para comentar sobre codeforces, que pongo acá para no hacer muy extenso el post inicial, es que se puede por ejemplo simular una competencia anterior.
Entonces por ejemplo, si alguien no puede estar a las 13.05 para hacer la competencia, puede participar como “virtual participation”, que obviamente no afectará el rating, pero si no vieron los problemas antes es como hacerlo en el momento.

También en codeforces se pueden armar competencias mezclando problemas de distintas competencias. Si les interesa puede comentar acá que les interesa, y si llegan a ser muchos podemos hacer una encuesta de qué temas más les gustaría practicar, o directamente armar una pruebita para simular en un horario en que puedan todos, así sirve para practicar y para charlar entre nosotros problemas que no salieron.

3 Me gusta
#3

Ya que nadie publicó soluciones, acá publico las mías:

Si alguno tiene alguna pregunta / quiere que le explique lo que hice que, me dicen.

6 Me gusta
#4

Muy buenos los códigos, buenísimo que los posteaste!
El E me gustó más que el D, como que el D creo que era más saber la formulita. O sea, una vez que veías que había que buscar

idea

sumar y/x con números de gcd 1

era saber la fórmula. Aunque para mí está buena también la idea de

otra idea

buscar la cantidad de formas de sumar con gcd = 1, es el total de la cantidad de formas de sumarlo menos la cantidad de formas de sumar el número con gcd = 2, 3, … . Y entonces medio que podés pensar eso como una recursión, aunque calcular la complejidad de eso no es tan fácil de calcular.

El B y el C estaban lindos también, el B creo que era más difícil de lo que suelen ser los B’s.

#5

No, no es que no sabía la formulita. La derivé teniendo en cuenta esto:


Tenés que g * 1 = (n -> 2 ^ (n - 1)), entonces “multiplicas” por el unverso de 1, que es la funcion de mobius, y te da la formultita.
Aunque también podés hacer la recursión (todas las formas de hacer, menos las formas con gcd 2, menos las con gcd 3, …) y ver que se te cancelan algunos términos, y te termina quedando lo mismo

1 me gusta
#6

Ah mirá no lo escribí, qué copado que termine quedando lo mismo. Está muy bueno que lo hayas hecho en el momento, yo personalmente no sabía lo de la Convolución de Dirichlet y tampoco lo de la función de mobius.

#7

Me encantó. :heart_eyes:

Quizá ayude a alguien que está leyendo esto junto con el artículo de wikipedia notar que ese 1, es la función constante 1 (o sea, una función que para todo número da 1).

Por si a alguien le interesa, escribo en detalle lo que planteás. Haciendo cuentas y pensando el problema, uno llega a g(n) = 2^{n-1} = \sum_{d | n} f(d) , pero lo que planteás es que se puede pensar como…

g(n) = \sum_{d | n} f(d) = \sum_{d | n} f(d){\bf 1}(\frac{n}{d})

Escrito como convolución de Dirichlet queda

g = f * 1 \Longrightarrow f = g * {\bf 1}^{-1} = g * \mu \Longrightarrow f(n) = \sum_{d|n} g(d) \mu(\frac{n}{d}) = \sum_{d|n} 2^{d-1} \mu(\frac{n}{d})

Yo lo hice de la otra forma y me quedó cuadrático en la cantidad de divisores (con un log además porque uso map). Ya que estoy, cuento un poco la idea para que el post no quede tan matematicoso.

Lo que hice fue despejar el término de f(n), y queda:

f(n) = 2^{n-1} - \sum_{\substack{d|n \\ d \neq n}} f(d)

Con esa relación uno puede calcular los f(d) en orden creciente hasta llegar a f(n) (con programación dinámica para no recalcular dos veces el mismo valor).

2 Me gusta