week13_notes.ipynb

{
 "metadata": {
  "name": "week13_notes.ipynb"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# Week 13 - Problem Analysis"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "So, the very first week of class, I gave sort of a general strategy for programming contests --- how to pick which problem to solve, general goals for solving problems, and so on.  Then for all of the following weeks, we covered lots of different kinds of problems you might run into and how to attack them.  This week, we're going to go back to that strategy we started off with --- rather than talk about new algorithms or approaches to solving problems, we're going to do some practical work.  \n",
      "\n",
      "I'll go over a number of different problems and discuss how you might approach a new problem during a contest.  The homeworks I've given you so far have always been related to the topic we discussed that week, giving you a headstart on finding a correct approach.  Normally, though, you'll need to analyze the problem and first identify how you might solve it, only then moving on to correctly implementing a solution.  During the class this semester, we covered a lot of different approaches and tools for solving problems:\n",
      "\n",
      "* Brute Force (Complete Search)\n",
      "* Greedy (pick the locally optimal choice and hope it leads to the globally optimal solution)\n",
      "* Dynamic Programming (exploit repeated subproblems)\n",
      "* Data Structures (stacks, queues, heaps, dictionaries, suffix trees, bitmasks, etc.)\n",
      "* Graphs (graph construction, traversal, connectivity, shortest paths, etc.)\n",
      "* Computational Geometry (convex hull, area of a polygon, basic geometric analyses)\n",
      "* Combinatorics (Fibonacci, binomial, Catalan numbers --- are we asked to count things?)\n",
      "* Number Theory (primes & prime factorization, modular arithmetic)\n",
      "* Random Numbers (generating random numbers, using randomness to find solutions)\n",
      "\n",
      "What I want to talk about this week is how to choose an approach to each problem we're presented with.  To do this, here's some questions to ask yourself about each problem that will be helpful in picking an approach.\n",
      "\n",
      "* Do you want *the* correct answer or *a* correct answer? (If there's lots of correct answers, it can be much easier!)\n",
      "* How many possible answers could there be? (Is a complete search feasible?)\n",
      "* Can you break the problem down into smaller subproblems? (Necessary for greedy or dynamic programming solutions.)\n",
      "* Can we greedily combine the solution to smaller subproblems to solve the larger problem? (Greedy solution?)\n",
      "* Do we see the same subproblems repeatedly? (Dynamic programming!)\n",
      "* What operations will we need to perform repeatedly?  Is there a data structure that efficiently supports these operations?\n",
      "* Does the problem concern itself with connections between elements?  Can we model it as a graph, and are there known graph algorithms that can find the solution?\n",
      "* Does the problem ask us to count something?  Is it represented by a well-known combinatoric sequence? (Fibonacci, binomial, Catalan numbers)\n",
      "* Does the problem deal with large integers where prime factors or modular arithmetic could be useful?\n",
      "* Can we use any known libraries in our language to simplify parts of the solution?"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "#### Problem 1 - Hex\n",
      "https://code.google.com/codejam/contest/2929486/dashboard#s=p2\n",
      "\n",
      "The first problem I want to discuss is Hex, from the Google Code Jam China New Grad Test this year.  \n",
      "\n",
      "Hex is a board game, played on an N by N board, with each cell being a hexagon, connected to six of its neighbors.  The upper and lower sides of the board are marked red, while the left and right are marked blue.  Red and blue players take turns placing stones of their color on an empty cell, with the winner of the game the first player to form a path of their color of stones from the sides of the board of their color.  "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from IPython.display import Image, display\n",
      "display(Image(filename='./week13_notes_img1.png'))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "png": "iVBORw0KGgoAAAANSUhEUgAAAUAAAAC5CAMAAABupBb9AAADAFBMVEVXYpoOFVKYKy0ALIcOHpV/\ni4sAA4U0DhSvDA/eBxQAHR2GkpLRAABwISImQEBPSzxfBxEnTU0EIHEyMQG7AAIWCyhXVkgcKJwF\nCgs0SUlCPCktAQUWCBE5UlJsDBhsBgnvHSxGWlpMChUdHCYDDz9fbm44NxkCFlYAMjFseXlFS9AA\nAJO/HCUaIG2lIiTUBxQAAicAAFyDDha2FiIAAU1FRkkjJl0wMTgbGzi8EhjwICc5OTzmHCj//v5h\nYmAXR0clM6CrFR0AAT/aHyglJDKOnJx2hYVAP0KzKCsnAACkAAAtLS4qLWo1OJZCSMdyAACUCw0A\nABRsa17LGiRDSbcAAXcZAADW1tYqLFZQZmYXIYc4AAAAAG9MAQE/Q7vPFhwBAxxDSr8AAAukDxRc\nXFsLGmO9KS3RLTEtL3PoJixES8oBAAEZGBgAAwUzN4wkLpYAPT0WG1kVF04rLn6QDxkuMYgUEgDn\nGiLwGSL2JCvwJCt6e3p/CQ1pAQAkJCMkJWsxOafEFBoKAwCOAAAhIEssM5VnaWmFAABVAQGxERYi\nJndFTcQ5PaDhGiL5HiYlJADY2Nk/R8PIyMZWV1clLIVfAQGdExsdHAAAAjE9R805P6n+/f5KUtVE\nAADLKS7AwsJHUNTbLDHVGB/sGSF/f3/kLDFLS0t1dnQ5QLTbGSCurq5SUlKRkZGYAADwKC/0ISgz\nPK/Kysrc3Nw1PbR6AABHT83tLDJvbm6VlZXR0dLvGyOLi4s+Q6+/v76qq6vr6+u7urr1KS8uNZ3t\n7e3i4uK2trakpaX2LzTg39/ExMM7RMI3Qb2ysrPn5+f6+flETdSgoKApL46FhYX0GiM4QLrNzc08\nRceampr19fU6Qr7p6enxGyP39/c+SM9CS9HxHCXv7+/l5eXtGyM/SM3z8vL1HSXvHCRASc7zHSUA\nFhX8/PzDFx2SHSDX1dXzHyfU1NT1HiZAStFASdBBS9Q/R8tBStI+R8vrGyQ/SMvsHCT9/f3+/v4A\nAADtHCQ/SMz///8Qn27BAAA1TklEQVR42tydCXxM9/r/+/vd/Xd/97a3/be/7trSUq9ybaVK3aK3\npfZS2iqKWoPWEmqPVBBJiJ20sV2aBbVUCIlIQ4IICRJJkEwYmTM37iWzzySfZH7P9zvnzHcy2597\nHa/fy1F6Zp452/s83+15nu/zfeTmkSF3htz558O33RlS5XwA2yN38NBuRc6qBwDwCHpNmtT4Hy3/\n8bBtC/DDCWet+gBv7sIC4MU33l6xYu/tf2/T3/4/s729YiB6YfeDKMLO0wuwcDnQaMboJL3OZnME\n3Gw2zV6NLbD46N7btiDiuqt1wU5+VRP00kdJGlh8w1tcVzdv8uANWO2sUR1gjTMbva3RC4EBvxlt\nq9bZHHX+N4du77b+m6tv2PxL6yondH1j9tUAhztsl+aMmxBIWmc7Wr1t822dLdClj+6dEFhK8OdM\nIPwN7tX2GKa3R4ebqhfiR2qdVUsQbdImLhyMAY91ZAj93qVDv7MrgM1zvnE4/BD4Zs7mdcCHhy75\nBWy7unfbUhzcWX3U5p/ujz2A9RMu+QXscFw6NLpnyx+/Ian/c+9cGr95tuepHZqYoVi1byUK1AdI\nSr4f7a1aizZrGiF8cdEsfZ3N9yGu7h0LpJ7bjX7b9l71ktPvLx06iBf+mYyeY38kNfPVzm3r8ZeM\n/0LLCZcEfqEu+nH9UFyAZezUDl/t1Ixbh1exdOclnc0f3Z0t8fWniJxwiS6kHKNvi/FGaSFwUu1C\n/Ai9oms/IN1grbdYs55kCEdo9PxWxOa4odm5Hq/HOp1VeX/H+p3V/DGFlIrnsmaZJU7n6VdxcNte\nRRdECdvck+A7j6dh2bi933idm5S3B17e73TGfoqWO/XKweLkh3rgj3e+W/01xv7oo6KOb/aOi8fc\nc+dz6NRzvrEpr6TuRcQZjKSCqc5atQHSFfLoddXbrZKlNGvxYHzRZoSOVYXiETWzNwOZ7zhZv+pc\nKvDGbCqoQjpn20G8et3prKl1ns/8E3ocun3D4aGds7f1w+EDTqYK+18gRnu9zk3itBJnLb3INAwe\ne+i2p/jG3h/HDkNxiZMuvATDNs/mSijE1YfWo0sse5B//pEVDtd9OfQDMc2srX8QKvgIe7ADmBlm\nsDKEJuuF54FR622VGp3DwZ/wb3NOUf31MlM/gl3DNeXPp+bcsLnEb5/a9i2QV+WsquWMTiSgX3cm\ndvG58fOh/4fJBJ+OJOm13UDHU2//zVWQbX97+1T3PfhLET83O3UXLBt4Sifzd5B4+0G8XEQyOrxq\n9Qv4cOfPNxSpg+5s4DDknKfbIvw3855G20N76dQEcAb6GOxWy74NKHbWqg2Qrp+GT6ySvZ4jLF34\nJLCubZJNr6ebpNrtd3vQLPs8UxG21dD/zmDdn0/pibDjm9mdP0Sz4nP88Z0uwEdextLfHWKVnU1X\nfei/+/3XjiskVqT/fD/kwwl0sK2Ozv3zrA/xdRqJ6aT8n/NnPqWW6GeqClnZnh3TD39KrmISfoaS\n5GY9//vQ7KsOJtXpT/1OpiuLr1MN/btTVFNqYuJHDTea6+u1vfEDKbfKAOnaVwZgulTPNrvdqC3d\nFwo89+L6ERrN0TmbDw4tuHNTAeSUbzV50vyxE67q9Dsjh/71SIVTpqtQiP1rz/nj9h6lAtZj/gd5\nFe/QIwqp89zvcZBVZ0fnjPt26O/Zuas8Tn3+5O/x7TZqro9WHvrtsJzT1/i3Cv4TW9YM2zNu71WS\n/tij328KDrAXK8TXjz3LTq1ZjydLjfZ6u3S5Pc7Q8aproLMAG7IsZhfCesliSlwI4IsZMTtJBWKd\nnoDkD+deR/y2oz16IlO+dyGtYZDeR9e9c3oMxfs3GRcv6ZDXsW5z5Zxv0ewO/85LfOYvrLmeMHaZ\n6+RCzHZvZjSjZqxywth1eP1cw4PZsQc+xfxxbz+GhVr2LFZTOjqp2xd8xHXlm++xrgwHyAqy2SAl\nLuwJ/GHo18eu0VN530FNjfO7ok/xB7z6T9IfLyn/fVU2DlLTUiS0z/M5a469gK4HmyUTXSEWCI/v\nwMGB86lp9rl0bRVJ0zBsIBXeLd/RfdR639c7mc0w7xWEmaz8WbTjkc3JqgqQrpCHDfss1nplM9db\npJ8WvodficLrQ+F8AvJqSCsCiI/h62NsL8DBOWh2MvC5i57BM1vkku0L+PTr+GPmeb9H1zAdBaZd\nluxcBS3p+KDCWas2QLpAGnrzdkTZqF+ojWpd5DwvLu6tC9koCWQwou8rkCf0y/fga8gRuutLofj5\nigB4nazF7cJ7TYEAZyKu3Ox6DK31E+yoUpHgI8otnwayFBVUSvL3HwcejfPuo7AX+TI4HqzsEANk\nBBSTILVXVUAx9RgP3yRpwHd3HaXldvkhjKHAFWeN2gB5O/JeKWv6xWbd+nkQgDUcYE1QgLX3CFCI\nUxdQ3RtQWnLY76sTynBWAWg2FE5CpvoA6QoVX8hdGQHw+38XYM2/AZA6KEE0sCIYwJMCYL3dMAUd\njqtH8BFxVznY8JPB+tABlKy9kUC9afUB1i7BeOmh08B6q6G0A/LUB0jXXU0qaLE+bACpJW6PN+n3\nagOkzm8C2lNX5mEDaDdErKQBXZW6AEVXxvzQAZQuf4JiNTVQqOAasspoHzaANCLOAk7T9yoDpFs6\nRgM6k/VhA8jNWgk06lQfoJMMgzSKfNgAmg2Jb+EACVQDKHrTuzD+oSvCrBBPUUsFH/EaRhahca5k\nf+gAGvbNRBFJ1AZIo8wPEG2x3g3A2rsZC/8fAcjtgmvIsqo2QNq4TcGuAAwS4MTMWTcDimucJ4Jr\nYIXqxgTPzWw8y4YjNaoDJNt0B0yxWBWA2cHMbjkQJlFfg985ZAqDsq/4PAGsEgd7G5aLOwhTt++r\nq0ooYdKAlx51ttxa33CTaDhCKqg2QOKRjAXygM5cHoECYXX3wkdGe+BYLdv3J765AwtWO8XBXj6V\nd7bgmStcm/yKz+1CUSBzNokP4IzvqYVTJRuDvq9vSNBsidigigo+4lu2OqC3UnHYL+C1PELoa7e/\neeQHpGV0wZennd4Ia5m4CD8kX8TcI778uWdo/6toE/+nLdf5wb74UnF4B3bHlvgw4gROZIYAabEB\nHCrX7szFLvxyYr7VsxRzB10nMmupCVC4R8LkQqwtT/klns2r8LhV7sWuiZ2MJUdIC4t2IblCURXh\n8DgG7KZogpMXgViOtKE4rxni39BPOAgkX+PIGhCoSAUKrjmHHEYHUUUIuleKgdQTGcDT+6u8xXTu\nLR9g0uqSjNe67UuhaAvPhvinXshRE6C4iYvorQzorNr8lP/BE6knmEC4hX/AjusytgxidZp2hbSq\noDHS5K8qkvFlrJByAtkUhDHu0G3H1R/H9cczOVc8xEyBkoGMEv7pSurTcjkW4tM7QNVKLf3uyJtY\ns1+8WTlqYg2WnD5PH0pS0W5QuZFroRjQDaBADxUBikYspNRgVRwjm7ZGfYYnVtdSrS0DOrMLsr+N\n3XNRF6CY6aj8DPu/ZMw4cO4D3oXdzIGmEDiZRj7hHy8ddVBky9XZm3sybSOuMt2aO19iB3fU8yMy\nkTDE6RkTkQ0UH5f3q7YAc4WOugJHJh1xlRFC/RFajDRJ5gY2hVQ160Chg7sxpcwufEtSftTnOMzL\nMavAd2BNCdtXVKoqsxd6naFveNuRA2TWuGu272qc51Oxq4hJORUSt/xRzwJraLPd0E/oARyOVWJj\nzu0AMqqUc3P/GlKP056sflS7xbLXpLg3L/KL0c855P0/4OJxfiX+uSQDmBJlciuh1ZIlYo3UBXji\nAyR6WFbtZuPEaDxVxMvkbqYDdJPentiMCvaBVX7nvKvEAwuQWsEZ3aHgoc0sLkZEQl7q/p9AMkde\nVQxcFCWaK/HxApJyXz3fzWRufo8ie2YSEipc/vbYHaR+Mj6h7eTg1FpVNGsRQH8EizFe28DDWW+K\naocld5yxwEXmkvVxdSegU15NxVz04somhLIucMAlRKBH54bBhw5COPY3SCDFupKAubG+bcqBuUg4\nQPtFwNwh8qUFoysX8UE2qzKzha56HEw1QnRKuVWpBfvwvqCKAIVxf2YWN2sJJSwjJcRF3vbW+vQt\niNFuIKEX8vxFMrCIrcP4YMvLaDOu0q1+DooLl2NMY/4A5BCBLezHvr2+/YT/ZjI67ReX9lRCoNd+\nCqpLOClenbjwd5n4IixfK/uICxew4ZHqAHnY9OLLfEAnEGpNUb2RHaB3W0XlJQfFVwL2fati51Lb\n+7YSwkvYdNWVOjkGU3NjLCEsOBEoWONKAZ5H3jV/Yqb9mQCpMIUf+BUPKcDaVZJdcXF2uuKsVRsg\nXbYIM5fLHjrRmOR/9UTAEVQtG/xWBAvW2D/0VKW79Do0mlkjRszSuYOod6Ig2KixGEK/fKVXenWp\n8QtfblwwvNzs0RDXqAdQ6GAGNohCLFch+Z+tDBbLcR3nghm/tgw75BD8ZvXvCYS01TvkoOadyAlm\ntyieVBVQTN/vSqNXF1B8HIVyNWi1xLFasEZ1gGRT+IAKsWT3BlgRBOA5XAkKMP6QzqHwi5mPGUkx\nkbcUgBoCGMz4VYxgrvGqHy4GlNFhJzlA0RCrWgcKfeqAhUTwHgF+dzcAHbpZ80MGVms01VSE7xZg\nMOtWTTCA9CgcoEywsDGbv6Q6QLqrZGxoEK5lv28AbfqOaKPR1dlsdQ8aYL3dMoVNfVAfILlHeqG3\nVK+GBtZd7Y9bK2wUxf7gAVoNicB1+lJFgKIlDg8zmO+/BlIJXjd5e8f4oTNG1OkeNECqBXvjIg18\nVAfodAWtqqCBDk1Sz/jHhkVG9kRXveMBAyQVPPse602rD5DcQr1GrTIKo8J9BDgUj8WsWLEIzydp\nHA8YINmmQ/EBDehUBCieGX0sdjU0cGjIwMpZjqsH0VZve9AA+fylggcD8AqQaDCrUwfqaQJtf3R9\n4ABp04opdGoClGchSiq0wrp5uKW3Oa6y/z14gGbDTwuQpm4dKGzT4RRsdL/7gQ5XP1Cf1HNykt7x\n4DXQalor4hTU1cCSXTzk8v4O5XgZxnod6eF6zQPuxshmrbONcZgs5GoDpCucwYYLBvvdGxNqgwIU\nI7ek/ogfGh9p092HsfBdATQ3MCwZLszkkxDVB1hzGJModF8ByMxZQYweFcHCBVYP+1lnc1sT9EmR\nkUnVinnLptvJIj1qA1tjniZrTFCANXejgaI3vZh3ZdQEKKJ+I0xWVx1oCkWRMAr7+LvPILkq8Oy3\nmmKM1SnuEAKnr67WuI3TuuptSKsKYtJLw/UAUk7hzYuBZ5U5GcB8SSYoXJxsQKcmQBHp0eGsUTZH\n5n6GYj+T1LhPJ7PLzNZ4Ko9Kmj+T/onip9AEL7Z16N1KaBPGaX3n9UMn49nMQFEk5C9CeF7A2YUH\n0rBBcaz6iqv2L8FbFy5brA1sc9J05KjaiIh2ZI27K2PX5ocBOeTC8XE9lBSjVVb58G7YdUdIhXj/\na2idmLsceHF7pc4rbwRNPe8+H00LE7th9wmB0DOQAcjatxG7jviN5Ti/G7jwFZ71MzWUZ3Eg+GEt\nsHGfyVMJrYbcASxsWnWALCmKmAhrt5aPXI5HuSu2gcOj6ClMSSmvNzDHUwHVLZ5i7grdmN7cKEnR\nixHe1iFy5PCyXP1SWyC6udGY0gcbMkpkCqL0DlmD3iMtlr7TgR2nFanQzpNfYvkgY/6gbkjwAsw/\nHOmCKSNp6u40XLhs0po9WuIpyHZWqQ+Q6BxGb624bnl6a6QxgaiBjiwhQEa6O7PWMHI6Vu4XYh5N\n8BqmTDTUm831psuhoyirxAqdQ5Tel271w5jhBq3ZrC2Pa4c1Z6oEBbn0RktG8u5ro9/CzGPnvQJB\nMkKQXk5iw8QpQM41ryiS07uBdFOZna68FhvD6kW0jN04Egn0I9UB0g1lYqWYPWKvt6REI0EJq2Iq\nsBuY0tdgt7tc8FI0FUXZA1TLM0FQkIrF9e6tkilxMYa27awnLeT4bnf/FqMuSEaznQ62kwYPwA4e\nAiEXz2JgepSlnknrDav6DEACD+xwT/D/EmOi6N3U07sz0rt79g4Hp/j7+dEUH8OvvK8JphUajXYF\nobQQWx4EQKpFloigVdrMVtPIdtzHzUtqAQbERRkluyKlchwGV3Fi+FKxcdBE+a45o8vDH8ey9THV\npIU6hq9p3CpJMssHS8a+g9rNzOHBMa4UKnFRpH6y1GjM7YPwi+zKtJF2HsbnI+nkSrYMadDHLrd/\nLf1H+FaOymJHK1e2Fk7F1ESTVq6ODCLQQzWAohaMMHnWwFLKvgGgXCc8gC0rpbyMA1IQUkxcFpBH\n0pJsICLFpX7Cvdw3tBXi23bWaDqPxsaIvuVSvTCZkTjlMzxLjKjxyEa7lPwGUsk0sil4AAy9m4tU\nKLcateLN1hu3hrkCnYhu5hP4LMrzaLNkMJL4gt1itwsXZ636AGmT08p4Gqej1gL7WRlJz9+k4BMU\n8qOmI/Umtb1jBuWXmblYHKs1DR8PzI+JmU+VX77ExGYr31zi/EHtsOO488yjaM3LH33n3kjN0hez\nt1ORMxOhKUoQJf1Cua8WeJZCPSoyqOLYquViceV6C/UEpiUa+LNYTRF8/pL6AMll/h5CveZil5VH\n/Q96fREWVea+SbvZvWctk6Jav4ZfR000Ko9IjNy7xvrh0U3ih/1iuNkl1hoMFvZHPtg4MbHdrsP4\n9ciJrrcmGfhGv9CSBhtWUUk9/Ozkd6MkpTTa6Rf1fN9qlEb+Ek/tfuKLRNel2csV90fiwuVYXiox\nibGQRsQUz6A6QCJ4BjP3GcwN1axs61qMzC9zV370aJIQW03DceF7UcAki8lkkexKYZNI/Hhzg0us\nNScmFrI/Vncx/741EpWjtbkuKf3IquUV5dZo/Dolv0wunoSPfrHJaOcfqBxTMN7HUeV0sJmaFoNb\n8Y0WiWUjMWbhgsnsGhGvZGHT6gOkOjkB0xXbtLDsXggvdXdOtRaTPbFQlHOrVBoeYRGunL5xFy6E\nWUmuiHPDQ01WWZj7JNj2xWXJLD+tYXrjeq0STTAF8jZmk+RiYW6/yj2ysBtzpz8NtDhLBJV3N2kV\nO7fWYJIK97mCbSWTVBpGU4hIUU1TCaA8IubRWmoCFAO6T3Ilr6rOdAHuLBVae9z0afjKZBYTM0rp\nRSvPaEifyQGcNYqnxlqLjItgTs2KoD+XJbe5ZDnRVBQsMSKLbe3xrsEu2wKmslIoi1ctxpis6ehG\nN6hEQ4PETLEvTCXoWqbTuVlTw+Eak2qnEUB5RBzCptCpD5CCG3ehj8kaECBNIsDGaXjXCyB9lMXR\nLfblJoZijNVNhQC6NXBV+Np8VsTpgw9A2owmkpn6vkWIBECjIpXG47NNJmoRPitTigYBJDEJwADS\nAWWr3sK08FYugBIHqETu76bHUxOgcBIvptsPBNBuDMsqSw8EkJdwC9WCC7HPYPUPULpMbUwAgHaz\n2Ww1hioKLgDyfWuTjZeNVm3fxSC7mwBo1tqnfJXbt/GYMnZ7w0MLV7012QsgqeC+Dcw0rSpAkQ6A\nJjAFAMhbSlNcYIC8o3FZWg4aVQfQQINF8g9QCclYi7OS1Q/Ay0823URVG+nbuxazB0DWcFlWTWIA\nuRavemuUN0A6ejq+pFpQPYBCBWPRuFQQ9AFIPYSgAKkXayqfhrN+i3BueIvEnxJLDYEB2rXS4s+o\nBvQDcNWT7TYZrdby8fiKfiAA8j69ApBO4A+g2VD6Ho45a9QHSA6Ei2gvCrEAKJ45GEDtqsLCsOVT\n91Er4Q/gwqktpgER2oAAzZY+rQi+L0Ai2x5fbSo3RYf7ArSXCYBlvgD5hUK5CqoKUAStrhVE7g0g\nPT8A/JRf7wuQ6ycNh2lSuWikBUAZU9/Gn7E2XQAU7Tm18P8RMb3V1H8JoPHse6wvqCpAETf9Ht3B\nvQJUwvIisqZPG/CV1gug2GiAF04E/AM0G6KhTD8TABUGiQvDgbAprA68R4D0PQv0OO6sVQ+gUMEj\nCF9o1P4rAHlH1mRYtZg9YwCAZPFb/HhZAIBaqTf2eQMUV5ZKCy/n81/cO0Ap9xPsVh+gkic0zGj/\nlwByg4ApmvXK/AG02l0AAxRhsyEuZAz1sgMAtNYbjYbhk9rREf4AaoMA5DaFmTjirFEVoJiL3dto\nD9YKG4iEP4BayWxmvwhpShh8AdI4i4pweoiinwKgaCjCTOYAACXJbr1s6qNUgXYFIO2xVngTAeYN\nMgGUrAKgqF3ewxLKL6AiQGFTEGYtn36g0UQd6Xyj0R9ALWmfwWDMD8VnRj/dGEN6FtGKmymYCYDy\nD8KZevkHqM210khl+PPuX4h+oMHUd9IYk8VCOmikkcyAs/lk+VUAigZ+Lbesqg+QujKHEW30C5As\nJmf7YG3pT6U+APlAYFpYaeHZuPCNZ/0ANBOfAdOeRLcsgcwLYChXL78ArdTBWXthbUiTQoO54VBO\nW5pYGDezaWEhGXHshYVxjRFW+FOu1hug3Vi6GHnqaqCId+uARIPVA6BiPrFEYBQm098WZe4sD7hg\ncetnaAgAtGAdSQHQ3SrQUP9CxD6rMUBHmuTckBVAA1dFTJ32H1/JRUMAtJaHYgAmh4RgYylrv0aF\n0P2xVowBtDfIiZKOJaQd6gMkgtks674AmGuyuh/RtSkaaDWWzuzjnnWvNeRmRUT8pDXa3eLLM8mc\n1cBcQATEMy1/sl6yeoxjBD9Wn1nb5xpJqhwsSZI4mlljRpGdTdwT08BSefey1l427QJ/dWIrbyHK\nsMoAT7Os+3LJI4DLc01ycgejwcJtxkalT7I1At3St7oN0gwRuc9k40B9OXkvuo00ae2ymJvrPXIw\nN2+BuOaScEJ6FjmzdevwUen5kl2W8kZC/sB38uPCh+fTIRK7JyP91cr3R/9JVkPK4inf84NFj2EQ\nUtXWQJGRYrFVMSqVLmfDL8Wh6dr4vt3IpminPYrPB21lrlhFrpRAS0p6O3TBxriJRq3QBTcBQ/PE\nxzEUv1jVXLL7SqVySkIAfDaSGixvMbdXT3y3CZqElRvsZmXjlNnNWa1lzUe2Bvkayo2enXhpKlNB\n9QESwS2YecHdGZZKIzC1kN5qwylh2vKRa/HRydqbQ+ai9aDyTV7JlaWJfboh7eT5K3PRLVpSdFSY\nssvTH8fSETEd17V6fLjBW6q1RE0ZgMyKAmB8ug9+MzmPpzcJ3zPwW4xJt5QpUlH2TSPHICGW/FVj\n6L48+rDR+JLHz6kPsPYwS1UrE6Tqp3QjLlhNDKFwG6eEgi9SQduWR7E2pVxI7eZN+YNa4fARJqza\n8hp6D2putHuI600UwxF/6yW9rvql34Y3nWjSklKLc1soAIH7fp0nU0HhJC7Aoi/avE8rHEzaq39p\n+3MI7WuqNzcQWyh6BBl08LXMmVguDrYaz/ZiI2J1AYp4t4WSyLpvyG2BLyIIoV1makhJ38hzevBZ\n/Cz0p1vcVoURc/tG4DWekIdJmSI9Tv4fs9t12zy9KdZ3rqbZ2Dbd7c4Hm0ZPZM2D8r6aD2qNuSxA\nhoe9HEaruHyjWRGbpfK+v6Ak/C/p6Wh99xloum9iuSRCKgxbqfTuYAkJ+BRkcppulV2uIl5QbYC0\n8QGdQTR5RmNYC6pyLhvrza7ogM+RoARYcIRHPsIvR0qEkIXO9E3vhoISj+VFzsx9AlkTDTx4g7SP\nwhbWvSEHDjpslSxsK26VkQOmc5Mn9cvVchgh+5v3FFWFFskqw++btXFo15dcS0LZ9NVvkN85ri8/\nNbuzieQN/egYuzM5lUDCqHejyEUse0c2IFlVgL7BRqLaYe7qjYkmI1V+gxaiC+FrkDfCWTSTgmfo\nOY3lhC9NDjAUeYjS0Cq9XLJS5RfdFOs6kgI53JFvLw1cilZ9KP8Lld5B40l3RXART7tyDOzUdtos\nq6Y0wZ7OhM+djOGlgfPRpI9EgM1ay6AxePSYmJbNtDAZ6BMle6a1CzHgBAnVBCgMg+OFBsoLkFDY\nyfJC08RQIOO8G5BY3qIYo/r0NY1sgdfOyMrpCXjIUxQDZDJMvIDnRnduuCybjqK3lqHFcJMxP5pV\nfl4plHiAR1OqRqXyuCYYNnCvzjNyjg5uO5QB1hqb09EZ1zyOVrKsjBq0VbLyqQ+TWKyRugCFCg4y\nNvSymy3WtUBEN552o8pPQqstu9AtAkj1TYvAwzPTgDCKnprB8MkIlOjputsvdQUihn/MF58SAMSp\ngc9L+65FTwr6Ug52azDFvjIlpF7T4XPiaME/dgnFJ1nsLu/zEvpORYCC4JUn2k3Uenc+DIVrReXn\ny+ja6sNIFQrkE6V7EVT5sag3JSUFPb5DoUDlGCuzawIlnch+alTTwaO789hXN0LWDDkcNr2u7VJM\nxUdnWHokv/f10ag4l2+lCe7QN6oCFAO6aIvZJyXFWZBlN8AdcCX0pSt04drXSw/pHSKIX6ejvwpN\n/c9Lm50LEoJesSt+czXBp02vkQGyKHY9Heugcgw/8dUi1VfqFylapoLRWCIiZdQFeB2tSiXvSI/y\nn3Al2CIfx3ZRLzKwrfHrPT+7g/b1MaMbPTbvlkOnlOOfv/3T+SDZRt/59ODPTPU01frtA5UpyCMi\nI7fr6Ay2vb/74mbQ+RcbUyQ53E0k7FQX4EmEU0oPPwCDTLQJCrCWA7wh49IvAh5bB7SxyQRv/Pzt\nX4JNtDn/6cEf2cExHedhhp4fo+sPADPoDDf2/nnyuaA3RgB5N2k6H46oClDErPYmy9S9AnTeHUDK\nCDAjSacbMR/r9XcHsIoBtOm3A/GuYxz0DmYkLaLUIJSZgQBeuRuAhsQFSFYXoGhGOiHUYlYLoGMW\nWxNwxQi80tmlgra7AzhiRtJ2DpAm4z23vlpTHbMs5Jb+bgHWa8U0WPUAiiyX5OK0qgSwTuewUT6o\nJA7wbjWQHaxZwQHySiBJT1ktRmP93QOkmdgruYNOfYD0vF/ScESrFkBGzVY9Ai9Sb+YeABJ0WQMr\nR4OSCfD0KrobdwmQB+7zoF81AYq5DzyrjEoA+TDixkFQYqN7A6jnAB00o5sBdOhH4LHOR+8aIPkZ\nFvN2RH2AZFnthPbaehUBUvGboVFGFHcJ0OECSPAbcYD08ZUY3d0C5DYFHvSrKkDh4lxJkQAqAaTS\nF0mJPagG/Nc08EajkHsFKMxaNKlcXYBiCasyya5SHbiiI16hZqBOALw3DZwPBeDdF2HFrEWr0KkP\nkK4xpDFC1QHo0Ok6PtcmSS+WTL83DaSepLsOfLHuLhsRka67QM1GxHca530HSPxs89C1WscnFN97\nK6yxkSU2kgDybkzXu+7GiHZEBP2qC/A4eEaK+w+w8rdYX72iurq68h4BalYkYf0K6oVrktB1ha56\n1rLJ2+8NIBXiaOSoD1AkyDNZPQCeuw9jYZ4U5bmukaMjI0e3tenuvgiT4ibF0AguJinJVqfpP/lW\nTEx/rL/roZwI5Wz9KFmV1AYoQi4luwB4PKg1Zk3QifEeACOXNVo2bNiwZUPb2IKNRMR23j0W5tvk\n7RpqhwGEdNXo/n91YG1DgNystVv1OlCEXC6X3BpYSAPJqsD2wOw3a4KsEHKz2Z7ZwhhKXWFdHf2R\nPzINDJpDlZuzdLO2y9ssnUMX03F0ZJJG52Aa+PeKwGYqbs5qEI0dxocjqgIUOePFImAUgoWnYgOa\nnKtW98KOioDiKzsQv/nnoy6EOuWPjE9XnRSP5HfIERTAoHomZF3nahuZruWN22SrK6vZqM52dfZY\nFPleWPiWCjZ+33BMNV4sYKUuQDIMemYn0w7fiBzftBH885Bd+KALeh3jc/J9xVuAtGfw4aG9VzlC\nh7K58NlGY/JvyBvKaPnL6fE6ej69bDvh4jZp+lfJCkL7usptewAUi+z/Xpe+PhfkFtlqtXukRBGJ\nodQFSFsepgsPnSEqotUT2SIfu/BaFKBL3pWSMwnosp9h8HoGmrV98YjzSvarw3rsvHRUOOUYBmpK\nyUraZsT2lvg6mWUS8EmokofBLbsvaoT+IzTeTiVH3aUJY8NRsD8Vbx7zybHOV1bIBLLpvn6Zwt2b\ncszPYqyhKld1gJzEYYwUYb60+MhXWHnsvMfq+/ICD3muOuhYJyyR/XYi7UYqUMQ/XXsfPcceuu2R\nm9ahd9xqBDIq6DUrxsUDxfKpRb6QY3/E+p3VGn11JDBvu8snKsaDc8at44sjOM8l4Mv9/Hqe8Cty\nXFlcnEeepenZMkIxIlYVoOhNj/ecJbwpn/IpfHTaMzHEEMWfW+ta8QMF/O3L/5TkkLhECQS58wMl\n9Zh9yeGQXZr6EeuA0UnkLae6bMLY5yiVPzur8Aq/jmWbWX55+mnMaKBjHc8mJafon725H5DBsJHT\nKg/YcYAdJtQvG1jCakf2Fp/FxyPztWb3iLgTdWXUBCj6b28iTrhH+HTz9NbIKbomIzl9EWlHauX6\nhzMqxtwzrtAZUs480G+VBraWeRnfx4fbdKwcO2waUqtho0cokR66yu49BiPjDrnOXOc+V4xlPSZU\nunDbNPoR/dFokc5Vjh1Xb4/7Fi/wUi/n1M+YhILTIp3Iybl0Z1VcRJ6lE9kJ+Goizw9CXvawBchR\nGaDIq+Y1jdOutaRkbQRf+I2vPpLpHelxBwC1JrR7DCzYR4jfYTtHgJZzLtURvqQ2GG2rFs5Om+bS\ntn8Ahw/wrktFMbDn0CWdTZR3/fZGrBxrqPW42p1+mS3aHfa/E7uBtJvywk3JgEcMCoOaSRGhrlAx\nuymUz8RWHyBd/wDC17raERGElp8SDdzhy4hcJJCi1hIrq+w6w5IydWIlqKGYr1szf7OuMiZyMCJX\niEgF3iRfvU3rPrBqrSTzGTQaN1vu+CiEqx2jgdExep1+21DMvc5O3qDHUtQJa1aznvfqBfSKxaWZ\nEtKFKWxwZDlpg1kq5RPA1AUoAj0alxq8HEyUwehz5HRBFwbIT9MTOxcoWIJk0TI2QJhNFG7FI76j\nxl2jUeI3XlAdl2b1eB5vnlmCoT3epspSBCFwsY7XmpETWqIDX7DK+8IlyUwJD+zCgjN+GuWSbJ6p\nh2b9iEy/KgIUkxCFCor1W7Yux6QztX74uZ6raBdwIGC/+vhFPD244yy96M04kmJ08i5fRAg9Jiil\n16FhdgeNQy7Hto5Dn45Hgsjm5rM0DF06O8DCMVStIt1IeUVIBZPVBSjeaioFDLrbEZGxNssvIHGr\nuOMrFS3kr5ZtI0DCQdKfG/qURYTWv9JdSPVJHSMpCkER6yo793tBZODyXXunAMV+uvtiBaKP8608\nhwG7QTUBiqiMTqIdETqY/xVZt6qCHIXTwUwPf/321N+EQVX/WyghB9xht2hepUiGuagnei7DZDfB\nWaf2/IquEPDUFU+fCBbpsf/j762uabAJqteBYinEtd4qaCaA14Ov7nogmPivS0/9TTiYkjCv0Yxq\nT4Aat3LalqHrLP0itxO57sapPe8HM1+dC3Zj5OwhgO585zVqAhTukTQsoMBztQCSaabfKzHzBUAH\nAdR7wG1zW1dX2T9koN4mADr/TYDcNE35zlUGKGwK0412tQCSh44yx6/z0EBvgGSJqezPyvB9A8gH\ndLwWVBmgiPSgeDd1ANL6QZhRfWNdAA3UzYqfPLCyOoncR8p6L/cDIG2bxotpsOoCrGUrMKWbrCoB\nrIwMIQ9dAA0kvpF47lbSusFMAe+fBvKkMjPZPaoLUMSs9ib/kgoAidZ2tuyIzr8G8k8jegI9Y1bY\n6u4rQAr6fQuxzipVAYrsZGnoYzGrAJCljX9RQ1bm+TNW6PxpYJ1uRP+QGf2HridHsAvo/QHI89Ty\nxFCqAhSXZTPArCoA1PTHsnmN5s17blijrgoiAZDVkIMpCLB6EZ6LkcX3DaBkby8SxqsLkHi8iYWS\nKnVg/2XL4slHN/i5njQW8dMK/xZtV9gc1SwU8P4CJAddInqRMURdgKIhXpllsKsAkDk3qHpbN0Nv\n81cH6uaNmqWzsZDKNpq6+9kK80I8HrtVrgNFQ7wLb9GA7v4D1NFWp9FRR7rObz+wf8j2FWTI6sii\n4e6rBtJmXM6DftUFKKwyG2jxlvsPUHbPDaPust+RyCI8tl2np3Dogfe7CJNpmtLj7VZdA8XKGeOt\nKhRhWQ0jb2n8j4Xr+iOk0bz4kK66+9uN4Zu0HMzFqSpAUYiX8CyXAuDxYNaYEpwMKK7l1phZDXyU\netIvoXVt9DYhShpxa9GIGI27l8OsMTW1/xrAqgYA7VqriNxXD6CI9HiLEskoACMgVqT2Y1E9jeyA\n4QL0d+66nZd4yn3h4nTv2Fa88Qda6J6+UdhWMoOqIv7m1J7XxZV9CZ2YRMb8IBOXCKDwslvEAlZq\nAyQd3CFmEtsN+75AQQX72p+9tCQPQLL39EHhd+oCDGY2Z07F21k+Z1s/HNz241VZyoMRbHyfe+MO\nRUKeMu//3STjYgXb9S8tmYt0SsBs9VzAajVJVAUoHEwQyxZIuVmtXks7Qu/c5y6vF0xCzski9Mrw\nsaxzB2QCDg8pehNDW3ZWzM5CD6++vXkpXi96Gf3GzrlqE4AVT/K2lkORkwwUB/C3HFuCnA+QJkqH\n99ounVLROro5TXQX2d3IrKUqQLGlimUL6NL5LD9JgTzPVJSRKubYqXByz0cnrzVA2H4GQN+S3+1N\nzCC/kSdCCpTZNg9/z77mvHbsBczfVqkAVtRv71gg7SSfPtthCyPm/erSsOs0dxemnfYqHMxdmApW\nau58hNbpSiIHqymRuzjVBShqQeFg4mnxo0J5nEKNZzDLXFyMZc9GmnnkB1z0EMtLNPDV6llMSCr+\nsPmS3qP2uzShB/iqRFUEuIB7lkgqCvfOGVgiL/tEUmV+siifmUBylbJSxhFxYTm7A3NT8w5F9mtY\nm6KkpdGOZy5OlQGKrswnIssVISzLT++GDB5LIDyHRfxx+MMRI+TcpD2xnj+KRPRAJvCf3eWVrFga\nj23LsINT4dLj/9ve9cc0fabxLLmbOzXnmbBsXPAumrBojlsWzbYbhlsMwx2VhHHmSoyHmrOxGnUh\nmzspHpLBTmoyTwNhS9xZrqOcO5Q2KNYVQqFOqSzCIcjhgEuhIJQ6u1ptu5YHued9+y3P0V9mJu9l\nae5L/AM+Pi98P9/nfd9vn+fzPo8OarW2VkQ5zN2vKwvhkKJJBzxvOksyLgXorkoqEqZoapylxDrn\n9GxIuBDkihNswvNvn/SBjo4+CCOQXHBxW+yHnks3UZPFXIqrMRRweZievJM3bPn7VUk604vsDrFM\nfHg4J05j7mZ4dq5eZXwRftzJuAi7a297KrxodNQjhf4Ri7YFfn0PrcKMOM3Pw8b2Bbp72gDauZm0\nVAyBYpCPxteVa6jmcFI5ESzkwOqi+HzkgmIJpFUwLLkkyRYrdTLGwEkkq1vSqdKkNZ1jPorXMGow\nC8MMkF9AkVZlC7iMz+TCEWlnoPVAB2qt1RWwqxqa0P2CfEBC0VjXG9rGqsP7CsHNiF6XlB7nQHGK\nUD5XbrwAz7GGG0z0++oXhIkkENfhLfC2RCDVwrr04UsnzVfHuo9uuXE7WuLHlFM1g6MdjQd4sxqC\npZ5C5lUgy7Zl58MyrlKKgO+tA9lWV2nKmeIuWk1pRTUfOFfXM+8s7IchBpM1l+50XgYzuv9ktaK/\nuhcNItL7fS/87rNLnm89F09CGxoIJpACg4uOgEn1ip57CbagSjCmTpRvCIotKJSJ8eYheeF6WNYT\nC8Z/ddugsmoprqTEAI08P34MoPos36uitRzomAowm9KgMQoNrbJH4Pc7fN96b35MgUGxBKLnb8QM\n3aNIpcfEP//69IpJoi/qTx3GZ4xwHBlzzzH+sSaOECTLNLOqg8FxjI/AkeGYMP/R4JvQRxVlIhn+\nRoEi5gkUDL6KrzJiCaR+pn8kF6T9+G+/uJxILjAKXbQ2Rt9nnxxlTHHR+XNtxE80C8MwhkzGMZ7l\n5y/iGw9i2zWfFzWrjcIJJNVv3vSjyAsJ/K0zUSQC+p68u6vzMd1dE/ft7azBMeKinMBp3ytQg4uk\nWALpV2J1socxCAwm4OA29AnsLzxMxk9EoM+LKc5m/E4sgaT0+ABfZZKJQPYuSI0QxRFIZ7HxDF1S\nEei7j/kl0hqJIpDSIx9gf6pkIpD66YokkGK+G6Hck1QeyAqLP4t6+VnBBFKO8+hFry+ZCOQ6hRqM\niggmkLo65yWXB6IL7jhI2RFhBNKvPXDL8zCZCMT2YdR4RCCB1ArxQ68vmQjkikvSdQsjkNIj5dNJ\nNYVDBQbbRG8iRAhKLr2+ZCKQpTipjZ8oAummquEdlMokE4GYZX8FFBTcF0zgfBvsnfgOwYTvP4Gh\n+nhtoqcwqX6l+m5EYPxwVpCFsxIVhuireByBn8Q1fnw0ZjbRgej/Vn9P58HL+IcIJpCqXFJMAQn8\nwYoxihlH59qhPyuBEEQHo/HCheynb+rwv8WFx2EsfqwR44GKRPFAE5z2SglOVq77Y1SkBEUTSJLL\nP3upEEEeFBc642g5spqLt1ekD8cimHf7zwHYPEwcLYaDrKVBXRbCMRnoHd9Mx0JjDD65GQZ7Yz87\nhp6HN8ovTnukrgXet1l+aVYogRTm7Kf0COsIv6YSXu+MWYz83jaQ7ctugbYOggnF3Fp+drZ6pivG\nAUwGn8X2GSmwutMZtZTxfFs6tGzaP9NIAonIIuotMlg5yL+Jtu6CovUA8l9+xXpK0KuMYAJp8aaX\nwelyuGvZWhbqRbBYENDbCGqNpcRmSYG1jZOR9e6d3UtBZnSMGGWQ2o2eEikEMa2FFKPDkF0G6+4t\nDE0Zj/biM+/r3dpKSL2+kFQh2Nm5Eh+dQVMGzdJwhPKTm4jOvbZmv/zZ977yTqBoC4P7JHcjAkX5\n4OdwMhSb9t3fUZB7YsRg3APPm28jRufwne0rYYPRVR/w21XKKliFJCEavsWsutVQpVTZ/f4SlbIW\ntvXQffK76Pgh6rRUqJF26bGewrLbzIj4CTanQ5URrW0W5XbImZSMKBmVjvoay5TfYT0O207xoQnl\ndSo0lqk594lDBQBpNyceeB5ib/ijdPZBOIGTOukI2IRvL6zHOmCtdxqeyb/cLWlWWDLOvK5IpjWE\n5BmBgVKlrOxYHZuqUoUKRDWlA35JGKOp/GmOaTSsC0E4Z0XVVj3XaPmnBhoyWmq6LnAkNPa19Nom\nDcJobB9peK2lJsfEH1o4ob+utknJrf2tmZom9ebBT9AujF4w1+RvaHAw1DH3/qElAOVXPnuAnR+u\nVMANwVOYXiB6AFhs2ue9VQF3UVQaQEeypgCcH+Oz7Yu+me0pRstCvRy/fcCC8MH2UA2Dya5cRN12\nv4S2Oqw/qoTV3UFJotkGZcutBntgQRtjXa6WDlMHsSDIUrlMb3WE4VaVdTnq4pBCqeRHP8j0loFW\nhBnBbuthGaQPcgzRjvNQhGOXhNA5t4N5oRyu+LzTnjwgiasgAmmaDPGWuiycu+awLcDvs16vfQuK\nb+B8GiyGJqN1Ud0ILLqDGheuPeutXgUZhIZsS617ann9F2QXEC5FXQzBdovxI3i9fRThMQVUGnF2\nIkyoNUMObDcJSbs01jka3F+fadWc4YUqcOPGsTdZLXY/6cJsjrtLdsn3P3XlEevLXi2eQCor8959\nbNKXC3Tg3G5TKVtg9fV2qFWqSsLn0onDEf0GgM7rx0CtNIRRuk+3nincRq8thUMNLok+gksMyjJI\nbc7qXFukLB2RrMnYhfqkVBOKmFZCpTZzMRxAFIc+Pz5fnYpoaFkh24D7Hz8/WJCLG/KDvfSpiQgU\n93kEywF4bqXhDCZnYIudGuC4viQQSR+fyK6GSgDYox+JhU45GnZDMeQrMxfBNLRGDbg57LszRzA9\nHJemFsw6KNMY0Dp6aO1HUPw5qHHdDUQ9WIf/OBQU4G5yGl7Gd0HRBFLfgnexf6g0g4mjO/t2Z/CH\nHH3xlTIDK2LFhlFFrtKoM/TRtxheR4271b/Rj8QxvmP8GuR79AN2fyx0xIALyCZjbHTKvfOtP+0C\n+Tu/gsL5IBEolkHU2n7pKccZHPm0DS7uIrEptLsMtgSorZTYjeFmBr17KhAPbXVpG0gaHMODtZk0\ndgTocNt2/mQXLEGpkfN/ReAFgNP/ksMGBx55W/Tlj/jBd4ARSoAiZk9oPNWaEE6A+g8HHId3p82w\nM4hBIlAsg6aKp96Fn025vz+X40lgQv9y4tOvoeaUtAqKJxAn8ck/rN95N4muT48fhQqsjyeYQApJ\nvnFgJsmutI3QJZxAOlaYlNcQESjaBy+Yvkm6q9A0Ht5E/n898dxi138AQlZHGZHn+hAAAAAASUVO\nRK5CYII=\n",
       "text": [
        "<IPython.core.display.Image at 0x10dbeadd0>"
       ]
      }
     ],
     "prompt_number": 1
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The question we're asked is, given the board and positions of pieces on the board, what's the state of the board:  does Red win, or Blue win, or has nobody won yet, or is the board state impossible to reach?\n",
      "\n",
      "Let's go through that list of questions and see if we can find the right approach to take with this problem.  To see if red or blue won, we'll need to look for connected paths between the left and right (for blue) and top and bottom (for red) sides of the board using pieces of the right color.  That phrase \"connected paths\" ought to be a hint to you to try modeling the problem as a graph.  As two graphs, in fact --- one for blue and one for red.  Each cell containing a blue piece is connected to any neighboring blue pieces, along with the neighboring left/right edges.  Similarly for red.  Once we've built the blue and red graphs (including the board edges as vertices!) we can use them to determine whether the left/right edges are connected (and blue has a connected path) or whether the top/bottom edges are connected (and red has a connected path).  So we're done, right?  If blue has a connected path, blue wins, if red has a connected path, red wins, and if nobody has a connected path, then nobody wins.  \n",
      "\n",
      "But what about the impossible board states?  We'll need to check for those as well.  There's several ways the board state can be impossible, and it takes some thinking to identify all of them:\n",
      "\n",
      "* The difference between the number of red and blue pieces on the board is more than 1 (somebody skipped a turn)\n",
      "* The winner of the game has fewer pieces on the board (their opponent placed a piece after the game was over)\n",
      "* The winning path between board edges can't be broken by removing a single piece (or in graph terms, has no *articulation vertex*) (the players kept playing after the game was over)"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "#### Problem 2 - Password Attacker"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "https://code.google.com/codejam/contest/4214486/dashboard\n",
      "\n",
      "The second problem I want to look at is called Password Attacker, and it involves trying to guess a password given some limited information about that password.  In particular, we know that the password has $N$ total characters and $M$ unique characters, with $M \\leq N$.  We're asked to give the total number of possible passwords they might be, modulo $10^9+7$.  Before we get into how to actually solve the problem, let's think about how to classify it.  Just like in the last problem, where the phrase \"connected path\" ought to have tipped you off that we were looking at a graph problem, the phrase \"how many possible passwords\" ought to tell you that this is a combinatorics problem.  It is not, however, a *simple* combinatorics problem.  So let's think about a simpler case, where $M=N$.  That means that no character is repeated in the password, so the number of possible passwords is simply the number of permutations of size $M$, which is $M!$.\n",
      "\n",
      "Now, how might we extend this where $M < N$?  Well, suppose we had a rule that as we build up our passwords starting from the beginning, we always add new characters in lexicographic order.  So for $M=N$, we'll always get the string \"abcd...\" of how ever many characters.  For $M < N$, though, we'll have multiple possiblilities.  For M=2, N=3, for example, we'll have the passwords \"aab\", \"aba\", \"abb\".  To get the total number of possible passwords, we'll have to swap those characters around, in every possible way.  *This is exactly equivalent to a permutation.*  So, we can multiply the number of passwords following this rule by $M!$ to get the total number of passwords.  \n",
      "\n",
      "How can we generate these lexicographically ordered passwords?  Well, at each character position, we have two options:  repeat one of the characters we already have, or add a new character.  Now, sometimes, one of those options might be foreclosed.  If M=3 and N=4, then we're only allowed one repeated character, so once we've repeated a character we can't ever do it again.  Similarly, if we've already added $M$ new characters, then we're out and we'll have to repeat characters until we've generated $N$ total characters.  That suggests we keep track of two variables to define a state:  the number of repeated characters that are allowed in the rest of the password ($R$) and the number of unique characters we've already used ($C$).  \n",
      "\n",
      "Then the initial state, once we've added the first character is $(R=N-M, C=1)$.  We can define a recurrence as $(R,C) = C * (R-1, C) + (R, C+1)$.  The base cases happen for $R=0$, in which there is only one way to generate the rest of the password, and for $C>M$, in which there are zero ways to generate such a password.  So we write the recursion, try to solve the problem, and find that it runs far too slow on the Large input.  What trick can we use here?  We know that $R$ can vary from $N-M$ to 0, and $C$ can vary from 1 to $M$, where $M$ and $N$ can be as large as 100, so there are no more than 10000 distinct calls for each problem.  The slow run time comes because we have *overlapping subproblems*, a hallmark of dynamic programming.  So by either implementing an array to store values or simply memoizing our recursive function, we can solve the problem very rapidly.\n",
      "\n",
      "*Aside:  If you're familiar with combinatorics, you might recognize our recurrence as the Stirling numbers of the second kind.  This knowledge would make it easier to quickly implement your algorithm!*"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "#### Problem 3 - Kingdom Rush\n",
      "\n",
      "https://code.google.com/codejam/contest/1645485/dashboard#s=p1&a=1\n",
      "\n",
      "The third problem is called Kingdom Rush, based on a little mobile tower defense game.  This game has lots of levels ($N$), and completing a level can earn you either one or two stars, depending on how well you do.  Stars make you more powerful, so that it will be easier for you to complete future levels.  You can only gain the stars from each level once, but if you complete a level with a one-star rating, you can go back later once you're more powerful and complete it with a two-star rating to earn the second star.  You already know how many stars you will have to have in order to be powerful enough to complete each level with either a one- or a two-star rating.  You want to know what's the minimum number of times you have to complete levels in order to finish all the levels with a two-star rating.  This could be as low as $N$ (if you can complete every level once with a two-star rating) or as high as $2N$ (if you must complete every level twice, first with a one-star rating and then with a two-star rating) or it might not be possible to finish all the levels at all.\n",
      "\n",
      "How might we answer this problem?  What kind of approaches can we use?  Well, we can define a state as the number of stars we've earned, the level completion count, and the list of all the levels we haven't yet completed.  One approach would be a complete search - at each state, we go through each level it's possible to complete and continue our search from that state, ending when all the levels are finished.  Then we return the minimum completion count from all the finished states.  In the Large case, there's 1000 levels, giving us up to 1000! permutations of the order in which to try levels --- far too big to run.  We can notice that the problem exhibits optimal substructure - the result for each state depends on the result of smaller substates, and we can solve the smaller substates independently.  So we might think about a dynamic programming approach - we can have from 0 and 2000 stars, but there are $3^{2000}$ possible subsets of levels still to be completed.  This is still too big to evaluate.\n",
      "\n",
      "What happens if we try to identify the \"best\" move at each state?  Well, first off, let's notice that the best thing to do for each level is to complete it once with a two-star rating.  That suggests that if, at any time, we have enough stars to complete a new level with two stars, we can just go ahead and do so right now.  Waiting until we have more stars won't improve our performance on that level; it's already as good as it can be.  That means taking this move can never be a bad idea, so we don't have to examine any other possible moves before taking it.\n",
      "\n",
      "What if there are no levels we can complete right now with two-star ratings, but there are levels we can complete with a one-star rating?  We'll have to pick one of them to complete, but which one?  Suppose there are two remaining levels.  We have enough stars to complete both levels with a one-star rating, but to earn a two-star rating requires one additional star for the first level and three additional stars for the second level.  If we complete the first level with a one-star rating, we earn an additional star.  We still can't complete the second level with a two-star rating, so we complete the first level again with a two-star rating.  Now we have to run through the second level twice to finish it, for a total of four levels completed.  But if we do the second level with a one-star rating first and earn an additional star, we now have enough to do the first level with a two-star rating without having to do it as a one-star rating first, letting us finish the game with only three additional levels completed.\n",
      "\n",
      "That suggest that when we have a choice between multiple levels which we can only complete with one star, we should choose to complete the one with the highest requirement to complete with two stars, because that additional star might enable us to two-star some of the other levels.\n",
      "\n",
      "Together, this gives us a complete *greedy* strategy, which only requires $O(2N)$ time to compute:\n",
      "\n",
      "1) First, complete any levels which we can two-star that we haven't yet done.\n",
      "2) Then, complete any level we can one-star with the highest requirement to two-star.\n",
      "3) Repeat until all levels are completed with two-stars.  If we ever end up with no possible levels to complete, then we can't win the game.\n"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "#### Lab Section\n",
      "\n",
      "No homework problem this week!  Instead, during lab section, I'd like you to look at the following problems and try to identify approaches that might be used to solve them --- no actual solutions required.\n",
      "\n",
      "* Problem 1 - [Copying Books](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=655) - There are several potential approaches to take here.\n",
      "* Problem 2 - [Osmos](https://code.google.com/codejam/contest/2434486/dashboard)\n",
      "* Problem 3 - [Parentheses Order](https://code.google.com/codejam/contest/4214486/dashboard#s=p3) - This one is hard!"
     ]
    }
   ],
   "metadata": {}
  }
 ]
}