Round 8.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Abakoda Round 8.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyM3e4D2mR439GD0dz8cQkKz",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/noi-ph/abakoda/blob/master/Round%208.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1kOdGUCUDP98"
      },
      "source": [
        "# Pusit Bulaga: Game A"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "hi0DnlrHMjiR"
      },
      "source": [
        "n, k = [int(x) for x in input().split()]\n",
        "top_row = [int(x) for x in input().split()]\n",
        "bot_row = [int(x) for x in input().split()]\n",
        "print(max(sum(top_row), sum(bot_row)))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8cch2uewDdbN"
      },
      "source": [
        "# Pusit Bulaga: Game B"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "q9iJkDLOQFiz"
      },
      "source": [
        "n, k = [int(x) for x in input().split()]\n",
        "top_row = [int(x) for x in input().split()]\n",
        "bot_row = [int(x) for x in input().split()]\n",
        "\n",
        "ans = 0\n",
        "for pos in range(n):\n",
        "  ans += max(top_row[pos], bot_row[pos]))\n",
        "\n",
        "print(ans)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DG2hZBXkDqkC"
      },
      "source": [
        "n, k = [int(x) for x in input().split()]\n",
        "top_row = [int(x) for x in input().split()]\n",
        "bot_row = [int(x) for x in input().split()]\n",
        "print(sum(max(top_row[pos], bot_row[pos]) for pos in range(n)))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F0uWtQxoD0uo"
      },
      "source": [
        "# Pusit Bulaga: Game K"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "s-94K9HrVHKd"
      },
      "source": [
        "n, k = [int(x) for x in input().split()]\n",
        "top_row = [int(x) for x in input().split()]\n",
        "bot_row = [int(x) for x in input().split()]\n",
        "\n",
        "ans = max(sum(top_row), sum(bot_row))\n",
        "\n",
        "# n * 2n steps = O(n^2) steps\n",
        "# outer loop runs n times\n",
        "# one step of the loop requires 2n steps for get the sums\n",
        "# n <= 10^5\n",
        "# n^2 <= 10^10 -> too big! 10^7 python operations per second\n",
        "for pos in range(n): \n",
        "\n",
        "  # top first, then bottom\n",
        "  # sum of top up to index pos (inclusive) + sum of bot starting from pos + 1\n",
        "  # n steps\n",
        "  ans = max(ans, whatever this is ^)\n",
        "\n",
        "  # bottom first, then top\n",
        "  # sum of bot up to index pos (inclusive) + sum of top starting from pos + 1\n",
        "  # n steps\n",
        "  ans = max(ans, whatever this is ^)\n",
        "\n",
        "print(ans)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zwmO-PTQEvVz"
      },
      "source": [
        "Idea: if you already know the sum of the first `pos` items in the row, you can get the sum of the first `pos + 1` items in $O(1)$. You don't need to repeat additions already done before. You can similarly get the sum of the last `pos - 1` items in a row if you know the sum of the last `pos` itmes."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "nY5Vh-JDEuDu"
      },
      "source": [
        "n, k = [int(x) for x in input().split()]\n",
        "top_row = [int(x) for x in input().split()]\n",
        "bot_row = [int(x) for x in input().split()]\n",
        "\n",
        "ans = max(sum(top_row), sum(bot_row))\n",
        "\n",
        "top_left_sum = 0\n",
        "bot_right_sum = sum(bot_row)\n",
        "\n",
        "bot_left_sum = 0\n",
        "top_right_sum = sum(top_row)\n",
        "\n",
        "for pos in range(n):\n",
        "\n",
        "  top_left_sum += top_row[pos]\n",
        "  bot_right_sum -= bot_row[pos]\n",
        "  ans = max(ans, top_left_sum + bot_right_sum)\n",
        "\n",
        "  bot_left_sum += bot_row[pos]\n",
        "  top_right_sum -= top_row[pos]\n",
        "  ans = max(ans, bot_left_sum + top_right_sum)\n",
        "\n",
        "print(ans)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WfXKn_7DFTkv"
      },
      "source": [
        "# Pusit Bulaga: Game D"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GTxDKLgHGwRh"
      },
      "source": [
        "Here is a recursive solution. Unfortunately, it's too slow. This one runs in $O(2^n)$."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "hvvj-wuFZ_Xt"
      },
      "source": [
        "n, k = [int(x) for x in input().split()]\n",
        "top_row = [int(x) for x in input().split()]\n",
        "bot_row = [int(x) for x in input().split()]\n",
        "\n",
        "def best(pos, swaps, top):\n",
        "    if pos == n:\n",
        "      return 0\n",
        "    else:\n",
        "      return (top_row if top else bot_row)[pos] + max(\n",
        "          best(pos + 1, swaps, top),\n",
        "          best(pos + 1, swaps - 1, not top) if swaps > 0 else 0\n",
        "      )\n",
        "\n",
        "print(max(best(0, k, True), best(0, k, False)))\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "OSoH8jMqHHKS"
      },
      "source": [
        "There is a simple trick to make solutions like this faster. If you draw the recursion tree, you'll notice that lots of the succeeding calls overlap. We can save time by saving the answer we got the first time we call the function with specific inputs. When we call the function again with the same inputs, instead of making additional recursive calls, let's just retrieve the saved answer. This technique is called **memoization** or **dynamic programming**."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "q-JRCr_8G0vn"
      },
      "source": [
        "n, k = [int(x) for x in input().split()]\n",
        "top_row = [int(x) for x in input().split()]\n",
        "bot_row = [int(x) for x in input().split()]\n",
        "\n",
        "saved_answer = {}\n",
        "\n",
        "def best(pos, swaps, top):\n",
        "  if (pos, swaps, top) not in saved_answer:\n",
        "    if pos == n:\n",
        "      saved_answer[(pos, swaps, top)] = 0\n",
        "    else:\n",
        "      saved_answer[(pos, swaps, top)] = (top_row if top else bot_row)[pos] + max(\n",
        "          best(pos + 1, swaps, top),\n",
        "          best(pos + 1, swaps - 1, not top) if swaps > 0 else 0\n",
        "      )\n",
        "    return saved_answer[(pos, swaps, top)]\n",
        "\n",
        "print(max(best(0, k, True), best(0, k, False)))\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4rR4RDnaIJvt"
      },
      "source": [
        "Doing this brings the running time down to $O(nk)$. Here's why:\n",
        "\n",
        "\n",
        "1. There are $n$ unique possible values of `pos`, $k$ unique possible values of `swaps`, and $2$ unique possible values of `top` in the recursion tree, for a total of $n \\times k \\times 2 = O(nk)$ unique recursion calls.\n",
        "2. The total running time is the sum over all unique calls of the following: the number of times a call is encountered for the first time, plus the number of times the answer to a call is accessed from the dictionary.\n",
        "3. The sum over all the first-time calls is just $O(nk)$.\n",
        "4. The number of dictionary accesses is at most the number of recursive calls that are made (only from first-time calls). There are $2$ recursive calls from each first-time call, so this is just $nk \\times 2 = O(nk)$.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "nHdN6kwtLLaE"
      },
      "source": [
        "To learn more about dynamic programming, we recommend the following references:\n",
        "\n",
        "\n",
        "* [MIT OCW 6.006 (2011) Lecture 19](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-19-dynamic-programming-i-fibonacci-shortest-paths/);  [Lecture Notes](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec19.pdf)\n",
        "* [MIT OCW 6.006 (2011) Lecture 20](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-20-dynamic-programming-ii-text-justification-blackjack/);  [Lecture Notes](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec20.pdf)\n",
        "* [MIT OCW 6.006 (2011) Lecture 21](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-21-dp-iii-parenthesization-edit-distance-knapsack/);  [Lecture Notes](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec21.pdf)\n",
        "* [MIT OCW 6.006 (2011) Lecture 22](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-22-dp-iv-guitar-fingering-tetris-super-mario-bros/);  [Lecture Notes](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec22.pdf)\n",
        "\n"
      ]
    }
  ]
}