{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Repaso (Think twice, code once)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Objetivos\n", "\n", "* Analizar los errores del último contest\n", "* Repasar temas vistos anteriormente mediante problemas (principalmente fuerza bruta)\n", "* Coordinar horarios para próximas sesiones" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Problema 1\n", "\n", "Dado un array $a_1, a_2, \\dots a_n$. Encontrar cuantas tuplas $(x, y)$ existen tal que\n", "\n", "$$1 \\leq x < y < n \\land \\displaystyle\\sum_{i = 1}^{x} a_i = \\displaystyle\\sum_{x + 1}^{y} a_i = \\displaystyle\\sum_{y + 1}^{n} a_i$$\n", "\n", "\n", "$$1 \\leq n \\leq 10 ^ 5$$\n", "$$-10 ^ 4 \\leq a_i \\leq 10 ^ 4$$\n", "\n", "**Hint:** Fija el primer elemento de la tupla \n", "**[Link del problema](https://codeforces.com/contest/21/problem/C)** \n", "**[Solución](./examples/p01.cpp)**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Problema 2\n", "\n", "Recibirás dos números $a, b$ seguido que $q$ consultas de la forma $l, r$.\n", "\n", "Para cada consulta imprime el máximo $d \\in [l, r]$ tal que $d$ sea divisor de $a$ y $b$ o $-1$ si tal $d$ no existe.\n", "\n", "$$1 \\leq a, b \\leq 10 ^ 9$$\n", "$$1 \\leq q \\leq 10 ^ 4$$\n", "$$1 \\leq l \\leq r \\leq 10 ^ 9$$\n", "\n", "**Hint:** $\\sigma_0 (n) = O(n ^ {1 / 3})$ (La demostración está en el Apéndice 1)\n", "\n", "**Nota:** $sigma_0 (n)$ es la cantidad de divisores de $n$\n", "\n", "**[Link del problema](https://codeforces.com/contest/75/problem/C)** \n", "**[Solución](./examples/p02.cpp)**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Problema 3\n", "\n", "Tiene `n` cajas con $a_i$ caramelos en la i-esima caja. Debes repartir esos caramelos entre $k$ niños de tal manera que cada niño obtenga la misma cantidad de caramelos y que estos sean de una misma caja. ¿Cuál es la mayor cantidad de caramelos que un niño puede recibir?\n", "\n", "$$1 \\leq n \\leq 5 \\cdot 10 ^ 4$$\n", "$$1 \\leq k \\leq 10 ^ 9$$\n", "$$1 \\leq a_i \\leq 10 ^ 9$$\n", "\n", "**Hint:** Si cada niño puede recibir $x$ caramelos, entonces cada niño también puede recibir $x - 1$ caramelos \n", "**[Link del problema](https://www.spoj.com/problems/MAIN8_C/)** \n", "**[Solución](./examples/p02.cpp)**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Problema 4\n", "\n", "$N_0 = 1$\n", "\n", "$N_i = N_{i - 1} + f(N_{i - 1})$\n", "\n", "donde $f(x) = $ número de divisores de $x$\n", "\n", "Recibirás $T$ consultas de la forma $l, r$ y deberás responder cuantos $i$ existen tal que $l \\leq N_i \\leq r$.\n", "\n", "$$1 \\leq T \\leq 10 ^ 5$$\n", "$$1 \\leq l \\leq r \\leq 10 ^ 6$$\n", "\n", "**Hint1:** La secuencia es creciente \n", "**Hint2:** Podemos generar la cantidad de divisores de $1, 2, \\dots n$ en $O(n log n)$ \n", "**Hint3:** podemos generar la secuencia hasta el máximo elemento que necesitaremos \n", "**[Link del problema](https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2987)** \n", "**[Solución](./examples/p04.cpp)**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Problema 5\n", "\n", "Recibirás una matrix de $n \\times m$ donde cada fila será una permutacion de $1 ... m$.\n", "Tienes permitido escojer (una sola vez) dos columnas (posiblemente las mismas) y cambiar sus elementos y para cada fila tienes permitido escojer (una sola vez) dos posiciones (posiblemente las mismas) y cambiar sus elementos.\n", "Las anteriores operaciones las puedes realizar en cualquier orden.\n", "\n", "Tu tarea consiste en imprimir 'SI' en caso es posible obtener la matriz de $n \\times m$ donde cada fila es la permutación identidad de $m$ elementos $(1, 2, 3, \\dots, m)$ usando las operaciones anteriormente descritas o 'NO' en caso no sea posible.\n", "\n", "$$1 \\leq n, m \\leq 20$$\n", "\n", "**Hint1:** Podemos probar todos los posibles pares de columnas a intercambiar en $O(n ^ 3)$ \n", "**Hint2:** Podemos saber cuantos intercambios son necesarios en una fila en $O(n)$ \n", "**[Link del problema](https://codeforces.com/contest/724/problem/B)** \n", "**[Solución](./examples/p05.cpp)**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Problema 6\n", "\n", "Un número de la suerte es un número donde sus dígitos son $4$ o $7$. Por ejemplo, $4, 7, 44, 47, 77$ son números de la suerte.\n", "\n", "Sea:\n", "\n", "$next(x) = $ menor número de la suerte que es mayor o igual a $x$\n", "\n", "\n", "Recibirás dos números $l, r$ y deberás imprimir $next(l) + next(l + 1) + \\dots + next(r)$ (se garantiza que la respuesta puede ser almacena en un entero de 64-bits)\n", "\n", "$$1 \\leq l \\leq r \\leq 10 ^ 9$$\n", "\n", "**Hint:** La cantidad de números de la suerte en el rango necesitado es poco \n", "**[Link del problema](https://codeforces.com/contest/121/problem/C)** \n", "**[Solución](./examples/p06.cpp)**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Problema 7\n", "\n", "Dos números $a, b$ se dice que son $k-$interesantes si su representación binaria difiere en exactamente $k$ bits.\n", "Dado $n, k$ y una secuencia $a_1, a_2, \\dots a_n$. Determinar cuantos pares $(i, j)$ existen tal que $i < j$ y $a_i, a_j$ son $k-$ interesantes.\n", "\n", "$$1 \\leq n \\leq 10 ^ 5$$\n", "$$0 \\leq k \\leq 14$$\n", "$$0 \\leq a_i \\leq 10 ^ 4$$\n", "\n", "**Hint1:** Los valores $a_i$ son pequeños \n", "**Hint2:** La cantidad de distintos pares de números $a[i], a[j]$ que difieran en $k-$bits es poco \n", "**[Link del problema](https://codeforces.com/contest/769/problem/D)** \n", "**[Solución](./examples/p07.cpp)**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Problema 8\n", "\n", "Recibirás un entero $n$ seguido de $n$ números $a_1, a_2, \\dots, a_n$. Debes retornar a cantidad de pares $(i, j)$ tal que $i < j \\land a_i$ y $a_j$ tengan algun dígito en común (no necesariamente en la misma posición).\n", "\n", "$$1 \\leq n \\leq 5 \\cdot 10 ^ 5$$\n", "$$1 \\leq a_i \\leq 10 ^ {18}$$\n", "\n", "**Hint:** Se puede representar un número como una máscara que indique que digitos tiene el número usando 10-bits \n", "**[Link del problema](https://www.spoj.com/problems/KOMPICI/)** \n", "**[Solución](./examples/p08.cpp)**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Problema 9\n", "\n", "Recibirás un $n$ seguido de una sudoku de $n ^ 2 \\times n ^ 2$ donde los espacios que aún no se han completado tendrán 0's. El objetivo es imprimir la solución del sudoku con el menor [orden lexicográfico](https://es.wikipedia.org/wiki/Orden_lexicogr%C3%A1fico) o imprimir 'NO SOLUTION' en caso de no tener solución el sudoku dado.\n", "\n", "Por ejemplo, para $n = 3$, si se recibe el sudoku de la izquierda, se deberá retornar el sudoku de la derecha.\n", "\n", "![](./images/sudoku.png)\n", "\n", "**Hint:** Backtracking \n", "**[Link del problema](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=930)** \n", "**[Solución](./examples/p09.cpp)**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## [Contest time!!!](https://vjudge.net/contest/288350)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Apéndice 1\n", "\n", "**Afimación:** $\\sigma_0(n) = O(n ^ {1/ 3)}$\n", "\n", "**Prueba:**\n", "\n", "$sigma_0$ es una función multiplicativa. Luego, observamos que es suficiente demostrar que lo anterior se cumple para un $n = p ^ k$ (pues para un $n$ que no tenga esa forma bastará usar la representación prima de este número y manipular unas desigualdades)\n", "\n", "Y como queremos encontrar $\\sigma_0(n) = O(n ^ {1/ 3)}$ bastará con demostrar que lo anterior se cumple a partir de un $n$ lo suficientemente grande (en este caso, para $p > 8$)\n", "\n", "Los divisores se $p ^ k son \\{1, p, p ^ 2, \\dots, p ^ k\\}$\n", "\n", "$$\\to \\sigma_0 (p ^ k) = k + 1 \\leq 2 ^ k$$\n", "$$\\to \\sigma_0 ^ 3 (p ^ k) \\leq 8 ^ k < p ^ k$$\n", "$$\\to \\sigma_0(p ^ k) = O((p ^ k) ^ {1 / 3} )$$\n", "\n", "Por lo tanto, $\\sigma_0(n) = O(n ^ {1/ 3)}$" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.1" } }, "nbformat": 4, "nbformat_minor": 2 }