09-Programacao_Dinamica.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Programação Dinamica\n",
    "\n",
    "É básicamente uma técnica que torna possível resolver problemas que podem ser rescritos como combinação de problemas \"menores\". Como vocês vão ver, programação dinâmica em si é bem simples, o desafio mesmo é conseguir observar problemas como PDs.\n",
    "\n",
    "#### Exemplo 1: Fibonacci\n",
    "\n",
    "O problema de se determinar o $n$-ésimo número de fibonacci pode ser descrito em função de problemas menores, seja $F(n)$ a função que retorna o $n$-ésimo número de fibonacci, temos:\n",
    "\n",
    "$$\n",
    "\\begin{align*}\n",
    "F(n)=F(n-1)+F(n-2)\\\\\n",
    "F(1)=F(0)=1\n",
    "\\end{align*}\n",
    "$$\n",
    "\n",
    "Nesse caso a relação \"menor\" é literalmente a relação $<$ entre dois números. Isso nem sempre acontece, o que importa mesmo é que não haja ciclos, isso vai ficar claro mais adiante. Outra requisito importante é que sejam definidos casos base para a recorrência. Não haver ciclos e possuir caso base são condições suficientes para que uma recursão pare eventualmente (ou seja, para que uma recursão defina um algoritmo).\n",
    "\n",
    "A partir de uma recorrência podemos definir um grafo:\n",
    "\n",
    "![](fibn.png)\n",
    "\n",
    "As arestas desse grafo são chamadas de transições e os vértices são os estados. Geralmente nos referimos a eles como estados e transições de uma PD.\n",
    "\n",
    "A partir dessa recorrência também podemos implementar uma função que computa o $n$-ésimo fibonacci:\n",
    "\n",
    "```c\n",
    "int fib(int n) {\n",
    "    if (n<1)\n",
    "        return 1;\n",
    "   \n",
    "    return fib(n-1) + fib(n-2);\n",
    "}\n",
    "```\n",
    "\n",
    "Fica como exercício mostrar a complexidade desse algoritmo é de $O(F(n))=O(2^n)$ (existem bounds melhores para $F(n)$). \n",
    "\n",
    "## Memoização\n",
    "\n",
    "Sim, está certo, não é memorização, é memoização mesmo!\n",
    "\n",
    "O código que implementamos para calcular o fibonacci não é muito esperto. Simule ele para o exemplo da figura do grafo e veja que alguns estados são visitados MUITAS vezes. Isso pode ser melhorado se guardarmos a resposta de um estado uma vez que ele é computado.\n",
    "\n",
    "Quando fazemos um DFS em um grafo, nunca visitamos um vertice mais de uma vez, simplismente usamos o valor calculado anteriormente.\n",
    "Memoização é isso, armazenamos o valor de um estado e nunca o visitamos de novo. A implementação fica assim:\n",
    "\n",
    "```c++\n",
    "int dp[100];\n",
    "bool vis[100]; // Inicialmente é tudo false.\n",
    "\n",
    "int fib(int n){\n",
    "    if (n<1) return 1;\n",
    "    if (vis[n]) return dp[n];\n",
    "    vis[n]=true;\n",
    "    return dp[n]=f(n-1)+f(n-2);\n",
    "}\n",
    "```\n",
    "\n",
    "A complexidade fica sendo a complexidade de uma DFS no grafo da PD: \n",
    "\n",
    "$O(|Estados| + |Transicoes|)$. Para o caso do fibonacci temos $O(n + 2n) = O(n)$.\n",
    "\n",
    "Este jeito de se resolver uma PD é conhecido como top-down.\n",
    "\n",
    "## Bottom-up\n",
    "\n",
    "Uma outra maneira de se resolver uma PD é começando pelos casos base e iterando para os casos maiores. Essa maneira é conhecida como bottom-up ou iterativa.\n",
    "Não existe apenas um jeito de se implementar uma PD iterativa, pessoalmente eu gosto de deixá-la bem parecida com a recorrência e setar separadamente os casos base:\n",
    "\n",
    "```c++\n",
    "int dp[100];\n",
    "dp[0]=dp[1]=1;\n",
    "\n",
    "for (int i=2; i<=n; ++i)\n",
    "  dp[i]=dp[i-1]+dp[i-2];  \n",
    "```\n",
    "\n",
    "Uma dificuldade de se utilizar bottom-up é encontrar uma ordem correta para computar os estados, ou seja, como fazer o **for**. Para o fibonacci isso é bem simples.\n",
    "\n",
    "É importante saber fazer bottom-up, algumas técnicas mais avançadas de otimização de PD só podem ser aplicadas utilizando bottom-up."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mais exemplos\n",
    "\n",
    "Para ficar bom em resolver problemas de PD só tem um jeito: resolver MUITOS problemas de PD. Existem muitos tipos de problemas diferentes e é essencial saber, todo round do codeforces tem um quase.\n",
    "\n",
    "Aqui vou mostrar os exemplos mais clássicos.\n",
    "\n",
    "### Exemplo 2: Coin change\n",
    "\n",
    "[coin1]: https://www.hackerrank.com/challenges/coin-change/problem\n",
    "[knap1]: https://codeforces.com/contest/19/problem/B\n",
    "[knap2]: https://codeforces.com/problemset/problem/543/A\n",
    "[coin2]: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1254\n",
    "\n",
    "Dado um conjunto $C=\\{c_1,\\dots,c_k\\}$ de moedas, deseja-se saber qual é o número mínimo de moedas para dar um troco de valor $X$. É permitido utilizar cada moeda uma única vez.\n",
    "\n",
    "Se você quiser tentar resolver problemas como este antes de continuar: [P1][coin1], [P2][knap1], [P3][coin2].\n",
    "\n",
    "O primeiro passo é observar que o algoritmo guloso do troco a seguir nem sempre funciona (tente criar um caso que isso ocorre):\n",
    "- Adiciona ao troco a moeda com maior valor menor do que $X$,\n",
    "- Atualize o valor de $X$ e repita se $X>0$.\n",
    "\n",
    "Quase sempre, a melhor maneira de se enchergar uma solução para um problema que você suspeita que seja PD é pensar em um brute-force que verifica todas as possíveis combinações. Para o coin change vamos definir a função $f(i, x)$ como sendo o troco mínimo para o valor $x$ utilizando as moedas $\\{c_i, \\dots, c_n\\}$. \n",
    "\n",
    "Para fazer um brute-force, testamos todas opções chamando a mesma função alterando seus parâmetros. Aqui, todas as opções para $f(i, x)$ são:\n",
    "- Utilizar a $i$-ésima moeda e chamar $f(i+1, x-c_i)$,\n",
    "- Não utilizar a $i$-ésima moeda e chamar $f(i+1, x)$.\n",
    "\n",
    "O caso base acontece quando $i=n+1$, pois já tomamos todas as decisões de usar ou não cada moeda. Portanto, existem dois senários:\n",
    "- Retornamos $\\infty$ se $x>0$, já que a solução não é um troco do valor desejado (o valor infito é utilizado para indicar que a solução não é válida),\n",
    "- Retornamos $0$ se $x=0$\n",
    "\n",
    "Veja como fica a recorrência:\n",
    "\n",
    "> case não-base:\n",
    "$$\n",
    "\\begin{align*}\n",
    "f(i, x) = \\left\\{\\begin{array}{cc}\n",
    "\\min \\{f(i+1, x-c_i)+1, f(i+1, x)\\} & c_i \\le x\\\\\n",
    "f(i+1, x) & c_i > x\n",
    "\\end{array}\\right.\n",
    "\\end{align*}\n",
    "$$\n",
    "\n",
    "> caso base:\n",
    "$$\n",
    "\\begin{align*}\n",
    "f(n+1,x) = \\left\\{\\begin{array}{cc}\n",
    "0 & x=0\\\\ \n",
    "\\infty & x>0\n",
    "\\end{array}\\right.\n",
    "\\end{align*}\n",
    "$$\n",
    "\n",
    "##### Implementação\n",
    "\n",
    "```c++\n",
    "int dp[100][5000]; //inicialize com -1 para indicar que nao foi visitado\n",
    "int c[100]; // conjunto de moedas, valor de cada moeda é menor do que 50\n",
    "const int INF=0x3f3f3f3f;//número grande que ainda pode ser somado a ele mesmo sem overflow\n",
    "\n",
    "int f(int i, int x) {\n",
    "    if (i==n)\n",
    "        return (x==0) ? 0 : INF;\n",
    "    if (x < c[i]) return dp[i][x] = f(i+1, x);\n",
    "    return dp[i][x] = min(f(i+1, x), f(i+1, x-c[i])+1);\n",
    "}\n",
    "```\n",
    "Veja que a complexidade é $O(|C| \\times K)$ em que $K$ é o valor máximo do troco.\n",
    "\n",
    "##### Exercícios:\n",
    "\n",
    "- Caso em que cada moeda pode ser usada mais de uma vez\n",
    "- Implementação bottom-up\n",
    "- Substituir o estado que representa o índice da moeda por um **for** (quando cada moeda pode ser usada mais de uma vez)\n",
    "- Contar quantas soluções ótimas existem\n",
    "\n",
    "#### Memória\n",
    "\n",
    "É hora de começar a se preocupar com memória. No codeforces, por exemplo, conseguimos executar $~10^8$ operações em $1s$. No entanto, armazenar um vetor de $10^8$ inteiros requer aproximadamente 500mb, se vc tentar fazer isso, provavelmente vai tomar MLE.\n",
    "\n",
    "No problema da moedas se $|C|=100$ e $K=10^6$ poderíamos fazer um trick na implementação bottom-up do problema para não precisar reservar 10^8 de memória. Veja:\n",
    "\n",
    "```c++\n",
    "dp[2][1000001];\n",
    "dp[1][0]=0;\n",
    "K=1000000;\n",
    "for(int i = 1; i<=K; i++) dp[1][K]=INF;\n",
    "\n",
    "int cur = 0, prv=1;\n",
    "for(int i = 0; i<k; i++)//k é o número de moedas\n",
    "{\n",
    "    dp[cur][0]=0;\n",
    "    for (int j = 1; j<=c[k];j--){//c[k] é a k-esima moeda\n",
    "        dp[cur][j]=INF;\n",
    "        dp[cur][j]=min(dp[cur][j], dp[prv][j-c[k]]+1);\n",
    "    }\n",
    "    \n",
    "    swap(cur,prv);\n",
    "}\n",
    "\n",
    "cout << dp[prv][X] << endl;\n",
    "```\n",
    "\n",
    "Para entender o trick de memória, primeiro implemente a versão bottom-up que não precisa economizar memória. Você vai perceper que a linha $i$ da sua matriz só precisa da linha $i-1$ para calcular seu valor, logo só precisamos das últimas duas linhas na dp.\n",
    "\n",
    "Problema em que precisa economizar memória: [PMem][knap2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Longest Common Subsequence (LCS)\n",
    "[lcs1]: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1346\n",
    "[lcs2]: https://www.hackerrank.com/challenges/dynamic-programming-classics-the-longest-common-subsequence/problem\n",
    "\n",
    "Sejam $A=\\{a_1, \\dots, a_n\\}$ e $B=\\{b_1, \\dots, b_n\\}$ duas strings, queremos saber qual é a subsequencia mais longa em comum nas duas. Uma subsequência é formada a partir de uma sequencia eliminando alguns elementos e mantendo sua ordem, por exemplo $axy$ é uma subsequência de $zabxccyk$.\n",
    "\n",
    "Problemas de LCS: [P1][lcs1], [P2][lcs2]\n",
    "\n",
    "O LCS pode ser visto como o problema de minimizar o número de caracteres removidos de duas strings dadas para que elas se tornem iguais. Exemplo:\n",
    "\n",
    "\\begin{align}\n",
    "A=abcabcabd\\\\\n",
    "B=axcxxcyby\n",
    "\\end{align}\n",
    "\n",
    "A maior subsequencia comum entre $A$ e $B$ é $accb$. Note que, esse exemplo pode te levar a achar que existe uma solução gulosa em que você adiciona na resposta se os caracteres são iguais e ignora se são diferentes começando do primeiro. Como exercício, tente criar um caso que isso falha.\n",
    "\n",
    "\n",
    "Uma ideia para resolver o LCS é pensar na função $f(i,j)$ que retorna o LCS entre as strings $\\{a_i, \\dots, a_n\\}$ e $\\{b_j, \\dots, b_n\\}$. Tente criar a recorrencia antes de continuar. *Obs: $\\wedge$ é o operador lógico and, $\\vee$ é o operador lógico or*.\n",
    "\n",
    "$$\n",
    "\\begin{align*}\n",
    "f(i,j) = \\left\\{\\begin{array}{cc}\n",
    "\\max\\{f(i+1,j), f(i,j+1), f(i+1,j+1)+1\\} & i\\le n \\wedge j \\le n \\wedge a_i=b_j\\\\\n",
    "\\max\\{f(i+1,j), f(i,j+1)\\} & i\\le n \\wedge j \\le n \\wedge a_i \\neq b_j\\\\\n",
    "0 & i > n \\vee j>n\n",
    "\\end{array}\\right.\\\\\n",
    "\\end{align*}\n",
    "$$\n",
    "\n",
    "#### Entendendo a recorrência\n",
    "Veja que a recorrência está tentando fazer com que as duas strings fiquem identicas removendo alguns caracteres. Como temos muitas maneiras de fazer isso, a recorrência tenta todas opções, é como se ela fizesse um brute-force e retornasse a melhor resposta encontrada. Programação dinâmica pode ser vista dessa maneira, uma otimização de brute-force. Separando os casos da recorrência temos:\n",
    "\n",
    "- O primeiro caso é quando os caractéres são iguais, temos três opções:\n",
    "    - Remover o caractere da primeira string, isso corresponde ao subproblema $f(i+1,j)$.\n",
    "    - Remover o caractere da segunda string obtendo o subproblema $f(i,j+1)$.\n",
    "    - Adicionar o caractere da resposta (por isso somamos $1$), com isso obtemos o subproblema $f(i+1, j+1)$.\n",
    "- O segundo caso é igual ao primeiro, porém não podemos adicionar nada na resposta pois os caracteres não são iguais\n",
    "- O tereceiro caso é o caso base quando uma das strings já foi inteiramente \"apagada\".\n",
    "\n",
    "#### Implementação\n",
    "\n",
    "Para $n<1000$ o código top-down a seguir funciona bem:\n",
    "\n",
    "```c++\n",
    "int dp[1001][1001]; //inicia com -1 para indicar não visitado.\n",
    "string a, b;\n",
    "\n",
    "// 0-based\n",
    "int f(int i, int j) {\n",
    "    if (i==n || j==n) return 0;\n",
    "    if (dp[i][j]!=-1) return dp[i][j];\n",
    "    \n",
    "    int ret = max(f(i+1,j),f(i,j+1));\n",
    "    if (a[i]==b[j]) ret = max(ret, f(i+1,j+1)+1);\n",
    "    return dp[i][j]=ret;\n",
    "}\n",
    "```\n",
    "\n",
    "O LCS é um bom exemplo no qual não é tão direto fazer a implementação bottom-up. Veja a seguir o grafo da recursão para uma instância com strings de tamanho $3$:\n",
    "\n",
    "![](lcs.png)\n",
    "\n",
    "Lembre que para fazer bottom-up precisamos encontrar uma ordem para computar os estados. Observando o grafo é possível identificar essa ordem: depois de setar os casos base, computamos primeiro o elemento $(n-1, n-1)$, depois $(n-2, n-1)$, $(n-1, n-2)$, depois o $(n-3, n-1), (n-1, n-3)$, até o $(0, n-1)$ e $(n-1, 0)$; ou seja computamos em ordem os elementos que estão fixados com a linha ou a coluna no $n-1$. Depois computamos os elementos com linha ou coluna no $n-2$, depois todos os estados com linha ou coluna no $n-3$, ..., até o $(0,0)$. A implementação fica assim:\n",
    "\n",
    "```c++\n",
    "for (int i = 0; i<=n; i++) dp[i][n]=dp[n][i]=0; //caso base\n",
    "\n",
    "\n",
    "for (int k=n-1; k>=0; --k)\n",
    "    for (int i = k; i>=0; --i){\n",
    "        // coluna fixa\n",
    "        dp[i][k]=max(dp[i+1][k], dp[i][k+1]);\n",
    "        if (a[i]==b[k]) \n",
    "            dp[i][k]=max(dp[i][k], dp[i+1][k+1]+1);\n",
    "        \n",
    "        // linha fixa\n",
    "        dp[k][i]=max(dp[k+1][i], dp[k][i+1]);\n",
    "        if (a[k]==b[i])\n",
    "            dp[k][i]=max(dp[k][i], dp[k+1][i+1]+1);\n",
    "            \n",
    "    }\n",
    "```\n",
    "\n",
    "Veja que ainda não é possível economizar memória, isso fica de exercício :)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Directed Acyclic Graph (DAG)\n",
    "\n",
    "Todo grafo de uma PD é direcionado e sem ciclos (DAG). Isso nos permite resolver varios problemas, quando sabemos que o grafo em questão é um DAG, em $O(|E|)$, $E$ é o conjunto de arestas. \n",
    "\n",
    "Por exemplo: encontrar o menor caminho de todos os vértices para um vértice *source* utilizando Dijkstra tem complexidade $O(|E|\\lg{n})$, utilizando PD isso pode ser feito em $O(|E|)$, ou seja, um pouquinho melhor.\n",
    "\n",
    "Outro exemplo: econtrar o maior caminho simples (um caminho sem repetições) em um grafo geral é NP-Hard (não há algoritmo polinomial a não ser que P=NP). No entanto, se o grafo é um DAG o problema pode ser resolvido em $O(|V|\\times|E|)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Reconstruindo uma resposta para problemas de otimização\n",
    "[pr1]: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=931\n",
    "[pr2]: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2399\n",
    "\n",
    "Problemas de otimização geralmente pedem que você simplesmente imprima o valor máximo ou o mínimo de algo. Porém, em contests mais estilo ICPC você pode se deparar com um problema que pede para você reconstruir uma solução ótima. Isso pode ser feito facilmente percorrendo um caminho ótimo no grafo da DP. Veja o código para o LCS:\n",
    "\n",
    "```c++\n",
    "int dp[100][100];//assumindo q a PD já foi computada e dp[i][j] tem o valor do maior LCS entre a[i..n-1], b[j..n-1]\n",
    "string a, b, ans;\n",
    "\n",
    "int i=0, j=0;\n",
    "while(i<n && j<n) {\n",
    "    if (dp[i][j] == dp[i+1][j]) //verifica se essa transição é ótima\n",
    "        i = i+1;\n",
    "    else if (dp[i][j] == dp[i][j+1])\n",
    "        j = j+1;\n",
    "    else{\n",
    "        ans.push_back(a[i]);\n",
    "        ++i;\n",
    "        ++j;\n",
    "    }       \n",
    "}\n",
    "\n",
    "cout << ans << endl;\n",
    "```\n",
    "\n",
    "Outra maneira de reconstruir uma solução é armazenar a melhor transição quando a PD está sendo calculada.\n",
    "\n",
    "Problema para praticar: [P1][pr1], [P2][pr2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## PD nos dígitos\n",
    "\n",
    "Outra PD muito comum é a chamada PD nos dígitos. Nesse tipo de problema geralmente queremos contar quantos números satisfazem uma certa propriedade e o estado da PD é definido como o índice do número que está sendo construído.\n",
    "\n",
    "Exemplo: Quantos números $x$ entre $L$ e $R$, $(L,R < 10^{18})$ existem, tal que o primeiro digito (não zero) de $x$ é igual ao último.\n",
    "\n",
    "- O primeiro passo é perceber que podemos resolver o problema de quantos números com essa propriedade existem menores ou igual a $M$.\n",
    "\n",
    "- Um dos estados será o indice, ou quantos digitos já foram atribuidos ao número $x$ (mais a esquerda).\n",
    "- Outro estado dirá se $x$ atualmente é menor ou se ele é exatamente igual a $R$.\n",
    "    -- Se $x$ é menor do que $R$ qualquer digito pode ser atribuído.\n",
    "    -- Senão podemos atribuir um digito menor e mudar para um estado em que $x$ já é menor do que $R$, ou permanecer no estado em que $x$ é igual a $R$.\n",
    "- O terceiro estado nos dirá qual é o primeiro digito não-zero que foi utilizado, ele será usado no caso base.\n",
    "    \n",
    "O código top-down fica assim:\n",
    "```c++\n",
    "int K = 200;//o numero tem no maximo 200 digitos\n",
    "int R[K]; //numero R (0s a esquerda)\n",
    "long long dp[K][2][10];\n",
    "const int MOD = 1000 * 1000 * 1000 + 7;\n",
    "\n",
    "long long f(int i, bool eq, int fd) {\n",
    "    if (i==K-1) {\n",
    "        if (eq) return fd <= R[i];\n",
    "        return 1;\n",
    "    }\n",
    "    \n",
    "    if (dp[i][eq][fd] != -1) return dp[i][eq][df];\n",
    "    \n",
    "    ret = 0;\n",
    "    \n",
    "    if (eq) {\n",
    "        ret = f(i+1, 1, (fd==0)?R[i]:fd);\n",
    "        for (int k = 0; k < R[i]; ++k)\n",
    "            ret = (ret + f(i+1, 0, (fd==0)?k:fd))%MOD;\n",
    "    }\n",
    "    else {\n",
    "        for (int k = 0; k<10; k++)\n",
    "            ret = (ret + f(i+1, 0, (fd==0)?k:fd))%MOD;\n",
    "    }\n",
    "    \n",
    "    return dp[i][eq][fd]=ret;\n",
    "}\n",
    "\n",
    "// Isso imprime todos os números que satisfazem a propriedade e são menores ou igual a R.\n",
    "// Para obter a resposta para o intervalo [L,R] basta fazer a mesma coisa setando R = L-1 e então subtrair da resposta.\n",
    "cout << f(0, 1, 0) << endl;\n",
    "\n",
    "```\n",
    "\n",
    "Problemas para praticar: [P1][pdig1], [P2][pdig2], [P3][pdig3].\n",
    "\n",
    "[pdig1]: http://codeforces.com/contest/55/problem/D\n",
    "[pdig2]: https://www.hackerrank.com/challenges/prime-digit-sums/problem\n",
    "[pdig3]: http://codeforces.com/contest/628/problem/D"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mais Coisas\n",
    "\n",
    "[Tutorial topcoder](https://www.topcoder.com/community/competitive-programming/tutorials/dynamic-programming-from-novice-to-advanced/)\n",
    "\n",
    "[Capítulo de um livro](https://www.ics.uci.edu/~goodrich/teach/cs161/notes/dynamicp.pdf)\n",
    "\n",
    "[Tutorial bem detalhado](https://www.freecodecamp.org/news/demystifying-dynamic-programming-3efafb8d4296/)\n",
    "\n",
    "[Lista de problemas](https://www.hackerrank.com/domains/algorithms?filters%5Bsubdomains%5D%5B%5D=dynamic-programming)\n",
    "\n",
    "[DPs no CF ordenado por dificuldade](http://codeforces.com/problemset?order=BY_RATING_ASC&tags=dp)\n",
    "\n",
    "[Outro tutorial](https://activities.tjhsst.edu/sct/lectures/1718/2017-10-20_Introduction_to_Dynamic_Programming.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### PS: \n",
    "- Isso é só o começo, resolvam problemas e façam CF, programação dinâmica é muito mais pratica do que teoria.\n",
    "- Não confiem nos códigos que eu coloquei aqui, eles são só um sketch, eu não passei os problemas com eles.\n",
    "- Deve ter muitos erros, feel free para colaborar, só pedir que eu te dou permissão no github ou manda um pull request."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}