D_Yarema_Taras-Laboratori_7.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "xHTT4DF3s0pz"
   },
   "source": [
    "# <span class=\"tema\">(Ordenar i cerca)</span> Sumatori parcial màxim"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "x4qcsKZHs0p1"
   },
   "source": [
    "Donada una llista d’enters, trobar el sumatori parcial d'elements consecutius de valor màxim. \n",
    "\n",
    "Si el valor màxim és negatiu, el sumatori parcial màxim donarà 0\n",
    "\n",
    "Indicacions:\n",
    "+ Aquest algorisme es pot implementar de tres maneres. \n",
    "    + Força bruta $(O(n*n))$\n",
    "    + Dividir i conquerir $(O(n log n))$\n",
    "    + Algorisme de Kadane $(O(n))$\n",
    "\n",
    "L'Algorisme Kadane consisteix en fer un únic recorregut per la llista, i anar acumulant el valor de la suma, amb la particularitat que si el que portem acumulat és negatiu, ho descartem.\n",
    "\n",
    "Per exemple, a la llista [-1,0,3,4,-2,5]   aniriem acumulant -1 => és negatiu, descartem; 0, 3, 7, 5, 10\n",
    "\n",
    "per no perdre màxims locals hem de mantenir dos valors: el valor acumulat fins a un punt i el valor màxim. A l'exemple:\n",
    "\n",
    "- **[-1**, 0, 3, 4, -2, 5] acum:-1=>0, maxim:0;  \n",
    "- **[-1, 0**, 3, 4, -2, 5] acum=0, màxim:0; \n",
    "- **[-1, 0, 3**, 4, -2, 5] acum:3, màxim:3; \n",
    "- **[-1, 0, 3, 4**, -2, 5] acum:7, màxim:7; \n",
    "- **[-1, 0, 3, 4, -2**, 5] acum:5, màxim:7; \n",
    "- **[-1, 0, 3, 4, -2, 5**] acum:10, màxim:10"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "EZM1yNFss0p2"
   },
   "source": [
    "### Conceptualització problema\n",
    "\n",
    "#### Implementa les tres versions de la solució\n",
    "    \n",
    "**Fet** a la cel·la següent.\n",
    "    \n",
    "#### Calcula el cost de cadascuna\n",
    "Suposem que $n$ denota la llargada de la llista.\n",
    "\n",
    "- **Brute force**: Es recorre la un cop llista. En cada pas es torna a recorre la llista, fent operacions $O(1)$. Per tant, la complexitat total és $O(n^2)$.\n",
    "- **Divide and conquer**: A partir dels [Master Theorem](https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)), tenim que $T(n) = 2 \\cdot T(\\frac{n}{2}) + O(n)$, ja que dividim la llista en dos en cada pas recursiu. D'aquí es pot extreure que la complexitat final és $O(n \\log (n))$.\n",
    "- **Kadane**: $O(n)$, ja que només es recorre la llista un cop, fent operacion $O(1)$ en cada pas."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementació"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "l2AlB6ahs0p6"
   },
   "outputs": [],
   "source": [
    "def sumatoriParcialMaximBrute(llista: list) -> int:\n",
    "    max_acc, arr_len = 0, len(llista)\n",
    "    \n",
    "    # We iterate over all the possible subarrays\n",
    "    \n",
    "    for i in range(arr_len):\n",
    "        for j in range(i+1, arr_len+1):\n",
    "            \n",
    "            # Compute the sum of the substring\n",
    "            # and update the max\n",
    "            \n",
    "            tmp_acc = sum(llista[i:j])\n",
    "            \n",
    "            if tmp_acc > max_acc:\n",
    "                max_acc = tmp_acc\n",
    "    \n",
    "    return max_acc\n",
    "\n",
    "def sumatoriParcialMaximDivide(llista: list) -> int:\n",
    "    \n",
    "    # Base cases\n",
    "    # If array contains only one element\n",
    "    \n",
    "    if len(llista) == 0:\n",
    "        return 0\n",
    "    \n",
    "    if len(llista) == 1:\n",
    "        return llista[0] if llista[0] > 0 else 0\n",
    "\n",
    "    # Find the middle element of the array\n",
    "    \n",
    "    mid = len(llista) // 2\n",
    "\n",
    "    # Find the max. subarray sum \n",
    "    # for the left subarray\n",
    "    \n",
    "    acc_left, max_left = 0, -1e+9\n",
    "    \n",
    "    for n in reversed(llista[:mid]): \n",
    "        acc_left += n\n",
    "        \n",
    "        if acc_left > max_left:\n",
    "            max_left = acc_left\n",
    "\n",
    "    # Find maximum subarray sum \n",
    "    # for the right subarray\n",
    "    \n",
    "    acc_right, max_right = 0, -1e+9\n",
    "    \n",
    "    for n in llista[mid:]: \n",
    "        acc_right += n\n",
    "        \n",
    "        if acc_right > max_right:\n",
    "            max_right = acc_right\n",
    "\n",
    "\n",
    "    # Recurssion step\n",
    "    \n",
    "    max_lr = max(\n",
    "        sumatoriParcialMaximDivide(llista[:mid]), \n",
    "        sumatoriParcialMaximDivide(llista[mid:]))\n",
    "    \n",
    "    # Return de max from the sides \n",
    "    # and middle segments\n",
    "    \n",
    "    max_acc = max(max_lr, max_left + max_right)\n",
    "    return max_acc if max_acc > 0 else 0\n",
    "        \n",
    "def sumatoriParcialMaxim(llista: list) -> int:\n",
    "    acc, max_acc = 0, 0\n",
    "    \n",
    "    for n in llista:\n",
    "        # Add the actual element\n",
    "        \n",
    "        acc += n\n",
    "        \n",
    "        # If the partial sum is negative,\n",
    "        # we reset it\n",
    "        \n",
    "        if acc < 0:\n",
    "            acc = 0\n",
    "        \n",
    "        # Update the max sum value\n",
    "        \n",
    "        if acc > max_acc:\n",
    "            max_acc = acc\n",
    "    \n",
    "    return max_acc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "sumatoriParcialMaxim([-3, 1, -5, 2, 7, 8]) = 17\n"
     ]
    }
   ],
   "source": [
    "def prettySumatoriParcialMaxim(llista: list) -> None:\n",
    "    max_sum = sumatoriParcialMaxim(llista)\n",
    "    print(f\"sumatoriParcialMaxim({llista}) = {max_sum}\")\n",
    "    \n",
    "prettySumatoriParcialMaxim([-3, 1, -5, 2, 7, 8])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Testeig\n",
    "\n",
    "#### Exemple\n",
    "```python\n",
    "sumatoriParcialMaxim([-3, 1, -5, 2, 7, 8]) # ha de retornar 17\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tests cases #1: Known results\n",
      "Ran 2 tests ... OK\n",
      "\n",
      "Tests cases #2: Random\n",
      "Ran 200 tests ... OK\n"
     ]
    }
   ],
   "source": [
    "from random import randint\n",
    "\n",
    "test_arr, arr_res     = [-3, 1, -5, 2, 7, 8], 17\n",
    "test_arr_2, arr_res_2 = [-1, 0, 3, 4, -2, 5], 10\n",
    "\n",
    "# Test for known results\n",
    "\n",
    "print(\"Tests cases #1: Known results\")\n",
    "assert sumatoriParcialMaxim(test_arr) == arr_res\n",
    "assert sumatoriParcialMaxim(test_arr_2) == arr_res_2\n",
    "print(\"Ran 2 tests ... OK\\n\")\n",
    "\n",
    "\n",
    "# Test that the three functions have the same outputs\n",
    "\n",
    "TEST_CASES = 100\n",
    "print(\"Tests cases #2: Random\")\n",
    "\n",
    "for i in range(TEST_CASES):\n",
    "    \n",
    "    # Generate random array of ints\n",
    "    # and get the target max value based on\n",
    "    # the Kadane algorithm\n",
    "    \n",
    "    arr = [randint(-1e+3, 1e+3) for _ in range(0, randint(1, 1e+2))]\n",
    "    target = sumatoriParcialMaxim(arr)\n",
    "        \n",
    "    # Test the results are equal for all\n",
    "    # the functions\n",
    "        \n",
    "    assert target == sumatoriParcialMaximBrute(arr)\n",
    "    assert target == sumatoriParcialMaximDivide(arr)\n",
    "        \n",
    "print(f\"Ran {2*TEST_CASES} tests ... OK\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Benchmark & performance\n",
    "\n",
    "Utilitzaré la llibreria `matplotlib` per veure com creix el temps d'execució usant els tres algoritmes implementats."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "              total (s)\tmean (s)\n",
      "Brute force   4.998596\t0.016662\n",
      "Divide & con. 0.112085\t0.000374\n",
      "Kadane        0.004815\t0.000016\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYgAAAEGCAYAAAB/+QKOAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nOzdeXxU5b348c93ZrKvkIR9CciasBNAXHBBAasVvGpdetW2Wmvrdmtba29bS622tVdvf3W512srrba2Ym1VVCzWKuKCSFCQXRGQJASy75n9+f1xzkwme4BMFvJ9v1555cw5z5nznMlkvvPsYoxBKaWUasnR2xlQSinVN2mAUEop1SYNEEoppdqkAUIppVSbNEAopZRqk6u3M9BdMjMzTXZ2dm9nQyml+pUtW7aUGWOy2jp20gSI7Oxs8vPzezsbSinVr4jI5+0di2oVk4gsE5G9IrJPRO5q43iciKy2j28SkWx7/5dFZGvET1BEZkUzr0oppZqLWoAQESfwKHABkANcJSI5LZJdD1QaYyYAvwbuBzDGPG2MmWWMmQVcAxwwxmyNVl6VUkq1Fs0SxHxgnzFmvzHGCzwDLG+RZjnwpL39HLBYRKRFmqvsc5VSSvWgaLZBjAQKIh4XAgvaS2OM8YtINZABlEWkuYLWgQUAEbkRuBFgzJgxrY77fD4KCwtxu93HeQvqZBMfH8+oUaOIiYnp7awo1ef16UZqEVkANBhjdrR13BjzOPA4QF5eXqtJpQoLC0lJSSE7O5vWBRM10BhjKC8vp7CwkHHjxvV2dpTq86JZxVQEjI54PMre12YaEXEBaUB5xPErgb8cbwbcbjcZGRkaHBQAIkJGRoaWKJXqomgGiM3ARBEZJyKxWB/2a1qkWQNcZ29fBrxh7OllRcQBfIkTbH/Q4KAi6ftBqa6LWoAwxviBW4B1wG7gWWPMThG5R0QutpM9AWSIyD7gDiCyK+wioMAYsz9aeVRKqb7u9V1HOVLdO6XeqI6DMMasNcZMMsacYoy5z953tzFmjb3tNsZcboyZYIyZHxkMjDHrjTGnRjN/PcHpdDJr1ixmzpzJnDlzeO+99475Of7whz9w+PDhYzqntLSUBQsWMHv2bN5+++1jvqZSqvcZY7jpT1v486Z2x7JFlc7FFGUJCQls3bqVbdu28Ytf/IIf/OAHrdL4/f4On+N4AsS//vUvpk+fzkcffcSZZ57ZpXMCgcAxXUMpFV3+oMEfNDT6eud/UwNED6qpqWHQoEEArF+/njPPPJOLL76YnJwcDh48yLRp08JpH3jgAVauXMlzzz1Hfn4+X/7yl5k1axaNjY1s2bKFs846i7lz57J06VKKi4ubXWfr1q3ceeedvPjii+Fz/vKXvzB9+nSmTZvG97///XDa5ORkvvOd7zBz5kw2btzI5s2bOe2005g5cybz58+ntraWQCDA9773PebNm8eMGTP4v//7v555wZQa4HyBIAAefzC874fPb+flj4/tC+Px6tPdXLvTT1/aya7DNd36nDkjUvnJF3M7TNPY2MisWbNwu90UFxfzxhtvhI99+OGH7Nixg3HjxnHw4ME2z7/ssst45JFHeOCBB8jLy8Pn83Hrrbfy4osvkpWVxerVq/nhD3/IqlWrwufMmjWLe+65h/z8fB555BEOHz7M97//fbZs2cKgQYNYsmQJL7zwAitWrKC+vp4FCxbw4IMP4vV6mTJlCqtXr2bevHnU1NSQkJDAE088QVpaGps3b8bj8XD66aezZMkS7SqqVJT5/FbvfY+vKUCs2XYYXyDIRTNGRP36AyZA9JZQFRPAxo0bufbaa9mxwxrWMX/+/GP+kN27dy87duzg/PPPB6xqoeHDh3d4zubNmzn77LPJyrImbPzyl7/Mhg0bWLFiBU6nk0svvTT83MOHD2fevHkApKamAvDaa6/x8ccf89xzzwFQXV3Np59+qgFCqSjz2iWI0G8Arz9IY0TAiKYBEyA6+6bfExYuXEhZWRmlpaUAJCUlhY+5XC6CwaY/ent99Y0x5ObmsnHjxm7JU3x8PE6ns8M0xhgefvhhli5d2i3XVEp1TVMVk9UGYYzBGwjS6O243bK7aBtED9qzZw+BQICMjIxWx4YOHUpJSQnl5eV4PB5efvnl8LGUlBRqa2sBmDx5MqWlpeEA4fP52LlzZ4fXnT9/Pm+99RZlZWUEAgH+8pe/cNZZZ7VKN3nyZIqLi9m8eTMAtbW1+P1+li5dyv/+7//i8/kA+OSTT6ivrz++F0Ep1WXhAGGXGHwBgzH0WKP1gClB9JZQGwRY0f/JJ59s8xt7TEwMd999N/Pnz2fkyJFMmTIlfOwrX/kKN910EwkJCWzcuJHnnnuO2267jerqavx+P//xH/9Bbm77JaThw4fzy1/+knPOOQdjDBdeeCHLl7ee3io2NpbVq1dz66230tjYSEJCAq+//jo33HADBw8eZM6cORhjyMrK4oUXXuiGV0cp1VJRVSNDUuKIcTrCAaJlVVOjt2cChNgDl/u9vLw803LBoN27dzN16tReypHqq/R9ofqqRm+A2T97jXsunsaX5o1m1+EavvDQ28zPHsyzNy2kot7LnJ/9kynDUvjHfyzqlmuKyBZjTF5bx7SKSSml+ogGrx+3L8jRGqsNMlzF1KItwt1DVUwaIJRSqo/wBawanXq7CskbboOwH9vjIRp6qIpJA4RSSvURvnAbg9VLyWcHBG+L3z3VSK0BQiml+ohQgGjwBth1uIaqRqvnYGgkdeh3TzVSay8mpZTqI0JVTNWNPlb8z7vMGZMOtA4Q/qDBFwgS44zud3wtQSilVB8RKkEcrXHj9QcpqfUATY3T3og5mXqiHUIDRJSFpvvOzc1l5syZPPjgg+ER0/n5+dx2220dnv/YY4/x1FNPtdrfcnK/npCcnNyj11NqoAk1SocCQ53baovw+pv3YoKe6cmkVUxRFjkXU0lJCVdffTU1NTX89Kc/JS8vj7y8Nrsfh9100009kc2Tlt/vx+XSt7nqH/x2FVOpHSBq7QDh8QetaTa0BHHyGjJkCI8//jiPPPIIxhjWr1/PRRddRDAYJDs7m6qqqnDaiRMncvToUVauXMkDDzwAwJYtW5g5cyYzZ87k0UcfDaft6nTcK1asYO7cueTm5vL444+H9ycnJ/PDH/6QmTNncuqpp3L06FEADhw4wMKFC5k+fTo/+tGP2r2vp556ihkzZjBz5kyuueYawCrhnHvuucyYMYPFixdz6NAhwBoVftttt3Haaacxfvz48ASAxhhuueUWJk+ezHnnnccXvvCF8LHs7GzKysoAq9R19tlnA1BfX8/XvvY15s+fz+zZs3nxxRcBa/2Miy++mHPPPZfFixd38a+jVO8LVTH5g1agiOyt5AuYZpP29URD9cD5avXqXXBke/c+57DpcMEvj+mU8ePHEwgEKCkpCe9zOBwsX76c559/nq9+9ats2rSJsWPHMnTo0GbnfvWrX+WRRx5h0aJFfO973wvv7+p03KtWrWLw4ME0NjYyb948Lr30UjIyMqivr+fUU0/lvvvu48477+S3v/0tP/rRj7j99tv55je/ybXXXtssIEXauXMn9957L++99x6ZmZlUVFQAcOutt3Lddddx3XXXsWrVKm677bbw9BzFxcW888477Nmzh4svvpjLLruM559/nr1797Jr1y6OHj1KTk4OX/va1zp8Le+77z7OPfdcVq1aRVVVFfPnz+e8884DrKnUP/74YwYPHtzFv4xSvS8yALTk8QeaTfvd6Iv+hH1agugjrrjiClavXg3AM888wxVXXNHseFVVFVVVVSxaZA2vD31TB2s67qeeeopZs2axYMECysvL+fTTT1td46GHHgqXEgoKCsJpYmNjueiiiwCYO3dueG2Kd999l6uuuqrV9SK98cYbXH755WRmZgKEP5A3btzI1VdfHT73nXfeCZ+zYsUKHA4HOTk54dLKhg0buOqqq3A6nYwYMYJzzz2309fstdde45e//CWzZs3i7LPPxu12h0sq559/vgYH1e+Eqpja4vEHW5Qgoj/l98ApQRzjN/1o2b9/P06nkyFDhrB79+7w/oULF7Jv3z5KS0t54YUXOqzSaakr03GvX7+e119/nY0bN5KYmBj+QAVrokARAaxG9cglUEP7u1NcXFyzvHcmcir0yGnQjTH87W9/Y/Lkyc3Sb9q0qdlU6kr1F74OShBef7BFG0Q/L0GIyDIR2Ssi+0TkrjaOx4nIavv4JhHJjjg2Q0Q2ishOEdkuIvHRzGtPKC0t5aabbuKWW25p9cErIlxyySXccccdTJ06tdWU4Onp6aSnp4e/iT/99NPhY12Zjru6uppBgwaRmJjInj17eP/99zvN7+mnn84zzzzT6nqRzj33XP76179SXl4OEK5iOu2005qd29m62IsWLWL16tUEAgGKi4t58803w8eys7PZsmULAH/729+a3ffDDz8cDjIfffRRp/ekVF/WUYDw+IPNejH1xGjqqAUIEXECjwIXADnAVSKS0yLZ9UClMWYC8GvgfvtcF/An4CZjTC5wNuCLVl6jKTTdd25uLueddx5LlizhJz/5SZtpr7jiCv70pz+1ql4K+f3vf8/NN9/MrFmzmn3zvuGGG8jJyWHOnDlMmzaNb3zjG81KAQDLli3D7/czdepU7rrrLk499dRO8/6b3/yGRx99lOnTp1NUVNRmmtzcXH74wx9y1llnMXPmTO644w4AHn74YX7/+98zY8YM/vjHP/Kb3/ymw2tdcsklTJw4kZycHK699loWLlwYPvaTn/yE22+/nby8vGZTpf/4xz/G5/MxY8YMcnNz+fGPf9zpPSnVl/k6rGIKNCtBbPikjM/Lo7suS9Sm+xaRhcBKY8xS+/EPAIwxv4hIs85Os9EOCkeALKygcrUx5t+7ej2d7vvk8pWvfIWLLrqIyy67rNufW98Xqq/6yweH+MHf2+5Ms+aW0/nnrqM8/Ma+8L7ls0bwmytnn9A1e2u675FAQcTjQntfm2mMMX6gGsgAJgFGRNaJyIcicmdbFxCRG0UkX0TyQ8t4KqVUf9VZFZPXH8QRUTv9eXlDVPPTVxupXcAZwDygAfiXHeX+FZnIGPM48DhYJYgez6WKmj/84Q+9nQWlelxHVUxefxCPP0hSnCs8gK6wMroBIpoliCJgdMTjUfa+NtPYVUxpQDlWaWODMabMGNMArAXmRDGvSinVqyrrvc0aoVsqr/fS4PUT52pqhyur87LqnQO8ubek3fNORDQDxGZgooiME5FY4EpgTYs0a4Dr7O3LgDeM1SiyDpguIol24DgL2BXFvCqlVK+pcftY+Mt/8fK24nbT3PaXj3g2v5A4V/OP7Xtf2cVL2w5HJV9RCxB2m8ItWB/2u4FnjTE7ReQeEbnYTvYEkCEi+4A7gLvscyuB/8YKMluBD40xr0Qrr0opFQ3BoGH93pJOx/tU1ftw+4IcqmhdZdRyKFKsy8ELN5/Oo1dblSpBA6edktlteY4U1TYIY8xarOqhyH13R2y7gcvbOfdPWF1dlVKqX9p0oIKv/H4zL958OjNHp7ebLlS1VOdpPfgtOdZFbcT+OJeDWaPTGZHWNDRs4SkZrc7rDjrVRpRFTpG9du1aJk2axOeff97l8yMnqlNK9S+hD/wad8fDuNy+1r2XYpxW0SE5vvn3+Fi7iikrJY44l4OxGYmMTE/ojuy20ld7MZ10/vWvf3Hbbbexbt06xo4d29vZUUr1gFC3VU8bASCSO6Jx2iFWtVFGUhxHatwkxbUIEPYqciLCGRMyyR2R2s25bqIliB6wYcMGvv71r/Pyyy9zyimnAPDSSy+xYMECZs+ezXnnnReetK68vJwlS5aQm5vLDTfc0Kzu8lin6y4tLeXSSy9l3rx5zJs3j3fffbcH71opFRr57O6gdxI0X/xncFIs31s6mUvnWsPGklsECEdEo8QTX5nHHUuaz0XWnQZMCeL+D+5nT8Webn3OKYOn8P353+8wjcfjYcWKFaxfv54pU6aE959xxhm8//77iAi/+93v+NWvfsWDDz7IT3/6U8444wzuvvtuXnnlFZ544onwOcczXfe3v/1tzjjjDA4dOsTSpUubTRColIqu0OyrbVUhRYo8HuN0cPM5E1hj90xqGSA6q67qTgMmQPSWmJgYTjvtNJ544olm8xEVFhZyxRVXUFxcjNfrDa/dsGHDBv7+978DcOGFFzJo0KDwOQ899BDPP/88QHi67oyMjFbTdf/zn/8E4PXXX2fXrqbewTU1NdTV1enSoUr1EF84QHS9BBFjVyHF220NsS26tdY0aoDodp19048Wh8PBs88+y+LFi/n5z3/Of/7nfwLWgjp33HEHF198MevXr2flypUdPs/xTNcdDAZ5//33iY/v9xPhKtUv+fwdB4gat4+UOFeLAGH9L8fHOMOPt/zoPPaX1XP5YxupcUd/mu8QbYPoAYmJibzyyis8/fTT4Sqj6upqRo606hiffPLJcNpFixbx5z//GYBXX32VysrKcPpjna57yZIlPPzww+HHobWxlVI9I1TF5PG3rmI6WuMm72ev886+Mtz+5lVMQHhAXIzTQUZyHCPsnkptdYWNFg0QPWTw4MH84x//4N5772XNmjWsXLmSyy+/nLlz54ZXYwNrausNGzaQm5vL3//+d8aMGQMc33TdDz30EPn5+cyYMYOcnBwee+yxqN2fUqq10NxKbZUgPj1ahzcQ5GB5A562qpjsEkSo11Jmcmy0s9vKgKli6i11dXXh7dGjR3PgwIHw4+XLl7dKn5GRwWuvvdbmc7366qudXuOyyy4LT5GdmZkZXsZUKdXzvB1UMYUm2mvZptC6iilUorAeL581IjqZbYMGCKWUihJfB72YiqoaAasdIlRKAHCFSxB2FZOrqVvr3nuXEePouYofrWJSSqko6agEUVRpB4hGX7PjsS1KDDERwSPO5cTh6P514ttz0pcgjDGt1n9WA1e0VlBUqi3hEkQbjdSF4QDhxxVRKmiqYrK7uTp773v8SV2CiI+Pp7y8XD8UFGAFh/Lycu32q3qMt4NG6sgqpsjjrhaN1DG9GCBO6hLEqFGjKCwsRJcjVSHx8fGMGjWqt7OhBghfO91cfYEgxdVNVUzpiU09lEIlhlingzGDExmXmdRDuW3tpA4QMTEx4RHKSinV09prgzhS7SZorLUeatz+NgfKORzChjvP6bnMtuGkrmJSSqne1DSba/MAEapeys5IoqbR16yE4erFKqWW+k5OlFLqJNNeN9dQA3XO8FSqW/Ri6s02h5b6Tk6UUuokE26kbjHdd6iL6+RhKfiDhsp6b/hYrLPv9LrUAKGUUlHitQNDyzaIwsoGhqTEkZkcB0BJrQeXPb5Bq5iUUmoAaJqLqXkVU1FVI6MGJZCaYPUTqm70kZ4YAwygKiYRWSYie0Vkn4jc1cbxOBFZbR/fJCLZ9v5sEWkUka32j84yp5Tqd9pbD6KoqpGRgxJJjY8J70tLsLYHRBWTiDiBR4ELgBzgKhHJaZHseqDSGDMB+DVwf8Sxz4wxs+yfm6KVT6WUipZQN1ePPxgesBsMGg5XNTIyPSEcFAAG2WMhBkoV03xgnzFmvzHGCzwDtJy+dDkQWgzhOWCx6LwYSqmTRGg9CGgaLFdS68EXMIwa1DxADLQqppFAQcTjQntfm2mMMX6gGsiwj40TkY9E5C0RObOtC4jIjSKSLyL5OlpaKdXX+CICRKiaKTSCenhaPKMGJZAUa02pERpNHTMQqphOUDEwxhgzG7gD+LOIpLZMZIx53BiTZ4zJy8rK6vFMKqVUR3z+pnngQg3VpbUeAIakxONyOpg2Mg2AoalxxMc4yEqJ6/mMtiOaAaIIGB3xeJS9r800IuIC0oByY4zHGFMOYIzZAnwGTIpiXpVSqtuU1nr4z+e3U+v2hUsIHn+A8joPpXVWgMhMsUoMM0ZZAcLpcLDhznO4aEbPLQjUmWgGiM3ARBEZJyKxwJXAmhZp1gDX2duXAW8YY4yIZNmN3IjIeGAisD+KeVVKqW7zs5d38edNh6j3BkixeyptL6om777XeW3nUQAykqySwoxR6YA1eG5ISjzOHlzvoTNRm6zPGOMXkVuAdYATWGWM2Ski9wD5xpg1wBPAH0VkH1CBFUQAFgH3iIgPCAI3GWMqopVXpZTqToftuZYAUuJdHKmBjwurMQY27i9nUGIMsS7r+/nS3GF89fRsvnZ635tYNKqzuRpj1gJrW+y7O2LbDVzexnl/A/4WzbwppVR79h6p5UBZHcumDT+u88vsaiRo6p30ydFawOr6OnZwYvh4rMvBT76YewK5jZ6+2kitlFK9ZtU7B/jh8zuO+/zyuqa5lcZnJgOQf7AyvK8vNUR3RAOEUkq1UOf1U+vxH/N5HxdWMf++15udOyYjkViXg7qIfaE5mPo6DRBKKdVCg8eP1x9sNo6hKzZ+Vk5JrafZvjiXg3EZzVeF0xKEUkr1Uw1ea1Bbg6f1WtIdCZrW++JcjvCyoaEOSlqCUEqpfqrRHvVc722/mskYg79FCaO60YfTIbx86xkMTgqNjHYwLssKEDkjrPG+WoJQSql+qt5uL2joIEC8/HExefe9TqO3qZRR3ehjUGIM00amkRBjDZCLcTaVIJbmDCM9MYbcEa0mhuiTotrNVSml+qPQh35dB1VM24uqqWrwcbTGTbYdAGoafaTaE/Al2iOoY1wOpg1NweUQFk8dyq2LJ0Y5991HA4RSSrVQH26DaL8EUWQPhiuv94QDRHWjLzxDayhAxDodTB6WwvaVS0mw9/UXWsWklFItNJUg2g8QodHSZRFjHmrcTQEiFAxCs7P2t+AAGiCUUqoZXyAYXsehwdt+FVMoQKzbeYTlj75LozfQogRhVdC01bOpv9AqJqWUihAZFNorQXj9wfB4h1c+LsbjD3KgrL7NKqaOGrr7Oi1BKKVUhMheSZEf7l5/MLyWw9EaN/YKouGV4oqqGq1G6vjmAaKxg1JIX6cBQimlIkSOfaiP6MX0i1d3M+++16lu9IUbqCN9WlJL0BAuQXx36WQumjGcL87sO+s7HCutYlJKqQiR3/jrI6qY3vrEWtb40Tf38fK2wwBkJMVSXm81Uu8ptmZrDQWIISnxPHL1nB7Jc7RoCUIppSJEtkHUR2wPtteMfnzDfg5Xu0lPjGG6vRocwJ4jNQDhcRAnAw0QSikVoXkVU9N2qFppcFIsr95+Jpv+czEj0hPCxz85Wgc0lSBOBlrFpJRStmc+OMQDr30CWOMXQo3UHn+AIzVubl88kVvPnYDLaX23zrTnWxqbkcjn5Q3AyRUgtAShlFK2V3ccCa8Gl5kcF+7mWlxl9VoaPTgxHBwAxmYkEetycNopGYDVc2nU4ITWT9xPaQlCKaVskWtJZ6XEhdsjCiut/aMGNf/wXz5rBAtPyeAlu9H62+dNCndzPRlogFBKKazpu5sFiOQ4DpTXA1BYaVUftQwQLqeDEekJXL1gDCPSE7hw+vGtYd1XRbWKSUSWicheEdknIne1cTxORFbbxzeJSHaL42NEpE5EvhvNfCqlVI3b37zXUlJseMGgQxUNuBzCsNT4Ns9NiY/hizNH4AitCHSSiFqAEBEn8ChwAZADXCUiOS2SXQ9UGmMmAL8G7m9x/L+BV6OVR6WUCjncYvDboKRYKhq8GGP4tKSOcZlJzdofBoJO71ZEForIoyLysYiUisghEVkrIjeLSFoHp84H9hlj9htjvMAzwPIWaZYDT9rbzwGLRUTs664ADgA7j/WmlFLqWLUMEMPT4vH6g5TXe/nkaC2ThqX0Us56T4cBQkReBW4A1gHLgOFYpYEfAfHAiyJycTunjwQKIh4X2vvaTGOM8QPVQIaIJAPfB37aSf5uFJF8EckvLS3tKKlSaoB6becRtnxe0Wm6UIC4/9Lp3HXBlPAYh/2l9RyqaGDSkIEXIDprpL7GGFPWYl8d8KH986CIZEYhXyuBXxtj6uwCRZuMMY8DjwPk5eX140l1lVLRcu8ru5k8LIXfXju4w3RFVW5inMLlc0fjcAjbC6sBePvTUoyBycOSeyK7fUqHASIUHEQkCWg0xgRFZBIwBXjVGONrI4CEFAGjIx6Psve1laZQRFxAGlAOLAAuE5FfAelAUETcxphHju32lFIDXXmdhzp352MTCiobGJ6WEG5oHp5uNUiv32vVTkwaqiWI9mwAzhSRQcBrwGbgCuDLHZyzGZgoIuOwAsGVwNUt0qwBrgM2ApcBbxhjDHBmKIGIrATqNDgopY6V2xeg3htotq7D2u3FuBzCktxhAHx4qJLqRh+7DtcwdXhTEMhIiiXW5WB7UTVxLgdjM5J6PP+9rasBQowxDSJyPfA/xphficjWjk4wxvhF5Bas9gsnsMoYs1NE7gHyjTFrgCeAP4rIPqACK4gopVS3CM20GhkgvvX0hwAc/OWFANz3ym4+OVpLrdvPpXOamklFhBFp8Rwsb+DU8Rk4T7IurF3R5QAhIguxSgzX2/s6XWDVGLMWWNti390R227g8k6eY2UX86iUUs2U29Nm1Lr9zR6H+AJBdhRVhxf9mT4qvdnx0P7FU4dEO6t9Ulc79d4O/AB43i4FjAfejF62lFLqxDWVIHwAbC2oanZ8T3FtOAgATB/ZvOd+aF6mcyYPzADRpRKEMWYDVjtE6PF+4LZoZUoppbpDeZ0VINy+IL5AkI8ONQUIXyDI1kLr8bjMJPzBIIPt2VlDfnfdPN75tJTRgxN7LtN9SIcBQkR+CzxkjNnexrEkrIZqjzHm6SjlTymljltFfVOVUr3Hz7bCpgBR2eBl66EqMpNjeepr85u1U4ScNSmLsyZl9Uhe+6LOShCPAj8WkenADqAUa4DcRCAVWAVocFBK9UmhEgRY7RAFFQ04HUIgaKio97KvtI4pw1IHbAmhM52Ng9gKfMke2ZyHNZK6EdhtjNnbA/lTSqnjFmqDAKsn09EaD1OHp7CjqIaKei8FFQ0smzasF3PYt3W1DaIOWB/drCilVPeK7LVUXN1Ioy/AlGGp7CiqoaCigYp6L2O09NCugTU1oVJqQCmv95Iab30P/qzEWtth6vBUoKlHkwaI9mmAUEqdtMrrvOER0CpmgmUAACAASURBVPtK6gCYYs/KurXAmmtJA0T7jilAiIi+kkqpfqO83sPYDOtj67NSK0CMTE8gNd7F7uIaAMZk6Mdae7oUIETkNBHZBeyxH88Ukf+Jas6UUuoENHj9uH3BVgFiaGo8GclxAKQnxpxUa0h3t66WIH4NLMWaaRVjzDZgUbQypZRSJyrUxTVUhVTZ4CM13kVCrDPcLjEuc+BNwHcsujoXE8aYghZrMwTaS6uUUr0t1MU1MzmO5DgXdR4/w9KsKby/s2Qy2wqquGjmiN7MYp/X1QBRICKnAUZEYrDmZtodvWwppdSJCXVxzUiOw1pFAIanWetCLJqUxaIBPEK6q7paxXQTcDPWEqFFwCz7sVJK9UmhEkRGUiz1XqvC45tnn9KbWep3ujpQroyOFwdSSqkeU+/xkxDjDK/+1pZQG0RGciwPXzWbhBgnp47P6KksnhS6FCDsVeFuBbIjzzHGXBydbCmlVNs8/gCn3/8G3182havmj2l1/Mn3DrK/tI5PS+qIj3GQGOvii9rWcFy62gbxAtbqby8BwU7SKqVU1JTUeKhq8LH3SG14nzGG3769nxmj0vnZy7vwB602h5Hpna9FrdrX1QDhNsY8FNWcKKVUF5TUugEorW2aZ+kP7x3k52v3kJEUiz9omD4yje1F1b2VxZNGVxupfyMiPxGRhSIyJ/QT1ZwppVQbjtZYgSEUKHYX1/DztbuJj3FQXu9FBH504VQAiqoaey2fJ4OuliCmA9cA59JUxWTsx0op1WOO1liBoaTWgz8Q5Lt/3UZaQgz3rpjGTX/6kMlDU5g/bjBOh3D53FG9nNv+rasB4nJgvDHG22nKCCKyDPgN4AR+Z4z5ZYvjccBTwFysUdpXGGMOish84PFQMmClMeb5Y7m2UurkVGJXLZXUeFidX8DOwzU8evUczps6lOFp8Zw1KQsR4ZN7L8DZQS8n1bmuBogdQDpQ0tUnFhEn1op05wOFwGYRWWOM2RWR7Hqg0hgzQUSuBO7HWsZ0B5BnjPGLyHBgm4i8ZIxpvSagUmpACZUgGn0B7nlpF/PHDeYL04chIqz79iLiXU4ADQ7doKsBIh3YIyKbgXDLUCfdXOcD+4wx+wFE5BlgORAZIJYDK+3t54BHRESMMQ0RaeKxqrOUUoqSmqbGaY8/yL+fOpbQNEA68V736mqA+MlxPPdIoCDicSGwoL00dmmhGsgAykRkAdaa12OBa9oqPYjIjcCNAGPGtO4PrZQ6+RytcZMa76LGbX0kzM8e3Ms5Onl1dST1W9HOSBvX3ATkishU4EkRedUY426R5nHstoq8vDwtZSg1ABytcTN9VBrv7isHCE/Ap7pfh91cReQd+3etiNRE/NSKSE0nz10EjI54PMre12YaEXEBadhTiocYY3YDdcC0zm5GKdW37S6u4fz/fouqhmPq7wJArdvH0Ro3NW4/M0alRyF3qqXOShBJAMaYlON47s3ARHuajiLgSuDqFmnWANcBG4HLgDeMMcY+p8CudhoLTAEOHkcelFJ9yPaiaj4tqWNrQRXv76/g2+dPJM5uVG6pot7L8kff4b8um8m4zCTO/NWbCBDjFK6cNxqXQ1iaO6xnb2CA6SxAHHe1jf3hfguwDqub6ypjzE4RuQfIN8aswZq+448isg+owAoiAGcAd4mID2vcxbfsCQOVUv1YTaMPgBe3Hub5j4o4Z3IWC9qZQO/9/eUUVDTy1/xCZo1Ow+u3hmDdcMY4xmYk8Z0lk3ss3wNVZwFiiIjc0d5BY8x/d3SyMWYtsLbFvrsjtt1YYyxanvdH4I+d5E0p1c/U2g3Ln5ZY8yiFpuRuafPBCj44UAHAG3uOUlTVwPisJFZdN4/Rg3UN6Z7SWYBwAslYg9WUUuqYVdZ7eenjw1xz6lhq3FYJYl+JtT50WZ2nVfr8gxVc/thGAGKdDiobfLy/v4Jvnn0K2bpEaI/qLEAUG2Pu6ZGcKKVOSs/mF/CLV/dw1qSscAnC7bOqi8pqPQSDptm6Dmu3HwlvXzRzOKW1HkYNSuSmRbrYT0/rLEBoyUEpdUL22NNyl9V5qLVLECFvfVrGQ2/s49lvLGT+uMEYY1i38wgzRqXR6A1w7cJsZo3WHku9pbMAsbhHcqGUOum8uaeEX7y6G4/duFxa66Wmsfl4120FVQA8vuEz5o8bzN6jtRRVNXL74ol8ad7oVs+pelaHAcIYU9FTGVFKnVye2XyIT47WhR+X13uo9fjaTPvhoSoq6718XGit4TA3e1CP5FF1rKtTbSilVJe5fQE2fNK8Z3pZrTfcBtFSRb2XOff+kxkj00iMdTIuQxuj+4KuLhiklFJdtvGzchp9ASYPbRpjW17vCY+DiHR+zlB+d20esU4H2wqrmTo8tVmjteo9GiCUUt1u52Grquixa+Zy57LJjM9Mshupm0oQowdb60WPz0zivJyhnDkxC4Cc4ak9n2HVJg0QSqluV1bnJSXOxbjMJL519gQyU+IorGzEHzQMTY0DCJcuxtljG5bkDgUgd4QGiL5CA4RSqtuV1XnITIkLP85KjuNAaT0AY+32hdCEexPtQPGF6cO5buFYluj8Sn2GNlIrpbpdeZ2XjKTY8OOM5FhqPVb10kUzhpMzPJUbF43ntFMymDvW6rGUHOfip8t10ua+REsQSvUTe47UkH3XK2z5vO/3Pi+v95CRHBEgkppKE2MGJ7Ly4lziY5zk6WI/fZoGCKX6idWbrQUa39/f9wNEWZ2XzOSmoJCZ0hQsUnRZ0H5DA4RS/cTOw9YaXZFVN32RPxCkssFLRkSAOD9naHg7PVEDRH+hbRBK9RO77ADR4A302DV/8epuiqvcPHTV7C6fU9ngwxjIiqhiGpISz9a7z+ftT8sYrzOy9htaglCqHzhc1Uid3cjb4G17NHI05B+sDK/L0JF1O4/w1d9/QDBowlN4R5YgANITY/nizBGI6CC4/kIDhFL9QEFFQ3i7vgdLEGV1HkrrPASCHS8uuW7nEd7cW8pnpXUcrmoE+n5VmOqcVjEp1Q/UR5QaGjw9V4Ioq7WCQ3m9hyEp8e2m+8xeAOi2Z7ayu9iqCoscB6H6Jw0QSvUDkVNURLsE8fO1uwkEDd9ZMil8rf2l9ZTWejglK5n4GGez9MYYPrMHwYWCA9CsF5PqnzRAKNUPhNofUuJcNEY5QLy5pwR/0HDdwuzwvpuf/pDyei9Th6fy6u1nNkt/pMZNncePyyH4g4afLc8lNSGGtATtrdTfRbUNQkSWicheEdknIne1cTxORFbbxzeJSLa9/3wR2SIi2+3f50Yzn0r1dfV2gBiSGtesuikaiqvdFFU2crTWHd5XXu8FrBLC5+X1zdKH1pf+5tmnsHzWCK5eMJbls0ZGNY+qZ0StBCEiTuBR4HygENgsImuMMbsikl0PVBpjJojIlcD9wBVAGfBFY8xhEZkGrAP0HacGrDq7iikzOY4GT/RKEDVuX7i0ElldBHBF3mhW5xewfm8p152WxF/zC3hy40F2FFnprlk4tsN2CtX/RLOKaT6wzxizH0BEngGWA5EBYjmw0t5+DnhERMQY81FEmp1AgojEGWM8UcyvUn1WnSdAcpyLlHgXxdXuzk84TsVVTc/90SFrOdBQ1dGFM4az6UA5f91SwGeldTy18XNyhqcyc1QasS4HWdrmcNKJZoAYCRREPC4EFrSXxhjjF5FqIAOrBBFyKfBhW8FBRG4EbgQYM2ZM9+VcqT6mzuMjKc5JQqwrqgPlQl1UAbYWVCECE4Yks+dILbkjUrk8bzT/tW4vnxyp4/K5o7j3kmnEuZwdPKPqz/p0I7WI5GJVOy1p67gx5nHgcYC8vLyOO2or1Y/V2yWIpFhnuD0iGg5XNwWIA2X1ZCTFMmpQAjWNPjKS47j5nAlcf8Y4gsaQGNunPz5UN4jmX7gIGB3xeJS9r600hSLiAtKAcgARGQU8D1xrjPksivlUqs+r9fhJjo8hMTa6vZiKq9w4BJLiXNS6/WQmx3HnsinNlgpt2c1Vnbyi2YtpMzBRRMaJSCxwJbCmRZo1wHX29mXAG8YYIyLpwCvAXcaYd6OYR6X6hXqPn+Q4J0lxTuq9foyJToH5cHUjQ1PjCdojp687LZtJQ1N0Wu4BKmolCLtN4RasHkhOYJUxZqeI3APkG2PWAE8AfxSRfUAFVhABuAWYANwtInfb+5YYY0qilV+l+rI6t5/M5EQSY10EDXj8wRP+Jn/Dk5uZPjKd28+bGN5XWNnI8LR47l0xjaoGH5fOHXWiWVf9WFQrEY0xa4G1LfbdHbHtBi5v47x7gXujmTel+pM6j5+kOBeJsVZQqPf4TyhAFFc38vruEo7WeMIBotbt46NDlXz19HEsnjq0k2dQA4G2MinVD9R5/KREBIgGb4CME3i+9XtLAfjkaC3+QJDPSuv5x44j+AKGxVOGdEOO1clAA4RSfZwxJlyCSIqz/mVPdDT1m3us2lqPP8ju4lq+8vsPwqOlQ2tEK6UBQqk+zuMPEggakuOblyCOlzGGTQcqmDk6nW0FVfz0pZ2U13s5e3IWp47PwOXUVQCURQOEUn1caCbXlIgSxIlMt1FY2Uh1o49LZo1gW0EV+Z9XMi97EH/46vxuya86eWiAUKqPCw2Mi2ykrnX7OjqlQ6G1rWeNGcSiSVmU1Lh5+Ko5J55RddLRAKFUHxeaPC85zsWo9EQACiobKKxsYGR6QpeW8PzHjmImDU1hfFYyuw5X43QIU4al8ORX5+kSoKpdWtmoVB9XbY9iTk2IIS0xhoykWN7cU8qiX73Jyx8Xt3mOMYY7Vm/lsv99j2fzC/jW0x/yw+d3AFYJ4pSsJOJjnBocVIe0BKFUH1dir8swxF7C85SsZDbuLwfg3X1lfHHmiFbn7D1ay98/KsLlELYcqsQY2Li/nH/sOMIHBypYkjus525A9VtaglCqjztaY01kPCTVWmthfFZS+Fj+55VtnvOWPc7hzmWTMcY6JznOxU1/2gLALedOiGaW1UlCSxBK9XElNR4SY50k2z2YIgPEvpI6Kuu9DEqK5Z+7jjJ/3GDSEmJ465NSpgxL4Wunj+PdfeWsmD2C3BFp/P3DIhZNzGRcZlJ7l1MqTAOEUn1cSa07XL0EVhUTwJwx6Xx4qIrNBysYm5HE15/K59qFY1k2bRgfHKjg+jPH4XI6ePJrTd1X77pgSo/nX/VfWsWkVB9XUutptpTntJFpxMc4uHXxRJLjXPxrdwkvf3wYgOe2FHLDk/mMy0ziG4tO6a0sq5OEliCU6iPqPX6e2VzAsmnDGJmeEN5fWushZ0Rq+PHQ1Hh2/nQZToeweOoQXt1RTHpiLCPTEyiqamRcZhJPf30Bg5Nie+M21ElEA4RSvcwYQ2mth3/uPsrPXt7Fz17exZpbTud3bx/gQFk9B8rqOXtyVrNznA6re+oF04bz4tbD1Lj9PHj5TAYnxZI7MrVZiUOp46UBQqle9tLHxXzn2a2cPiEzvO/rT+WHey+BVWpoy9mTs7h0zigWTcrk4pkjdFyD6lYaIJTqZe9+WoYvYFi/t5T54wbj9QfZWlDFqeMHc6TazcHyBjKT49o8Nz7GyYNfmtnDOVYDhTZSK9XLPjzUNJYhZ3gqF0yzBrH925xRXLMwG4AMbU9QvUBLEEr1oH0ldazdXsyt505ARKhu9PFpSV34+NThKSzLHU69N8DFM0cQ53IwY1QaebpGg+oFGiCUirKtBVU8tv4zRg9OwBcw/OG9g1wxbzRDU+PZVlAFwHlTh/D67hJyhqeRlhjDHedPCp8/L3twb2VdDXAaIJSKIq8/yH888xGHKhoIGhhmNzYfLKtnSEocHx6qRAR+/m/TuWhfOdNGpnbyjEr1nKi2QYjIMhHZKyL7ROSuNo7Hichq+/gmEcm292eIyJsiUicij0Qzj0pFy54jNVy36gMOljfwn1+YCsCRGmvivf9Z/xl5977Om3tKmDw0hSEp8ayYPVJ7Iak+JWoBQkScwKPABUAOcJWI5LRIdj1QaYyZAPwauN/e7wZ+DHw3WvlTKtrufmEnu4pruOP8SVx/xrhm02W89Ukp5fVethVWM3uMti+ovimaJYj5wD5jzH5jjBd4BljeIs1y4El7+zlgsYiIMabeGPMOVqBQqt/Zc6SGDw5WcPM5p3Db4omICKedkgEQXhUuZM6Y9N7IolKdimaAGAkURDwutPe1mcYY4weqgYyuXkBEbhSRfBHJLy0tPcHsKtV9/ppfSKzLweVzR4f3XbMwmy8vGMP8cVajc2gqjLnaQ0n1Uf16HIQx5nFjTJ4xJi8rK6vzE5SKki2fV/Di1qLw400HyskbO4hBEeMX5o4dxH2XTA9Ptf3A5TP43bV5jLdnZ1Wqr4lmgCgCRkc8HmXvazONiLiANKA8inlSqlvVuH2U1Xl4YN0nfP9vH+P2Bajz+Nl1uIa8drqnnjo+g3GZSSwcn8l5OUN7OMdKdV00u7luBiaKyDisQHAlcHWLNGuA64CNwGXAG8YYE8U8KdUt9pfW4Q0E+fnaPRRWNlBc5cbtC/LUxoMcKKsnaGBedttVR0tzh7FUl/xU/UDUAoQxxi8itwDrACewyhizU0TuAfKNMWuAJ4A/isg+oAIriAAgIgeBVCBWRFYAS4wxu6KVX6WOxc1//ojCygZq3f5m+3++dk94W3snqf4uqgPljDFrgbUt9t0dse0GLm/n3Oxo5k2p47X3SC27i2sAsGfdJmhg5qg09h6t5ZZzJhAf07REqFL9lb6DleqCnYerSY2PYUhqHH947wBOh3DNqWNxOYTtRdUUVDTwu+vmUdXgZeLQlN7OrlLdQgOEUp2456VdrHr3ACPS4slKiWNbYTWXzB7JyotzASiosKqaslLiyEppe1pupfojDRBKdaCk1s2TGw9yxoRM3v2sjMPVbv77SzO5ZHbTkJ7RgxN7L4NKRZEGCDXgGGP45at7WDptGHMiGpKf+eAQT286RO6IVC6aMYL/2/AZJTUeAkHDyotzyT9YgdMh/NucUb2Ye6V6jgYINeB8Xt7A/23Yz/v7y3nh5tMREfYcqeEHz29nQlYyz+YX8MzmAlLiXdR5/Mwek86EIclMGKID2tTAogFCDTgfHKgAYFthNe/sK2NQYiw/e3kXybEu/nrTQkprPRyudjNjZBpHatykJcT0co6V6h0aINSAcqi8gbf3lTEoMYbEWBdf+8NmfAGDQ+AnX8wlPTGW9MTYcE+kQbrUpxrANECoAaHe4+fRN/fxv299hjFwfs5Q7rtkGj9/ZTfjs5K5bmE2aYlaUlAqkgYIdVKq9/j5w3sHafD6efvTMj49WkejL8CF04fzWWkdl84ZxZCUeP7flbN7O6tK9VkaINRJIRA0fFxYhdcf5OPCap7bUsjeo7UAzBydzhXzRvPFmSN0am2ljoEGCNUvGWN4c28Jf/+wiJJaD5+X13O0xhM+fkpWEr//6jxOOyWDOJezg2dSSrVHA4TqU4qqGnl2cwEZybGMTE8gb+zgcNvAzsPVrN5cQEKMkw8PVbL5YCVZKXGMy0wib+xgluQOJS0hhqnDUxmaGt/Ld6JU/6cBQvUpP39lN69sLw4/jo9xcOfSKew9UsvfPizE6RCCxjA0NZ57V0zjinmjiXH263WvlOqzNECoXuf1B9l7pJaD5fWs3VHMN84azw1njOez0jr+a91e7nl5F3EuB1cvGMMd508iPVG7nirVEzRAqGO290gtWSlx4TWVu8ofCOKyv+0bY9h8sJKXth3m1R3FlNV5AUhPjOGGM8aHJ77789cXsPNwDZOGpuj02Ur1MP2PG4A8/kCzhts9R2oYn5lMrMv68N57pJYxgxNJiHXiDwRxOgQRa+GDm5/+kFe2F3PulCGs+sq8Tq9V3eBjX2kd976yi93FNcwYlU5No4+iqkZq3X4SY50smpjFRTOHMzI9gXGZSc1KCHEuZ7P5kpRSPUcDxACzv7SOLzz0Nr+5cjZLc4exo6iaLz7yDrcvnsh/nDeJ8joPFz38Nl+cOYJbz53IFf+3kczkOL52xjgmDEnmle3FjEiLZ/3eEkpq3WQlx/HOvjIAPiup42itB38gyL6SOg6WN3CgrB6AhBgnF0wbTmFlA6MHJ5KXPYjZowdxwfRhJMbq21Cpvkj/MweYP77/OW5fkCfePsCSnKE8/ManGAN/3nSIm8+ZwGu7juILGJ7/qIgNn5QRNAa3L8B3/7qNWJeDGKfwm6tmc/ljG7nk0ffw+IOU1TV1L3U6BKcIE4cmM3FIMpfNHcWkoSnkjkhlRHpCL965UupYaYAYIKobfRRVNvK3LYUkx7n44GAFi//7LfaX1jMvexCbD1by6Jv72LS/gpHpCQSChuHp8dy3YjpTh6ewdvsRvr16K0tyhjEvezAXzhhOQUUDk4emMHfsIJLiXKQmxDAvexCCkBCrYw+6nTEQDIBT/21VzxBjTG/noVvk5eWZ/Pz83s5GjzPG0OANkBDj5KMCa2yAyyF4A0EmZCUzcWgKr+4o5oF1ewkaSI5z8di/z+X+f+whPTGGpbnDuDxvFLf95SPW7TwKwDfPPoXvLZmMI7Tgsu1QeQODkmJIidc5i3rc5xvhL1eAzw0XPghzronetV75LmCs65xsPvgtuOKj+/pFgzEg0nm64yAiW4wxeW0ei2aAEJFlwG8AJ/A7Y8wvWxyPA54C5gLlwBXGmIP2sR8A1wMB4DZjzLqOrtXfA0QwaKhx+/AFDMlxLkprPew9Wst5U4eEG4gBDpbVs7Wginqvn/f3V7C7uIZ9JXWkxLmo9fjbff6luUNZNCmLZbnDyEhuvSymMYYNn5bR6A2waFKm1S5QuheSh0JCelPC2iMQmwxxujZCjynZA08th5gESB0Jn78L48+GRd+DjFMgPg0CPhCH9eFX9Tm8dDtMWAxzv2J9uID921i/3VVWel8DOGIg6LceH90Jf7/BSv+lpyB9rHUs4ANfvZ3WB0lDrP2hY0G/tT9g/w76m7bFAUmZgFjXNkE7H0H7J2I7vN+0sz9oXa/8M3DGQPIQcMZa+ysOgMNpvQYmaL1e7mpwuMDvgYZy2P6sdW+zr7He141V1nUSB0W8TkHrPG+d9dqW74eaIhg517pm6LU0AatEZwLWOcFgxHag6bWmjdc/dJ3QTzDQ/HHkDwKVB60AkZhh3U/o2sGA9VpPuRAufui43l69EiBExAl8ApwPFAKbgauMMbsi0nwLmGGMuUlErgQuMcZcISI5wF+A+cAI4HVgkjEm0N71eitAGGMIGvAFghytceMQIc7lwBsI4vUH8QUMXl8Ar9/HzqIqDpbW0uj14/b5KK1upLzOTTAQoLrRg9cXwIEh3gVOAZ/Px8j0OBwY3F4fjR4fgWAAweDAMCnZzbykErKyhnLEl8jU4clMG56Cw+/G1VjCQedYDtUJI+I8TE0L4Ai4oXgb1B2FEXOsN1b+Kpi01HrjDRpn/S7dY/2DvPv/IDETcldAyjDrH/HNX0BSBiy8FeJT7TerafGGjvwnb+OfvuXxyDQNFVCx3/pHdMVb13TFgyvW/iCIPL/Fc7TMR1t56Shtq+duK3179xr5Qzv/6MeQ78i8+BogYRBc95L1N3rrftj+V+tDqz3OWAh4j+9NnTERAh6oOnR85/cEV0JTUAqJSbRet4DX+jAN+q33TjBgvR4AE8+zfn/6OmCsLzvisN7vItY2Yn0Bik0GT40VDNNGQsmu5nkQpxWQwr8d1k9oG7G/9UvEt//IfQ5wOJrOk4jnCB1DrPdA2ijrf62h3LqfyOs6nNb/83GWinorQCwEVhpjltqPfwBgjPlFRJp1dpqNIuICjgBZwF2RaSPTtXe94w0Qb2z+G/+19SdWfsJ7m78m7e2nxX5psS86BcKIK4j9WURTztq7qthHJPRGDP1jOeOsD4O2xCRYTxzw2B9wdnpjf2vpKG9d2NdmXgXrWyqEPySNaXmX0uZfyEgb+5rtamNfRNqWm23lL/yXlpb7Orhuq+fu+B3V6vkEjCsOb9CPP+gnxhFDnDOWmIAPB4IxQYxI0+sF4ErABL2YYKDVcxpM+N6azpDQmdYHERBjgjjFab1nWuQbE2z+oQctqkBCH4SmKWB28Do0F/n6mFb7rDeysykf4f3NR9SbZnlsX1c/A03bf9U+4ZzR57DytJXHdW5HASKarV0jgYKIx4XAgvbSGGP8IlINZNj7329x7sgW5yIiNwI3AowZM+a4MpmSOIgRJlRd0vSGD78VQtHe3pZQunBSB6G9ztAgMELjBqzfItYHc4zTYY01iHjOZv98zb5lhPLTcjvin9Hhgvh0JOhHAl4Eh/3FxIk44zHuKjBBjDMW44yxPhRik6xz/W7rAyUmwSp+O1zgrbc++OOSrX88V8R8RsGAdU5MovU44LGqEOwPl6aXrymPEvltKbQn8h9WpHUacSCOrjVwC9J6XxsfCCeSrs3rdvUaXbxum9do49xYZywuhwt/0I8n4METEdgl4rWNPFdCr3GLNJHpmqWxt4MmSMAE8Af9BE2wy/nu6r30lBN5vU8oXZTaC9qTk5ETleft190hjDGPA4+DVYI4nueYl3su83Lf7zyhUkoNMNGc5awIGB3xeJS9r800dhVTGlZjdVfOVUopFUXRDBCbgYkiMk5EYoErgTUt0qwBrrO3LwPeMFaF4BrgShGJE5FxwETggyjmVSmlVAtRq2Ky2xRuAdZhdXNdZYzZKSL3APnGmDXAE8AfRWQfUIEVRLDTPQvsAvzAzR31YFJKKdX9dKCcUkoNYB31YtKVVpRSSrVJA4RSSqk2aYBQSinVJg0QSiml2nTSNFKLSCnw+XGcmgmUdXN2esPJch+g99JX6b30TSd6L2ONMVltHThpAsTxEpH89lrw+5OT5T5A76Wv0nvpm6J5L1rFpJRSqk0aIJRSSrVJA4Q92d9J4GS5D9B76av0XvqmqN3LgG+DUEop1TYtQSillGqTBgilM/VGiAAABmxJREFUlFJtGrABQkSWicheEdknInf1dn6OlYgcFJHtIrJVRPLtfYNF5J8i8qn9e1Bv57MtIrJKREpEZEfEvjbzLpaH7L/TxyIyp/dy3lo797JSRIrsv81WEflCxLEf2PeyV0SW9k6uWxOR0SLypojsEpGdInK7vb/f/V06uJf++HeJF5EPRGSbfS8/tfePE5FNdp5X20sqYC+RsNrev0lEsk8oA8aYAfeDNf34Z8B4IBbYBuT0dr6O8R4OApkt9v0KuMvevgu4v7fz2U7eFwFzgB2d5R34AvAq1pqkpwKbejv/XbiXlcB320ibY7/X4oBx9nvQ2dv3YOdtODDH3k4BPrHz2+/+Lh3cS3/8uwiQbG/HAJvs1/tZ4Ep7/2PAN+3tbwGP2dtXAqtP5PoDtQQxH9hnjNlvjPECzwDLezlP3WE58KS9/SSwohfz0i5jzAas9T8itZf35cBTxvI+kC4iw3smp51r517asxx4xhjjMcYcAPZhvRd7nTGm2Bjzob1dC+zGWge+3/1dOriX9vTlv4sxxtTZD2PsHwOcCzxn72/5dwn9vZ4DFssJLJA9UAPESKAg4nEhHb+B+iIDvCYiW0TkRnvfUGNMsb19BBjaO1k7Lu3lvb/+rW6xq15WRVT19Yt7saslZmN9W+3Xf5cW9wL98O8i8v/bu7vXOKowjuPfH77jK9UiQkPTaEqhWEqN0GJ8QUyh3qhQpAUxipdeKKJXFcE/QK/UXGitWGovQq3GG6FqBS2V2te02loLUqSVRouNULBofbw4Z5NhnXWTLclmkt8HlsnOnNl5DiebJ3Nm5hxdJukgMALsIJ3hnIuIv3ORYrxjdcnbR4GbWz32XE0Qs0FvRKwA1gDPSrqvuDHSOWYl72GucuzZAHA7sBz4BXitveFMnKTrgG3A8xHxR3Fb1dqlpC6VbJeIuBgRy4EFpDObJdN17LmaIE4BHYX3C/K6yoiIU3k5Amwn/eKcqZ3m5+VI+yKctEaxV66tIuJM/lL/A7zNeHfFjK6LpCtIf1C3RMSHeXUl26WsLlVtl5qIOAfsBFaRuvRqU0YX4x2rS95+I3C21WPO1QTxLdCd7wS4knQxZ6jNMU2YpGslXV/7GVgNHCHVoT8X6wc+bk+ELWkU+xDwZL5rZiUwWujymJHq+uIfI7UNpLqsy3eaLAK6gT3THV+Z3E+9ETgaEa8XNlWuXRrVpaLtMl/STfnna4A+0jWVncDaXKy+XWrttRb4Ip/5tabdV+nb9SLdhXGc1J+3od3xTDL2LtJdF4eA72rxk/oaPwd+BD4D5rU71gbxbyWd4v9F6j99plHspLs43sztdBjoaXf8E6jL5hzrcP7C3lYovyHX5QdgTbvjL8TVS+o+GgYO5tfDVWyX/6lLFdtlGXAgx3wEeCWv7yIlsRPAIHBVXn91fn8ib++6lON7qA0zMys1V7uYzMysCScIMzMr5QRhZmalnCDMzKyUE4SZmZVygjDLJD0qKSRN25Oqkr6UNCUTzptdKicIs3Hrga/z8j8KT67W3kuSv0M2a/mX24yxcXt6SQ+6rSusf0DSV5KGgO8ldeY5A94nPbjUIWlA0t668foflPRR4XP6JG1vEsNqSbsl7Zc0mGOqzf3xal5/eDrPcGxuc4IwSx4BPo2I48BZSXcVtq0AnouIxfl9N/BWRCyNiJOkJ9l7SE+93i9pGWkohCWS5ud9ngbebXRwSbcALwMPRRqEcS/wQqHIb3n9APDipVbWbCKcIMyS9aR5QcjLYjfTnkjzBNScjDQHQs3jkvaThkRYSpp8KkhDOzyRx9JZRZpgp5GVpIlrduWhnfuBhYXttcHz9gGdk6mYWasub17EbHaTNI80AcudkoI042BIeikXOV+3y/nCvotI/9HfHRG/S3qPNB4OwCbgE+BPYDDGx+8vDQPYERGl1z+AC3l5EX9vbZr4DMIsjXq5OSIWRkRnRHQAPwH3TmDfG0gJY1TSraT5OQCIiNPAaVLX0aYmn/MNcI+kO2BsxN7FTfYxm1JOEGapO6n+AvI2GtzNVBQRh0hdS8eAD4BddUW2AD9HxNEmn/Mr8BSwVdIwsJsmE8NI6pH0TrMYzVrl0VzNppCkN4ADEbGx3bGYTZYThNkUkbSP1P3UFxEXmpU3m2mcIMzMrJSvQZiZWSknCDMzK+UEYWZmpZwgzMyslBOEmZmV+hcBjD3z0aBgqAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "from time import time\n",
    "from matplotlib import pyplot as plt\n",
    "\n",
    "%matplotlib inline\n",
    "\n",
    "TEST_CASES, BASE = 300, 1\n",
    "\n",
    "ns = []\n",
    "t_brute, t_divide, t_kadane = [], [], []\n",
    "\n",
    "for i in range(TEST_CASES):\n",
    "    arr = [randint(-1e+3, 1e+3) for _ in range(BASE)]\n",
    "    BASE += 1\n",
    "    \n",
    "    ns.append(BASE)\n",
    "    \n",
    "    t = time()\n",
    "    _ = sumatoriParcialMaximBrute(arr)\n",
    "    t_brute.append(time() - t)\n",
    "    \n",
    "    t = time()\n",
    "    _ = sumatoriParcialMaximDivide(arr)\n",
    "    t_divide.append(time() - t)\n",
    "    \n",
    "    t = time()\n",
    "    _ = sumatoriParcialMaxim(arr)\n",
    "    t_kadane.append(time() - t)\n",
    "\n",
    "t_brute_sum = sum(t_brute)\n",
    "t_divide_sum = sum(t_divide)\n",
    "t_kadane_sum = sum(t_kadane)\n",
    "\n",
    "t_brute_mean = t_brute_sum / TEST_CASES\n",
    "t_divide_mean = t_divide_sum / TEST_CASES\n",
    "t_kadane_mean = t_kadane_sum / TEST_CASES\n",
    "\n",
    "print(\"              total (s)\\tmean (s)\")\n",
    "print(f\"Brute force   {t_brute_sum:2.6f}\\t{t_brute_mean:2.6f}\")\n",
    "print(f\"Divide & con. {t_divide_sum:2.6f}\\t{t_divide_mean:2.6f}\")\n",
    "print(f\"Kadane        {t_kadane_sum:2.6f}\\t{t_kadane_mean:2.6f}\")\n",
    "\n",
    "\n",
    "# Matplotlib stuff\n",
    "\n",
    "plt.plot(ns, t_brute, label=\"Brute force\")\n",
    "plt.plot(ns, t_divide, label=\"Divide and conquer\")\n",
    "plt.plot(ns, t_kadane, label=\"Kadane\")\n",
    "plt.xlabel(\"Array len.\")\n",
    "plt.ylabel(\"Time (s)\")\n",
    "plt.legend()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "6sDeyjwNs0qB"
   },
   "source": [
    "### Avaluació (0 a 10 punts)\n",
    "\n",
    "\n",
    "Concepte | Puntuació \n",
    "--- | --- \n",
    "Solució correcta força bruta | **3** punt\n",
    "Solució correcta i eficient Kadane | **4** punt\n",
    "Solució correcta i eficient  dividir i vencer | **2** punt\n",
    "Solució correcta no eficient | **2** punts \n",
    "Codi comentat i seguint estàndar PEP8 | **+1** punt \n",
    "S'ofereix una funció adicional per mostrar la solució elegantment| **+0.5** punts \n",
    "L'algorisme falla repetidament | **-7** punts \n",
    "L'algorisme falla en algun cas excepcional | **-4** punt\n",
    "No es donen prous exemples d'execució | **-1** punt\n",
    "Codi, noms de variables, solució o comentaris no prou clars | **-1** punt\n",
    "La funció o els paràmetres no s'anomenen com a l'exemple | **-1** punt"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "name": "SumatoriParcialMaxim.ipynb",
   "provenance": []
  },
  "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}