{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Clase 07"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*“Premature optimization is the root of all evil.”*\n",
    "\n",
    "*― Donald Ervin Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Objtivos\n",
    "\n",
    "* Entender las soluciones de los problemas del último contest\n",
    "* Resolver algunos problemas usando recursión"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Las soluciones se explicarán en más detalle en clase.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [1 - Nice Icerland](https://codeforces.com/problemset/problem/1108/C)\n",
    "\n",
    "### Solución\n",
    "\n",
    "Basta darse cuenta que la respuesta tiene la forma $abcabcabc \\dots$ donde $abc$ es una permutación de $RGB$, luego podemos probar todas las opciones en $O(3!n) = O(n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <bits/stdc++.h>\n",
    "\n",
    "using namespace std;\n",
    "\n",
    "int main () {\n",
    "  int n;\n",
    "  cin >> n;\n",
    "  string s;\n",
    "  cin >> s;\n",
    "  vector <char> p = {0, 1, 2};\n",
    "  string X = \"RGB\";\n",
    "  int mn = INT_MAX;\n",
    "  string ans;\n",
    "  do {\n",
    "    int cnt = 0;\n",
    "    for (int i = 0; i < 3 and i < s.size(); i++) {\n",
    "      for (int j = i; j < s.size(); j += 3) {\n",
    "        cnt += s[j] != X[p[i]];\n",
    "      }\n",
    "    }\n",
    "    if (cnt < mn) {\n",
    "      mn = cnt;\n",
    "      string ret = \"\";\n",
    "      for (int k = 0; k < s.size(); k++) {\n",
    "        ret += X[p[k % 3]];\n",
    "      }\n",
    "      ans = ret;\n",
    "    }\n",
    "  } while (next_permutation(begin(p), end(p)));\n",
    "  cout << mn << endl;\n",
    "  cout << ans << endl;\n",
    "  return (0);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [2 - Minimum Sum](https://codeforces.com/problemset/problem/910/C)\n",
    "\n",
    "### Solución\n",
    "\n",
    "Notemos que $abcdefghij$ será una permutación de $0123456789$. Luego, pademos buscar la respuesta en cada permutación en $O(q!n)$ con $q = 10$, pero $n \\leq 1000$ así que ese enfoque daría `TLE`. Sim embargo, notamos que podemos guardar un contador de frecuencia por posiciones y luego simular la suma con ello, logrando así una solución en $O(q!L S)$ con $L \\leq 6 \\land S = 10$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <bits/stdc++.h>\n",
    "\n",
    "using namespace std;\n",
    "\n",
    "const int LEN = 6, SIGMA = 10;\n",
    "\n",
    "int cnt[LEN + 1][SIGMA + 1], val[SIGMA + 1];\n",
    "bool invalid[SIGMA + 1];\n",
    "\n",
    "int main () {\n",
    "  int n;\n",
    "  cin >> n;\n",
    "  for (int i = 0; i < n; i++) {\n",
    "    string number;\n",
    "    cin >> number;\n",
    "    invalid[number[0] - 'a'] = true;\n",
    "    int sz = number.size();\n",
    "    for (int j = 0; j < sz; j++) {\n",
    "      cnt[LEN - sz + j][number[j] - 'a']++;\n",
    "    }\n",
    "  }\n",
    "  string sigma = \"abcdefghij\";\n",
    "  int ans = INT_MAX;\n",
    "  do {\n",
    "    if (invalid[sigma[0] - 'a']) continue;\n",
    "    int p = 0;\n",
    "    for (const char ch: sigma) val[ch - 'a'] = p++;\n",
    "    int sum = 0, carry = 0, power = 1;\n",
    "    for (int i = LEN - 1; i >= 0; i--) {\n",
    "      int ac = 0;\n",
    "      for (int j = 0; j < SIGMA; j++) {\n",
    "        ac += cnt[i][j] * val[j];\n",
    "      }\n",
    "      ac += carry;\n",
    "      sum = sum + power * (ac % 10);\n",
    "      power *= 10;\n",
    "      carry = ac / 10;\n",
    "    }\n",
    "    while (carry) {\n",
    "      sum = sum + power * (carry % 10);\n",
    "      power *= 10;\n",
    "      carry /= 10;\n",
    "    }\n",
    "    ans = min(ans, sum);\n",
    "  } while (next_permutation(begin(sigma), end(sigma)));\n",
    "  cout << ans << endl;\n",
    "  return (0);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [3 - Nice table](https://codeforces.com/problemset/problem/1099/E)\n",
    "\n",
    "### Solución\n",
    "\n",
    "Sea $abcd$ una permutación de $AGTC$\n",
    "\n",
    "Luego, notemos que una matriz de $1 \\times n$ tendra la forma:\n",
    "\n",
    "$$ababababababab \\dots$$\n",
    "\n",
    "Una matriz de $2 \\times n$ tendrá la forma:\n",
    "\n",
    "$$ababab \\dots$$\n",
    "$$cdcdcd \\dots$$\n",
    "\n",
    "Ahora, observamos que una matriz de $n \\times m$ en todas las filas impares tendrá alguna de estas 2 formas:\n",
    "\n",
    "$$ababab \\dots \\text{ | } bababa \\dots$$\n",
    "\n",
    "Y las filas pares tendrán alguna de estas 2 formas:\n",
    "\n",
    "$$cdcdcd \\dots \\text{ | } dcdcdc \\dots$$\n",
    "\n",
    "Asi, para cada permutación de $AGTC$ podemos probar obtener una matriz con las anteriores caracteristicas (de manera que minimicemos la cantidad de celdas a cambiar) y luego intentamos hacer lo mismo en la matriz transpuesta en $O(4!nm) = O(nm)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <bits/stdc++.h>\n",
    "\n",
    "using namespace std;\n",
    "\n",
    "int n, m;\n",
    "vector <string> table;\n",
    "\n",
    "int rowCheck (vector <string>& tmp, string pat) {\n",
    "  int totalCost = 0;\n",
    "  for (int row = 0; row < n; row++) {\n",
    "    char a, b;\n",
    "    if (row & 1) a = pat[2], b = pat[3];\n",
    "    else a = pat[0], b = pat[1];\n",
    "    int cost1 = 0, cost2 = 0;\n",
    "    for (int col = 0; col < m; col++) {\n",
    "      if (col & 1) cost1 += table[row][col] != b;\n",
    "      else cost1 += table[row][col] != a;\n",
    "    }\n",
    "    swap(a, b);\n",
    "    for (int col = 0; col < m; col++) {\n",
    "      if (col & 1) cost2 += table[row][col] != b;\n",
    "      else cost2 += table[row][col] != a;\n",
    "    }\n",
    "    totalCost += min(cost1, cost2);\n",
    "    if (cost1 < cost2) swap(a, b);\n",
    "    for (int col = 0; col < m; col++) tmp[row][col] = (col & 1) ? b : a;\n",
    "  }\n",
    "  return totalCost;\n",
    "}\n",
    "\n",
    "int colCheck (vector <string>& tmp, string pat) {\n",
    "  int totalCost = 0;\n",
    "  for (int col = 0; col < m; col++) {\n",
    "    char a, b;\n",
    "    if (col & 1) a = pat[1], b = pat[3];\n",
    "    else a = pat[0], b = pat[2];\n",
    "    int cost1 = 0, cost2 = 0;\n",
    "    for (int row = 0; row < n; row++) {\n",
    "      if (row & 1) cost1 += table[row][col] != b;\n",
    "      else cost1 += table[row][col] != a;\n",
    "    }\n",
    "    swap(a, b);\n",
    "    for (int row = 0; row < n; row++) {\n",
    "      if (row & 1) cost2 += table[row][col] != b;\n",
    "      else cost2 += table[row][col] != a;\n",
    "    }\n",
    "    if (cost1 < cost2) swap(a, b);\n",
    "    totalCost += min(cost1, cost2);\n",
    "    for (int row = 0; row < n; row++) tmp[row][col] = (row & 1) ? b : a;\n",
    "  }\n",
    "  return totalCost;\n",
    "}\n",
    "\n",
    "int main () {\n",
    "  cin >> n >> m;\n",
    "  table.resize(n);\n",
    "  for (int row = 0; row < n; row++) cin >> table[row];\n",
    "  string AGCT = \"AGCT\";\n",
    "  int mn = n * m + 1;\n",
    "  vector <string> ans;\n",
    "  do {\n",
    "    vector <string> tmp1(n, string(m, ' '));\n",
    "    vector <string> tmp2(n, string(m, ' '));\n",
    "    int ret1 = rowCheck(tmp1, AGCT);\n",
    "    int ret2 = colCheck(tmp2, AGCT);\n",
    "    if (ret1 <= ret2 and ret1 < mn) {\n",
    "      ans = tmp1;\n",
    "      mn = ret1;\n",
    "    }\n",
    "    if (ret2 <= ret1 and ret2 < mn) {\n",
    "      ans = tmp2;\n",
    "      mn = ret2;\n",
    "    }\n",
    "  } while (next_permutation(begin(AGCT), end(AGCT)));\n",
    "  for (string row: ans) cout << row << endl;\n",
    "  cerr << mn << endl;\n",
    "  return (0);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [4 - Farey sequences](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1349)\n",
    "\n",
    "### Solución\n",
    "\n",
    "Podemos simplemente generar todas las fracciones improvias en el rango pedido, ordenarlas e imprimir la respuesta en $O(n ^ 2)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <bits/stdc++.h>\n",
    "\n",
    "using namespace std;\n",
    "\n",
    "struct Fraction {\n",
    "    int num, den;\n",
    "    Fraction() {}\n",
    "    Fraction(const int& _num, const int& _den):\n",
    "        num(_num), den(_den) {}\n",
    "    bool operator < (const Fraction& other) const {\n",
    "        return num * other.den < den * other.num;\n",
    "    }\n",
    "    inline void print() const {\n",
    "        cout << num << \"/\" << den << endl;\n",
    "    }\n",
    "};\n",
    "\n",
    "int n, k;\n",
    "\n",
    "int main() {\n",
    "    while (cin >> n >> k) {\n",
    "        vector <Fraction> arr;\n",
    "        for (int den = 1; den <= n; den++) {\n",
    "            for (int num = 1; num <= den; num++) {\n",
    "                // __gcd(a, b) = mcm(a, b)\n",
    "                if (__gcd(num, den) == 1) {\n",
    "                    arr.push_back(Fraction(num, den));\n",
    "                }\n",
    "            }\n",
    "        }\n",
    "        sort(begin(arr), end(arr));\n",
    "        arr[k - 1].print();\n",
    "    }\n",
    "    return (0);\n",
    "}\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [5 - Children's Game](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1846)\n",
    "\n",
    "### Solución\n",
    "\n",
    "Notemos que queremos obtener un ordenamiento de los números de manera que al juntarlos de el mayor número posible. Luego, podemos ordenarlos con una relación de orden (ver código) en $O(n ^ 2 log n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <bits/stdc++.h>\n",
    "\n",
    "#define SIZE 60\n",
    "\n",
    "using namespace std;\n",
    "\n",
    "int n;\n",
    "string v[SIZE], s1, s2;\n",
    "\n",
    "bool cmp(const string& x, const string& y){\n",
    "    s1 = x + y, s2 = y + x;\n",
    "    return (s1 > s2);\n",
    "}\n",
    "\n",
    "int main(){\n",
    "    while(scanf(\"%d\", &n), n!=0){\n",
    "      for (int i = 0; i < n; i++) cin >> v[i];\n",
    "      sort(v, v + n, cmp);\n",
    "      for (int i = 0; i < n; i++) cout << v[i]; cout << endl;\n",
    "   }\n",
    "   return(0);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [6 - Football Sort](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1639)\n",
    "\n",
    "### Solución\n",
    "\n",
    "Creamos un `struct` con los datos necesarios para cada equipo y conforme vamos leyendo la entrada vamos actualizando sus parámetros. Luego, ordenamos los equipos de acuerdo a la relación señalada en el problema y los imprimos en $O(n log n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// En clase se detallara de que otras formas se podría haber implementado la solución\n",
    "#include <bits/stdc++.h>\n",
    "\n",
    "#define SIZE 20\n",
    "\n",
    "using namespace std;\n",
    "\n",
    "struct Team{\n",
    "   char name[SIZE], lower_name[SIZE];\n",
    "   int points, games, goals, sgoals, dif;\n",
    "}aux;\n",
    "\n",
    "int tc, t, g, pos1, pos2, g1, g2, j;\n",
    "char s[SIZE], team1[SIZE], team2[SIZE];\n",
    "vector <Team> v;\n",
    "\n",
    "inline bool equals(Team x, Team y) {\n",
    "   return (x.points == y.points && x.dif == y.dif && x.goals == y.goals);\n",
    "}\n",
    "\n",
    "bool cmp(const Team& x, const Team& y) {\n",
    "   if(x.points != y.points) return (x.points > y.points);\n",
    "   if(x.dif != y.dif) return (x.dif > y.dif);\n",
    "   if(x.goals != y.goals) return (x.goals > y.goals);\n",
    "   return (strcmp(x.lower_name, y.lower_name) < 0);\n",
    "}\n",
    "\n",
    "void lowerNames() {\n",
    "   for(int i = 0; i < v.size(); i++){\n",
    "      for(j = 0; v[i].name[j]; j++) v[i].lower_name[j] = tolower(v[i].name[j]);\n",
    "      v[i].lower_name[j] = '\\0';\n",
    "   }\n",
    "}\n",
    "\n",
    "int findTeam(char x[]) {\n",
    "   for(int i = 0; i < v.size(); i++) if(strcmp(v[i].name, x)==0) return i;\n",
    "}\n",
    "\n",
    "void printResults() {\n",
    "   int it = 1;\n",
    "   for(int i = 0; i < v.size(); i++, it++){\n",
    "      if(i == 0 || equals(v[i], v[i - 1]) == false) printf(\"%2d.\", it);\n",
    "      else printf(\"   \");\n",
    "      printf(\"%16s %3d %3d %3d %3d %3d \", v[i].name, v[i].points, v[i].games, v[i].goals, v[i].sgoals, v[i].dif);\n",
    "      if(v[i].games) printf(\"%6.2f\\n\", 100.0 * v[i].points / (3.0 * v[i].games));\n",
    "      else printf(\"   N/A\\n\");\n",
    "   }  \n",
    "}\n",
    "\n",
    "int main(){\n",
    "    while (scanf(\"%d %d\\n\", &t, &g), t | g) {\n",
    "        if (tc++) putchar('\\n');\n",
    "        v.clear();\n",
    "        for (int i = 0; i < t; i++) scanf(\"%s\", s), strcpy(aux.name, s), v.push_back(aux);\n",
    "        for (int i = 0;i < g; i++){\n",
    "            scanf(\"%s %d - %d %s\", team1, &g1, &g2, team2);\n",
    "            pos1 = findTeam(team1);\n",
    "            pos2 = findTeam(team2);\n",
    "            if(g1 > g2) v[pos1].points += 3;\n",
    "            else if(g1 < g2) v[pos2].points += 3;\n",
    "            else v[pos1].points += 1, v[pos2].points += 1;\n",
    "            v[pos1].games += 1, v[pos2].games += 1;\n",
    "            v[pos1].goals += g1, v[pos2].goals += g2;\n",
    "            v[pos1].sgoals += g2, v[pos2].sgoals += g1;\n",
    "            v[pos1].dif += g1 - g2;\n",
    "            v[pos2].dif += g2 - g1;\n",
    "        }\n",
    "        lowerNames();\n",
    "        sort(v.begin(), v.end(), cmp);\n",
    "        printResults();\n",
    "    }\n",
    "    return(0);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [7 - Petr and a Combination Lock](https://codeforces.com/problemset/problem/1097/B)\n",
    "\n",
    "### Solución:\n",
    "\n",
    "Cada angulo dado tiene 2 opciones (rotación horaria o antihoraria). Luego, simplemente podemos probar todas las opciones en $O(2 ^ n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <bits/stdc++.h>\n",
    "\n",
    "using namespace std;\n",
    "\n",
    "int n;\n",
    "vector <int> angle;\n",
    "\n",
    "bool check (int mask) {\n",
    "  int cur = 0;\n",
    "  for (int bit = 0; bit < n; bit++) {\n",
    "    if ((mask >> bit) bitand 1) cur += angle[bit];\n",
    "    else cur -= angle[bit];\n",
    "  }\n",
    "  return (cur % 360) == 0;\n",
    "}\n",
    "\n",
    "int main () {\n",
    "  cin >> n;\n",
    "  angle.resize(n);\n",
    "  for (int i = 0; i < n; i++) cin >> angle[i];\n",
    "  bool ok = false;\n",
    "  for (int mask = 0; mask < (1 << n); mask++) ok |= check(mask);\n",
    "  puts(ok ? \"YES\" : \"NO\");\n",
    "  return (0);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [8 - Splitting Numbers](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3084)\n",
    "\n",
    "### Solución\n",
    "\n",
    "Iteramos los bits y si esta prendido de acuerdo a la paridad de la cantidad de bits prendido encontrad hasta el momento vamos construyendo la respuesta."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <bits/stdc++.h>\n",
    "\n",
    "using namespace std;\n",
    "\n",
    "int main () {\n",
    "  int n;\n",
    "  while (cin >> n, n) {\n",
    "    int a = 0, b = 0;\n",
    "    bool toA = true;\n",
    "    for (int bit = 0; bit < 32; bit++) {\n",
    "      if ((n >> bit) & 1) {\n",
    "        if (toA) a |= 1 << bit;\n",
    "        else b |= 1 << bit;\n",
    "        toA = !toA;\n",
    "      }\n",
    "    }\n",
    "    cout << a << ' ' << b << endl;\n",
    "  }\n",
    "  return (0);\n",
    "}\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [9 - Flip Game](http://acm.timus.ru/problem.aspx?space=1&num=1060)\n",
    "\n",
    "### Solución\n",
    "\n",
    "Notemos que si selecciono una celda 2 veces el tablero no se altera. Así, para cada pieza solo tiene sentido el tomarla o el no tomarla. Luego, podemos simular las celdas que tomamos en $O(2 ^ n n ^ 2)$ donde $n = 16$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <bits/stdc++.h>\n",
    "\n",
    "using namespace std;\n",
    "\n",
    "int main () {\n",
    "  int dr[] = {0, 1, 0, -1, 0};\n",
    "  int dc[] = {0, 0, 1, 0, -1};\n",
    "  vector <string> grid(4);\n",
    "  vector <string> black(4, string(4, 'b'));\n",
    "  vector <string> white(4, string(4, 'w'));\n",
    "  for (int i = 0; i < 4; i++) cin >> grid[i];\n",
    "  int ans = INT_MAX;\n",
    "  for (int mask = 0; mask < (1 << 16); mask++) {\n",
    "    vector <string> tmp = grid;\n",
    "    int cnt = 0;\n",
    "    for (int bit = 0; bit < 16; bit++) {\n",
    "      if ((mask >> bit) & 1) {\n",
    "        cnt++;\n",
    "        int r = bit / 4;\n",
    "        int c = bit % 4;\n",
    "        for (int d = 0; d < 5; d++) {\n",
    "          int nr = r + dr[d];\n",
    "          int nc = c + dc[d];\n",
    "          if (0 <= min(nr, nc) and max(nr, nc) < 4) {\n",
    "            if (tmp[nr][nc] == 'b') tmp[nr][nc] = 'w';\n",
    "            else tmp[nr][nc] = 'b';\n",
    "          }\n",
    "        }\n",
    "      }\n",
    "    }\n",
    "    if (tmp == black or tmp == white) {\n",
    "      ans = min(ans, cnt);\n",
    "    }\n",
    "  }\n",
    "  if (ans == INT_MAX) puts(\"Impossible\");\n",
    "  else cout << ans << endl;\n",
    "  return (0);\n",
    "}\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Recursión\n",
    "\n",
    "![](./images/recursion.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Un algoritmo recursivo puede ser descrito asi:\n",
    "    \n",
    "* Si la instancia actual del problema puede ser resuelto directamente, *just do it!*\n",
    "* Sino, reduce el problema a instancias más simples del problema."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ejemplo 1\n",
    "\n",
    "Escribe un programa recursivo que reciba un entero e imprima su representación binaria."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solución\n",
    "\n",
    "**¿Qué diferencia hay entre la Solución 1 y Solución 2?**\n",
    "\n",
    "```c++\n",
    "#include <bits/stdc++.h>\n",
    "\n",
    "using namespace std;\n",
    "\n",
    "// Solucion 1\n",
    "void rec1 (int num, string& bin) {\n",
    "  if (num == 0) return;\n",
    "  bin += '0' + (num % 2);\n",
    "  rec1(num / 2, bin);\n",
    "}\n",
    "\n",
    "void printBinary1 (int num) {\n",
    "  string bin = \"\";\n",
    "  if (num == 0) bin = \"0\";\n",
    "  else rec1(num, bin);\n",
    "  reverse(begin(bin), end(bin));\n",
    "  cout << bin << endl;\n",
    "}\n",
    "\n",
    "// Solucion 2\n",
    "void rec2 (int num, string& bin) {\n",
    "  if (num == 0) return;\n",
    "  rec2(num / 2, bin);\n",
    "  bin += '0' + (num % 2);\n",
    "}\n",
    "\n",
    "void printBinary2 (int num) {\n",
    "  string bin = \"\";\n",
    "  if (num == 0) bin = \"0\";\n",
    "  else rec2(num, bin);\n",
    "  cout << bin << endl;\n",
    "}\n",
    "\n",
    "int main () {\n",
    "  printBinary1(8);\n",
    "  printBinary2(8);\n",
    "  return (0);\n",
    "}\n",
    "\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ejercicios de calentamiento\n",
    "\n",
    "1. Escribe un programa recursivo que retorne la suma de cifras de un entero.\n",
    "2. Escribe un programa recursivo que retorne el factorial de un entero.\n",
    "3. Escribe un programa recursivo que retorne `C(n, m)`.\n",
    "4. Escribe un programa recursivo `rec(n, d)` que retorne la cantidad de `d`s que posee el número `n`.\n",
    "5. Escribe un programa recursivo que calcule $a ^ b$ en $O(b)$ para $a, b$ enteros."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ejemplo 2\n",
    "\n",
    "Escribe un programa recursivo que calcule $a ^ b$ en $log (b)$ para $a, b$ enteros.\n",
    "\n",
    "Notamos que:\n",
    "\n",
    "\n",
    "$$\n",
    "power(a, b) =\n",
    "  \\begin{cases}\n",
    "    1       & \\quad \\text{si } b = 0\\\\\n",
    "    power(a, b / 2) ^ 2  & \\quad \\text{si } b \\text{ es par}\\\\\n",
    "    a * power(a, \\lfloor b / 2 \\rfloor) ^ 2 & \\quad \\text{si } b \\text{ es impar}\n",
    "  \\end{cases}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <bits/stdc++.h>\n",
    "\n",
    "using namespace std;\n",
    "\n",
    "long long sq (long long a) { return (a * a); }\n",
    "\n",
    "long long power (long long a, int b) {\n",
    "  if (b == 0) return 1;\n",
    "  if (b & 1) return a * sq(power(a, b / 2));\n",
    "  return sq(power(a, b / 2));\n",
    "}\n",
    "\n",
    "int main () {\n",
    "  cout << power(2, 60) << endl;\n",
    "  assert(power(2, 60) == (1LL << 60));\n",
    "  return (0);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ahora, analizaremos como resolver estos problemas:\n",
    "\n",
    "1. [CPCRC1C - Sum of Digits](https://www.spoj.com/problems/CPCRC1C/)\n",
    "2. [Fractal](http://poj.org/problem?id=2083)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Soluciones**\n",
    "\n",
    "1. [CPCRC1C - Sum of Digits](https://www.spoj.com/problems/CPCRC1C/)\n",
    "\n",
    "Básicamente nos piden:\n",
    "\n",
    "$$\\sum_{k = a}^{b}sumaDeDigitos(k)$$\n",
    "$$0 \\leq a \\leq b \\leq 1e9$$\n",
    "\n",
    "Luego, la solucion trivial de iterar en el rango $[a, b]$ nos daría una complejidad $(b \\log b)$ lo cual obviamente daría TLE.\n",
    "\n",
    "Entonces, busquemos una solución más eficiente.\n",
    "\n",
    "Primero, definamos:\n",
    "\n",
    "$$S(x) = \\sum_{k = 0}^{x}sumaDeDigitos(k)$$\n",
    "\n",
    "Luego, nuestro problema se reduce a calcular $S(b) - S(a - 1)$\n",
    "\n",
    "Ahora, centremonos en calcular eficientemente $S(x)$\n",
    "\n",
    "Sea $x = \\overline{a_na_{n-1} \\dots a_k \\dots a_2a_1}$\n",
    "\n",
    "Definamos\n",
    "$$cnt(x, k) = \\sum_{i = 0}^{x} \\text{el k-esimo digito de } i$$\n",
    "\n",
    "Luego $$S(x) = \\sum_{k = 0} ^ {n} cnt(x, k)$$\n",
    "\n",
    "Así, como n es $O(log x)$, todo se reduce a calcular eficientemente $cnt(x, k)$\n",
    "\n",
    "Ahora, para calcular $cnt(x, k)$ notemos que estaremos sumando los k-esimos digitos de los números $num \\in [0, x]$.\n",
    "\n",
    "Sea $num = \\overline{p_np_{n-1}\\dots p_{k +1}p_{k}k_{k -1}\\dots p_{1}}$ (podemos considerar que $num$ siempre tiene `n` digitos por simplicidad - si tiene menos de `n` digitos simplemente podemos agregarle ceros al inicio y no afectara la respuesta -)\n",
    "\n",
    "Ahora analicemos por casos:\n",
    "\n",
    "* Si $\\overline{p_np_{n-1}\\dots p_{k+1}} < \\overline{x_nx_{n-1}\\dots x_{k+1}}$\n",
    "\n",
    "    Entonces\n",
    "    \n",
    "    $\\overline{p_np_{n-1}\\dots p_{k+1}} \\in [0, \\overline{x_nx_{n-1}\\dots x_{k+1}} - 1] \\to $ este numeral puede tomar $\\overline{x_nx_{n-1}\\dots x_{k+1}}$ valores\n",
    "    \n",
    "    $\\overline{p_{k-1}\\dots p_{1}} \\in [0, 999 \\dots 9999] \\to$ este numeral puede tomar $10 ^ {k - 1}$ valores\n",
    "    \n",
    "    Ahora, notamos ademas que $p_k \\in [0, 9]$\n",
    "    \n",
    "    Luego, en este caso, la suma de los k-esimos dígitos sería:\n",
    "    \n",
    "    $$10 ^ {k - 1} \\times (\\overline{x_nx_{n-1}\\dots x_{k+1}}) \\times (0 + 1 + 2 + \\dots + 9) = 10 ^ {k - 1} \\times (\\overline{x_nx_{n-1}\\dots x_{k+1}}) \\times 45$$\n",
    "    \n",
    "* Si $\\overline{p_np_{n-1}\\dots p_{k+1}} = \\overline{x_nx_{n-1}\\dots x_{k+1}} \\quad \\land \\quad p_k < x_k$\n",
    "\n",
    "    Entonces\n",
    "    \n",
    "    $\\overline{p_np_{n-1}\\dots p_{k+1}} \\in [\\overline{x_nx_{n-1}\\dots x_{k+1}}, \\overline{x_nx_{n-1}\\dots x_{k+1}}] \\to $ este numeral puede tomar 1 valor\n",
    "    \n",
    "    $\\overline{p_{k-1}\\dots p_{1}} \\in [0, 999 \\dots 9999] \\to$ este numeral puede tomar $10 ^ {k - 1}$ valores\n",
    "    \n",
    "    Ahora, notamos ademas que $p_k \\in [0, max(0, x_k - 1)]$\n",
    "    \n",
    "    Luego, en este caso, la suma de los k-esimos dígitos sería:\n",
    "    \n",
    "    $$10 ^ {k - 1} \\times (0 + 1 + \\dots + max(0, x_k - 1)) = 10 ^ {k - 1} \\times max(0, x_k - 1) \\times (max(0, x_k - 1) + 1) / 2$$\n",
    "    \n",
    "\n",
    "* Si $\\overline{p_np_{n-1}\\dots p_{k+1}} = \\overline{x_nx_{n-1}\\dots x_{k+1}} \\quad \\land \\quad p_k = x_k$\n",
    "\n",
    "    Entonces\n",
    "    \n",
    "    $\\overline{p_np_{n-1}\\dots p_{k+1}} \\in [\\overline{x_nx_{n-1}\\dots x_{k+1}}, \\overline{x_nx_{n-1}\\dots x_{k+1}}] \\to $ este numeral puede tomar 1 valor\n",
    "    \n",
    "    $\\overline{p_{k-1}\\dots p_{1}} \\in [0, \\overline{x_{k - 1}\\dots x_1}] \\to$ este numeral puede tomar $\\overline{x_{k + 1} \\dots x_1} + 1$ valores\n",
    "    \n",
    "    Ahora, notamos ademas que $p_k \\in [x_k, x_k]$\n",
    "    \n",
    "    Luego, en este caso, la suma de los k-esimos dígitos sería:\n",
    "    \n",
    "    $$p_k \\times (\\overline{x_{k + 1} \\dots x_1} + 1)$$\n",
    "    \n",
    "    \n",
    "Notamos que ya no hay mas casos para analizar, luego $cnt(x, k)$ sería la suma de los resultados obtenidos en cada caso, obteniendo:\n",
    "\n",
    "$$cnt(x, k) = 10 ^ {k - 1} \\times (\\overline{x_nx_{n-1}\\dots x_{k+1}}) \\times 45 + 10 ^ {k - 1} \\times max(0, x_k - 1) \\times (max(0, x_k - 1) + 1) / 2  + p_k \\times (\\overline{x_{k + 1} \\dots x_1} + 1)$$\n",
    "\n",
    "Ahora, con ello ya podemos calcular $S(x)$ lo cual nos permitirá resolver nuestro problema original. \n",
    "\n",
    "Con ello solo quedaría implementar lo anteriormente descrito ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "    #include <bits/stdc++.h>\n",
    "     \n",
    "    using namespace std;\n",
    "     \n",
    "    typedef long long ll;\n",
    "     \n",
    "    ll s (ll num) { return num * (num + 1) / 2; }\n",
    "     \n",
    "    ll sum (ll num, ll power = 1, ll r = 0) {\n",
    "      if (num == 0) return 0;\n",
    "      int d = num % 10;\n",
    "      return (num / 10) * 45 * power + s(max(0, d - 1)) * power + d * (r + 1) + sum(num / 10, power * 10, r + d * power);\n",
    "    }\n",
    "     \n",
    "    int main () {\n",
    "      int a, b;\n",
    "      while (cin >> a >> b, a != -1 and b != -1) cout << sum(b) - sum(max(0, a - 1)) << endl;\n",
    "      return (0);\n",
    "    }\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. [Fractal](http://poj.org/problem?id=2083)\n",
    "\n",
    "```c++\n",
    "#include <iostream>\n",
    "#include <vector>\n",
    "#include <string>\n",
    "#include <cmath>\n",
    "\n",
    "using namespace std;\n",
    "\n",
    "vector <string> grid;\n",
    "int DR[] = {-1, -1, 1, 1, 0};\n",
    "int DC[] = {1, -1, 1, -1, 0};\n",
    "\n",
    "void print () {\n",
    "  for (int i = 0; i < grid.size(); i++) {\n",
    "    string& row = grid[i];\n",
    "    int j = row.size() - 1;\n",
    "    while (row[j] == ' ') row.erase(row.begin() + j);\n",
    "    cout << row << endl;\n",
    "  }\n",
    "  cout << '-' << endl;\n",
    "}\n",
    "\n",
    "void rec (int r, int c, int step) {\n",
    "  if (step == 0) {\n",
    "    grid[r][c] = 'X';\n",
    "    return;\n",
    "  }\n",
    "  for (int d = 0; d < 5; d++) {\n",
    "    rec(r + DR[d] * step, c + DC[d] * step, step / 3);\n",
    "  }\n",
    "}\n",
    "\n",
    "int main () {\n",
    "  int n;\n",
    "  while (cin >> n, n != -1) {\n",
    "    int gridSize = int(pow(3, n - 1));\n",
    "    grid = vector <string> (gridSize, string(gridSize, ' '));\n",
    "    int initial = (n == 1) ? 0 : gridSize / 3 + gridSize / 6; \n",
    "    int step = gridSize / 3;\n",
    "    rec(initial, initial, step);\n",
    "    print();\n",
    "  }\n",
    "  return (0);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [Contest time](https://vjudge.net/contest/282201)"
   ]
  }
 ],
 "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
}