{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Clase 05\n",
    "\n",
    "### Objetivos\n",
    "\n",
    "* Discutir los problemas del contest de la anterior clase\n",
    "* Ver más ejemplos de fuerza bruta"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solucionario del contest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [A - Wonderful Randomized Sum](https://codeforces.com/contest/33/problem/C)\n",
    "\n",
    "#### Resumen del enunciado\n",
    "\n",
    "Dada una sequencia de `n` números, puedes tomar cualquier prifijo y sufijo de la secuencia e invertir el signo de los elementos del prefijo o sufijo tomado. Determina cual es la máxima suma de elementos que puedes conseguir.\n",
    "\n",
    "#### Límites\n",
    "\n",
    "$$3 \\leq n \\leq 1e5$$\n",
    "$$-10^4 \\leq a_i \\leq 10^4$$\n",
    "\n",
    "#### Solución\n",
    "\n",
    "Sea:\n",
    "\n",
    "* `left[i]:` máxima suma conseguida en $[1, i]$ tomando algún prefijo\n",
    "* `right[i]:` máxima suma conseguida en $[i, n]$ tomando algún sufijo\n",
    "\n",
    "Luego, la respuesta sería `max(left[i] + right[i + 1]` $\\mid \\quad i \\in [1, n]$ `)`\n",
    "\n",
    "Ahora, notamos que (en clase se explicará con más detalle esto):\n",
    "\n",
    "* `left[0] = 0`\n",
    "* `left[i] = max(left[i - 1] + arr[i], abs(sum(1, i)))`\n",
    "* `right[n + 1] = 0`\n",
    "* `right[i] = max(right[i + 1] + arr[i], abs(sum(i, n)))`\n",
    "\n",
    "Donde: `sum(i, j) = suma de los elementos entre i y j` \n",
    "\n",
    "Así, con las relaciones anterior podemos calcular la respuesta en `O(n)`\n",
    "\n",
    "[Implementación](https://codeforces.com/contest/33/submission/48694275)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [B - Number of Triplets](https://codeforces.com/contest/181/problem/B)\n",
    "\n",
    "#### Resumen del enunciado\n",
    "\n",
    "Dados `n` puntos. Determinar la cantidad de tripletas `(A, B, C)` donde `B` sea punto medio de `A` y `C`. \n",
    "\n",
    "#### Límites\n",
    "\n",
    "$$3 \\leq n \\leq 3000$$\n",
    "$$-1000 \\leq x, y \\leq 1000$$\n",
    "\n",
    "#### Solución\n",
    "\n",
    "Si fijamos los puntos `A` y `C`, podemos calcular `B` y si guardamos todos los puntos en un set podemos determinar en `O(log n)` si `B` es un punto dado en la entrada (sumando 1 a nuestra respuesta). Asi, podemos solucionarlos en $\\text{O(} n ^ 2 \\log n \\text{)}$\n",
    "\n",
    "**Extra:** ¿Cómo podríamos solucionarlo en $\\text{O(} n ^ 2 \\text{)}$ ?\n",
    "\n",
    "[Implementación](https://codeforces.com/contest/181/submission/48690302)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [C - Unsorting Array](https://codeforces.com/problemset/problem/252/B)\n",
    "\n",
    "#### Resumen del enunciado\n",
    "\n",
    "Dado un array de `n` elementos. Determinar dos índices $i, j$  $(arr[i] \\not = arr[j] \\land i < j)$ de manera que al intercambiar las posiciones de $i$ y $j$ el array no este ordenado de forma ascendente ni descentente.\n",
    "\n",
    "#### Límites\n",
    "\n",
    "$$1 \\leq n \\leq 10 ^ 5$$\n",
    "$$0 \\leq arr[i] \\leq 10 ^ 9 $$\n",
    "\n",
    "#### Solución\n",
    "\n",
    "Sea $(i, j)$ las posiciones a intercambiar.\n",
    "* Si $arr[i] < arr[j]$. Si al cambiarlas el array no queda ordenado de forma descendente, tenemos una respuesta. Sino el\n",
    "  array tiene la forma\n",
    "  \n",
    "  $$arr_1 \\geq arr_2 \\geq \\dots arr_j \\geq \\dots \\geq arr_i \\geq \\dots \\geq arr_n $$\n",
    "\n",
    "  De manera que ya no podríamos encontrar otro par $(i, j) \\mid arr[i] < arr[j]$\n",
    "\n",
    "* Si $arr[i] > arr[j]$. Si al cambiarlas el array no queda ordenado de forma ascendente, tenemos una respuesta. Sino el \n",
    "  array tiene la forma\n",
    "  \n",
    "  $$arr_1 \\leq arr_2 \\leq \\dots arr_j \\leq \\dots \\leq arr_i \\leq \\dots \\leq arr_n $$\n",
    "\n",
    "  De manera que ya no podríamos encontrar otro par $(i, j) \\mid arr[i] > arr[j]$\n",
    "\n",
    "Así, podemos buscar un par $(i, i + 1) \\mid arr[i] < arr[i + 1]$ y otro par $(i, i + 1) \\mid arr[i] > arr[i + 1]$. Si encontramos esos pares y con ninguno encontramos una respuesta. Entonces, no hay respuesta. \n",
    "\n",
    "Luego, lo anterior podemos implementarlo en `O(n)` o `O(n log n)`\n",
    "\n",
    "[Implementación](https://codeforces.com/contest/252/submission/48695232)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [D - Fibonacci-ish](https://codeforces.com/problemset/problem/633/D)\n",
    "\n",
    "#### Resumen del enunciado\n",
    "\n",
    "Dado un array de `n` numereros. Encontrar el tamaño de la secuencia más grande que se puede formar con los elementos del array (cada elemento es tomado a lo más una vez) donde la secuencia es de la forma.\n",
    "\n",
    "$$f_0 = a_i$$\n",
    "$$f_1 = a_j \\quad i \\not = j$$\n",
    "$$f_k = f_{k - 1} + f_{k - 2} \\quad k \\geq 2 \\land f_k \\text{es un elemento aun no tomado del array}$$\n",
    "\n",
    "#### Límites\n",
    "\n",
    "$$1 \\leq n \\leq 10 ^ 3$$\n",
    "$$-10^9 \\leq arr[i] \\leq 10 ^ 9 $$\n",
    "\n",
    "#### Solución\n",
    "\n",
    "Si fijamos $f_0$ y $f_1$ podemos simular ir formando la secuencia deseada (notemos que $f_0 = f_1 = 0$ podemos tratarlo\n",
    "como un caso especial). Así, podriamos lograr una solución\n",
    "`O(n * n * k)` donde `k` sería el tamaño de la secuencia más larga donde ($f_0 \\not = 0 \\lor f_1 \\not = 0$).\n",
    "\n",
    "Pero recordamos que en una clase previa mostramos como para $f_0 = 0, f_1 = 1, f_{95} > 10 ^ {18}$. Luego, notamos que \n",
    "para otros $f_0, f_1$ definitivamente antes del término 95 la secuencia tendrá un valor absoluto mayor a 10 a la 9.\n",
    "\n",
    "Así, nuestra solución `O(n * n * k)` debería pasar. \n",
    "\n",
    "**Nota:** En esta implementación se uso un mapa para la simulación, por lo que en realidad la complejidad es `O(n * n * k * log k)`\n",
    "\n",
    "[Implementación 1](https://codeforces.com/contest/633/submission/48698184)\n",
    "\n",
    "**Extra:** En el código anterior, esta sección:\n",
    "        \n",
    "```c++\n",
    "int c = (a + b);\n",
    "if (frec[c] == 0) break;\n",
    "frec[c]--;\n",
    "```\n",
    "\n",
    "Hace que tengamos que buscar el elemento `c` dos veces en el mapa, y esta operación se hace un gran cantidad de veces.\n",
    "\n",
    "Luego, se podría hacer esto para reducir un poco el tiempo de ejecución:\n",
    "    \n",
    "```c++\n",
    "int c = (a + b);\n",
    "int& f = frec[c]; // una referencia a frec[c]\n",
    "if (f == 0) break;\n",
    "f[c]--;\n",
    "```\n",
    "Ya que solo buscamos a `c` una vez en el mapa (como ya tenemos la referencia `f[c]--` es `O(1)`)\n",
    "\n",
    "[Implementación 2](https://codeforces.com/contest/633/submission/48698163)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [E - New Year Cards](https://codeforces.com/contest/140/problem/B)\n",
    "\n",
    "#### Resumen del enunciado\n",
    "\n",
    "Tienes `n` amigos. El amigo `i` te enviará la tarjeta `i` (comenzará el primer amigo, luego el segundo, ...).\n",
    "Cada amigo tiene una lista de preferencencias de que tarjeta le gustaría recibir y tu tienes una lista de preferencia de que tarjeta te gustaria enviar. Para enviar una tarjeta al amigo `i` debes seguir las siguientes reglas:\n",
    "\n",
    "* Entre las tarjetas que tienes, escogeras aquellas por la que tengas más preferencia de enviar y que sea distinta de `i`.\n",
    "* Si ya habias pensado enviarle otra tarjeta al amigo `i`, la tarjeta que le piensas enviar ahora tiene que tener mayor preferencia para `i`.\n",
    "\n",
    "Básicamente, así podemos interpretar el enunciado por practicidad.\n",
    "\n",
    "#### Límites\n",
    "\n",
    "$$2 \\leq n \\leq 300$$\n",
    "\n",
    "#### Solución\n",
    "\n",
    "Podemos simular lo descrito en el enunciado en `O(n * n * n)`. Ver la implementación para más detalles.\n",
    "\n",
    "\n",
    "[Implementación](https://codeforces.com/contest/140/submission/48719947)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [F - Hot Bath](https://codeforces.com/contest/126/problem/A)\n",
    "\n",
    "#### Resumen del enunciado\n",
    "\n",
    "Dado $t_1, t_2, t_0, x_1, x_2$\n",
    "\n",
    "Sea\n",
    "\n",
    "$$t(y_1, y_2) = \\frac{y_1 * t_1 + y_2 * t_2}{y_1 + y_2} \\mid 1 \\leq y_1 \\leq x_1 \\land 1 \\leq y_2 \\leq x_2$$\n",
    "\n",
    "Encontrar para que valores de $y_1, y_2$, $t(y1, y2)$ es lo más cercano posible a $t_0$. En caso de múltiples respuestas\n",
    "imprimir aquella donde $y1 + y2$ es máximo.\n",
    "\n",
    "#### Límites\n",
    "\n",
    "$$1 \\leq t_1 \\leq t_0 \\leq t_2 \\leq 10 ^ 6$$\n",
    "$$1 \\leq x_1, x_2 \\leq 10 ^ 6$$\n",
    "\n",
    "#### Solución\n",
    "\n",
    "$$y_1 \\cdot \\frac{(t_1 - t_0)}{(t_0 - t_2)} \\geq y_2 $$\n",
    "\n",
    "Luego, podemos fijar $y_1$, calcular $y_2$ a partir de ello e ir maximixando la respuesta.\n",
    "\n",
    "Así, podemos resolver el problema en `O(x_1)`\n",
    "\n",
    "**Nota:** Tener cuidado con la precisión.\n",
    "\n",
    "[Implementación](https://codeforces.com/contest/126/submission/48701713)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [G - Easy Tape Programming](https://codeforces.com/contest/239/problem/B)\n",
    "\n",
    "#### Resumen del enunciado\n",
    "\n",
    "Dado\n",
    "\n",
    "$$s_1s_2 \\cdots s_n \\quad \\mid s_i \\in \\{<, >, 1, 2, \\cdots, 9\\}$$\n",
    "\n",
    "Recibirás `q` consultas de la forma `l r`. En cada consulta debes simular la\n",
    "ejecución de \n",
    "\n",
    "$$ s_l \\cdots s_r $$\n",
    "\n",
    "e imprimir la cantidad de veces que se imprimio cada dígito (`0-9`)\n",
    "\n",
    "Para simular la ejecución de la secuencia $s_l \\cdots s_r$ usted comienza en la\n",
    "posicion `l` en la direccion derecha. Ahora:\n",
    "\n",
    "* Si la sentencia actual es un dígito. Imprímelo y muevete en tu dirección\n",
    "  actual. Luego, reduce el número de la anterior sentencia en 1. Si este se\n",
    "vuelve negativo, eliminalo de la secuencia.\n",
    "* Si la sentencia actual es `<` o `>` cambia la dirección hacia la izquida\n",
    "  o derecha respectivamente. Luego, muevete en tu dirección actual. Si la\n",
    "sentencia en tu posición actual es `<` o `>`, elimina la sentencia de tu\n",
    "anterior posición.\n",
    "\n",
    "* Si tu posición actual no esta en `[l, r]`. Termina la simulación.\n",
    "\n",
    "#### Límites\n",
    "\n",
    " $$1 \\leq n, q \\leq 100 $$\n",
    "\n",
    "#### Solución\n",
    "\n",
    "En el peor de los casos (una consulta de al forma `>99...99<`) la simulación\n",
    "se hara en `O(n)`\n",
    "\n",
    "Luego, bastará simular la ejecución de cada consulta siguiendo la descripción\n",
    "del enunciado para obtener una solución en `O(q n)`\n",
    "\n",
    "**Nota:** Tener cuidado, las consultas son independientes entre sí.\n",
    "\n",
    "[Implementación](https://codeforces.com/contest/239/submission/48684436)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [H - Restoring Increasing Sequence](https://codeforces.com/contest/490/problem/E)\n",
    "\n",
    "#### Resumen del enunciado\n",
    "\n",
    "Se tiene una secuencia $a_1, a_2, \\cdots a_n$ donde algunos dígitos han sido\n",
    "reemplazados por `?`. Ahora, deberás reemplazar los `?` por dígitos de tal\n",
    "forma que \n",
    "\n",
    "$$a_1 < a_2 < \\cdots < a_n$$\n",
    "\n",
    "e imprimir dicha secuencia (si hay multiples respuestas, imprime alguna válida)\n",
    "o indicar que es imposible formar tal secuencia. Tener en cuenta que los\n",
    "números formados no pueden tener `0` como primer dígito.\n",
    "\n",
    "#### Límites\n",
    "\n",
    "$$n < 10 ^ 5$$\n",
    "$$1 < a_i < 10 ^ 8$$\n",
    "\n",
    "#### Solución\n",
    "\n",
    "Si ya tengo formado el número $a_i$. Para formar $a_{i + 1}$ puedo intentar\n",
    "formar un número mayor que $a_i$ lo menor posible.\n",
    "\n",
    "Si $a_{i + 1} > a_i$ y ambos tienen la misma cantidad de dígitos. Entonces\n",
    "ambos tendrán la forma:\n",
    "$$a_i = \\overline{xmy}$$\n",
    "$$a_{i + 1} = \\overline{xnz}$$\n",
    "\n",
    "Y $n > m$ y $z$ puede tomar cualquier forma.\n",
    "\n",
    "Luego, para hacer $a_{i + 1}$ lo más pequeño posible, nos conviene hacer $n = m + 1$ y hacer que `z` sea tan pequeño como sea\n",
    "posible (para lo cual nos conviene completar con `0`s los `?` en `z`). \n",
    "\n",
    "Así, simplemente cada `?` en $a_{i + 1}$ puedo tomarlo como la posición de `n`\n",
    "e intentar formar $a_{i + 1}$ y al final tomar el menor $a_{i + 1}$ formado (Si\n",
    "no logro formar ningun $a_{i + 1}$ entonces no hay respuesta). Como $a_i$ tiene\n",
    "a lo mucho `8` digitos. Entonces, en `O(8 * 8) = O(1)` podemos formar todas las\n",
    "posibilidades de $a_{i + 1}$.\n",
    "\n",
    "Finalmente, puedo agrupar los números dados por su cantidad de dígitos. Ir completando\n",
    "los `?` con lo anterior descrito. Juntar todas las secuencia y comprobar si se\n",
    "forma una respuesta válida en `O(n)`.\n",
    "\n",
    "[Implementación](https://codeforces.com/contest/490/submission/48590505)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [I - Divisors](https://codeforces.com/contest/448/problem/E)\n",
    "\n",
    "#### Resumen del enunciado\n",
    "\n",
    "Sea:\n",
    "\n",
    "$$D(x) = \\{ \\text{Los divisores de x ordenados de menor a mayor} \\} $$\n",
    "\n",
    "$$f_0(x) = \\{x\\}$$\n",
    "$$f_k(x) = \\bigcup_{d \\in D(X)} f_{k -1}(d)$$\n",
    "\n",
    "Recibirás un `x, d` y deberás imprimir los primos $10 ^ 5$ términos de $f_k(x)$\n",
    "\n",
    "#### Límites\n",
    "\n",
    "$$1 \\leq X \\leq 10 ^ {12}$$\n",
    "$$0 \\leq k \\leq 10 ^ {18}$$\n",
    "\n",
    "#### Solución\n",
    "\n",
    "Notemos que:\n",
    "$$f_k(p) = \\{1\\} \\times k \\quad  \\bigcup \\quad \\{p\\} \\quad \\mid p \\text{ es primo }$$\n",
    "$$f_k(1) = \\{1\\}$$\n",
    "\n",
    "Luego, notemos que bastará simular la recurrencia anterior mientras mantenemos\n",
    "un contador de cuantos números ya hemos imprimido (lo cual nos indicará cuando \n",
    "detenernos)\n",
    "\n",
    "Ahora, necesitamos tener un vector con los divisores que necesitaremos de\n",
    "manera rápida. Para ello podemos fijar una constante, por ejemplo \n",
    "\n",
    "$$ \\text{MX}= 10 ^ 5 $$\n",
    "\n",
    "Preprocesar todos los divisores de los números $< \\text{MX}$ en `O(MX log MX)`\n",
    "y aquellos $x \\geq \\text{MX}$ en $\\text{O(}\\sqrt{x} \\text{)}$ (Se explicará esto en clase).\n",
    "\n",
    "Consiguiendo así una solución en $\\text{O(} \\sqrt{x} + \\text{MX} \\log \\text{MX}  \\text{)}$\n",
    "\n",
    "[Implementación](https://codeforces.com/contest/448/submission/48651120)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Más ejemplos de fuerza bruta\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [Cut Ribbon](https://codeforces.com/problemset/problem/189/A)\n",
    "\n",
    "Dado\n",
    "\n",
    "$$a, b, c, n$$\n",
    "$$\\text{Encontrar: } \\max(x + y + z \\mid x \\cdot a + y \\cdot b + z \\cdot c =  n \\land x, y, z \\geq 0)$$\n",
    "\n",
    "$$1 \\leq a, b, c, n \\leq 4000$$\n",
    "\n",
    "### Solución:\n",
    "\n",
    "Podemos fijar $(x, y)$ y partir de ello determinar $z$ en `O(n * n)`\n",
    "\n",
    "[Implementación](https://codeforces.com/contest/189/submission/21265127)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [2Char](https://codeforces.com/contest/593/problem/A)\n",
    "\n",
    "\n",
    "Dado `n` palabras. Sea\n",
    "\n",
    "$$f(ch1, ch2) = \\sum |s_i| \\mid s_i \\text{ solo está formado con } ch1 \\lor ch2$$\n",
    "\n",
    "Encontrar $$max(f(ch1, ch2) \\mid ch2, ch2 \\in a, b, \\dots, c)$$\n",
    "\n",
    "$$1 \\leq n \\leq 100$$\n",
    "$$1 \\leq MAX_LEN \\leq 1000$$\n",
    "\n",
    "### Solución:\n",
    "\n",
    "Podemos fijar (ch1, ch2) y ver cuantas palabras cumplen la condición en `O(26 * 26 * n * MAX_LEN)`\n",
    "\n",
    "[Implementación](https://codeforces.com/contest/593/submission/34567942)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problemas para practicar\n",
    "\n",
    "1. [Intense Heat](https://codeforces.com/contest/1003/problem/C)\n",
    "2. [Alphabetic Removals](https://codeforces.com/contest/999/problem/C)\n",
    "3. [Alyona and Numbers](https://codeforces.com/contest/682/problem/A)\n",
    "4. [Second Order Statistics](https://codeforces.com/contest/22/problem/A)\n",
    "5. [Nearly Lucky Number](https://codeforces.com/contest/110/problem/A)\n",
    "6. [Triangular numbers](https://codeforces.com/contest/47/problem/A)\n",
    "7. [Beautiful Year](https://codeforces.com/contest/271/problem/A)\n",
    "8. [Far Relative’s Birthday Cake](https://codeforces.com/contest/629/problem/A)\n",
    "9. [Decoding](https://codeforces.com/contest/746/problem/B)\n",
    "10. [ACMCEG2B - FIGUREFUL](https://www.spoj.com/problems/ACMCEG2B/)\n",
    "11. [SORT2D - 2D-SORT](https://www.spoj.com/problems/SORT2D/)\n",
    "12. [Link/Cut Tree](https://codeforces.com/contest/614/problem/A)\n",
    "13. [Economy Game](https://codeforces.com/problemset/problem/681/B)\n",
    "14. [Little Xor](https://codeforces.com/problemset/problem/252/A)\n",
    "15. [Non-square Equation](https://codeforces.com/problemset/problem/233/B)\n",
    "16. [Pythagorean Theorem II](https://codeforces.com/problemset/problem/304/A)\n",
    "17. [Batch Sort](https://codeforces.com/problemset/problem/724/B)\n",
    "18. [Pride](https://codeforces.com/problemset/problem/892/C)\n",
    "19. [Really Big Numbers](https://codeforces.com/problemset/problem/817/C)\n",
    "20. [Jimmy's Balls](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2475)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### También te podría interesar revisar el material del curso del año pasado sobre el tema.\n",
    "\n",
    "[Fuerza Bruta I - PCUNI - No Fiis - 2018](https://nbviewer.jupyter.org/github/GPC-UNI/Programacion-Competitiva/blob/master/uni-no-fiis/clase-03/clase_03.ipynb)"
   ]
  }
 ],
 "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
}