Round 1.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Abakoda Round 1.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyO5zbG0yxs+NOykarbkM8/U",
      "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%201.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PxXnr6T7EYEy"
      },
      "source": [
        "# Problem Letters"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "OnIHKfTz2Yqk"
      },
      "source": [
        "n = int(input())\n",
        "print('ABKD'[n - 1])"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hKATjytlIRDk"
      },
      "source": [
        "# Problem Statistics"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "bkI3lEcl5d4w"
      },
      "source": [
        "a = 0\n",
        "b = 0\n",
        "k = 0\n",
        "d = 0\n",
        "\n",
        "n = int(input())\n",
        "for i in range(n):\n",
        "  solved = input()\n",
        "  if 'A' in solved:\n",
        "    a += 1\n",
        "  if 'B' in solved:\n",
        "    b += 1\n",
        "  if 'K' in solved:\n",
        "    k += 1\n",
        "  if 'D' in solved:\n",
        "    d += 1\n",
        "\n",
        "print(a, b, k, d)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RBgkneCnIXxE"
      },
      "source": [
        "Save the input in a text file to save time."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "QmTlRINt64TH"
      },
      "source": [
        "%%writefile sample-input-1.txt\n",
        "4\n",
        "AK\n",
        "ABKD\n",
        "A\n",
        "ABK"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Jn7DjYVCIjrt"
      },
      "source": [
        "Save the solution to a file."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "sj-kdAkWIgNI"
      },
      "source": [
        "%%writefile solution.py\n",
        "a = 0\n",
        "b = 0\n",
        "k = 0\n",
        "d = 0\n",
        "\n",
        "n = int(input())\n",
        "for i in range(n):\n",
        "  solved = input()\n",
        "  if 'A' in solved:\n",
        "    a += 1\n",
        "  if 'B' in solved:\n",
        "    b += 1\n",
        "  if 'K' in solved:\n",
        "    k += 1\n",
        "  if 'D' in solved:\n",
        "    d += 1\n",
        "\n",
        "print(a, b, k, d)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "kWiEF0EaIoGR"
      },
      "source": [
        "Run the solution where the input is obtained from the text file."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DKuogSeX76zh"
      },
      "source": [
        "!python solution.py < sample-input-1.txt"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "R9aY1azkJPQe"
      },
      "source": [
        "This solution is easier to extend to handle more letters."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "1nqGEHqy7zBf"
      },
      "source": [
        "%%writefile solution.py\n",
        "scores = [0, 0, 0, 0]\n",
        "letters = 'ABKD'\n",
        "\n",
        "n = int(input())\n",
        "for i in range(n):\n",
        "  solved = input()\n",
        "  for j in range(4):\n",
        "    if letters[j] in solved:\n",
        "      scores[j] += 1\n",
        "\n",
        "for j in range(4):\n",
        "  print(scores[j], end=\" \")"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "bPb5yqSoIyMr"
      },
      "source": [
        "!python solution.py < sample-input-1.txt"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xQ70KyLWKCEc"
      },
      "source": [
        "# Rankings Order"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rX4E-G_F_leh"
      },
      "source": [
        "%%writefile solution.py\n",
        "\n",
        "def key_by_score(contestant):\n",
        "  return contestant[1]\n",
        "\n",
        "def key_by_name(contestant):\n",
        "  return contestant[0]\n",
        "\n",
        "n = int(input())\n",
        "contestants = []\n",
        "for i in range(n):\n",
        "  name, score = input().split()\n",
        "  score = int(score)\n",
        "  contestants.append([name, score])\n",
        "\n",
        "# key=function is your way to tell Python what parts of the data is important to look at to determine the order\n",
        "contestants.sort(key=key_by_name)\n",
        "contestants.sort(key=key_by_score, reverse=True)\n",
        "\n",
        "for contestant in contestants:\n",
        "  print(contestant[0], contestant[1])\n",
        "\n",
        "# sort with custom comparison in C++/Java"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "kR5pPLZDrdud"
      },
      "source": [
        "It seems upside-down, but if we want to sort by score and then break ties by name, we sort by name first, then by score. Why this works: the sort function in Python is **stable**, meaning, if two items are tied according to the comparison rule/key function we provided, their *relative* order is left unchanged. Of the two tied items, the item that came first before sorting still comes first after sorting. In our solution, this means that if there are ties while sorting by score, the tied items will be left in the order they had before sorting by score, in other words, ties become sorted by name."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mh0zvr29A8Ap"
      },
      "source": [
        "%%writefile sample-input-1.txt\n",
        "5\n",
        "baba 200\n",
        "aba 200\n",
        "abby 400\n",
        "koda 100\n",
        "cody 300\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KCb4viI6BCNa"
      },
      "source": [
        "!python solution.py < sample-input-1.txt"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "VWzXhuEbMGgB"
      },
      "source": [
        "By the way, the built-in sort functions in Python, C++, and Java turn into $O(n \\log nT)$ CPU operations, where $n$ is the number of items to sort, and $T$ is how many operations are required to do a comparison. For example, sorting by score is $O(n \\log n)$ because comparing two numbers happens instantly. On the other hand, sorting by name is $O(n \\log n S)$, where $S$ is the maximum length of one string. You don't have to understand why it is $O(n \\log nT)$ for now, but you can already use this fact to estimate the efficiency of your own programs, if they use the sort function. Take note! Just because the syntax is short, doesn't mean it translates into a small constant number of CPU operations. Behind the scenes, those built-in functions can have loops and stuff inside."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "oMlubLLYKOQ8"
      },
      "source": [
        "# Rankings Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DjN6xv9NMsI"
      },
      "source": [
        "n = int(input())\n",
        "contestants = []\n",
        "for i in range(n):\n",
        "  name, score = input().split()\n",
        "  contestants.append(name)\n",
        "s = int(input())\n",
        "# Everything in this loop is roughly (s * n * length of string) operations.\n",
        "for i in range(s):\n",
        "  name = input()\n",
        "  # Everything in this loop is roughly (n * length of string) operations.\n",
        "  for j in range(n):\n",
        "    # This if statement is roughly (length of string) operations.\n",
        "    # Even though this looks like it should happen instantly,\n",
        "    # behind the scenes, to know if two strings are equal, Python checks the characters one by one.\n",
        "    # We should count it.\n",
        "    if contestants[j] == name:\n",
        "      print(j + 1)\n",
        "\n",
        "# (s * n * length of string) operations is too slow."
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "WeH8XqjrN88j"
      },
      "source": [
        "n = int(input())\n",
        "contestants = []\n",
        "for i in range(n):\n",
        "  name, score = input().split()\n",
        "  contestants.append(name)\n",
        "s = int(input())\n",
        "# Everything in this loop is roughly (s * n * length of string) operations.\n",
        "for i in range(s):\n",
        "  name = input()\n",
        "  # This statement is roughly (n * length of string) operations.\n",
        "  # Even though this looks like it should happen instantly,\n",
        "  # behind the scenes, Python will do the exact same loop as in the earlier solution.\n",
        "  print(contestants.index(name) + 1)\n",
        "\n",
        "# (s * n * length of string) operations is too slow."
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "loxQV5wXLLc-"
      },
      "source": [
        "n = int(input())\n",
        "\n",
        "contestants = {} # This is called a dictionary in Python.\n",
        "# In C++: map<string, int> contestants; (OK, not exactly, but you can learn the difference in the future)\n",
        "# In Java: HashMap<String, Integer> contestants;\n",
        "for i in range(n):\n",
        "  name, score = input().split()\n",
        "\n",
        "  # The things we insert into a dictionary are called \"key-value pairs.\"\n",
        "  # Here, the key is \"name,\" and the value is \"i.\"\n",
        "  # Dictionaries let us \"associate\" keys with values, and retrieve the value associated with a key.\n",
        "  contestants[name] = i\n",
        "  \n",
        "s = int(input())\n",
        "# Everything in this loop is roughly (s * length of strings) operations (on average).\n",
        "for i in range(s):\n",
        "  name = input()\n",
        "  # Everything in this loop is roughly (length of string) operations (on average).\n",
        "  # It doesn't seem much different than the solution before,\n",
        "  # but behind the scenes, Python does something much smarter to make it faster.\n",
        "  print(contestants[name] + 1)\n",
        "\n",
        "# (s * length of strings) operations is fast enough."
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "SESqjhI_RpEa"
      },
      "source": [
        "The reason why this is faster: behind the scenes, dictionaries are just arrays/lists. When you tell Python to insert a **key-value pair** in the dictionary, it first converts the key into a number, then puts the value in that position in the list. When you tell Python to get the value associated with a key, it also first converts the key into a number, then accesses that position in the list. There is no loop that compares the key with every item in the dictionary one-by-one.\n",
        "\n",
        "One of the \"expensive\" operations that Python needs to do is converting a key to a number, and this is about (length of the key) operations for string keys, which is not really that expensive if the strings are short. What might make dictionary operations slow is **collisions**: because keys are converted to numbers basically randomly, it might happen that two different keys get converted to the same position. There are ways to deal with this. They make dictionaries slightly slower than plain list indexing, but usually still much better than for-looping through a list of items, one item at a time.\n",
        "\n",
        "For more details on how this works, see [this YouTube video](https://www.youtube.com/watch?v=KyUTuwz_b7Q)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fRxF0VI8OOct"
      },
      "source": [
        "Another way (code not shown here): repeatedly compare the string to find to the middle of the search range, at each step shrinking the search range to the upper half if what we are looking for is smaller than the item in the middle, or to the lower half if what we are looking for is larger than the item in the middle. This works because we know the list is sorted. For details on how to turn this idea into code, see [this YouTube video](https://www.youtube.com/watch?v=6ysjqCUv3K4).\n"
      ]
    }
  ]
}