week10_hw.ipynb

{
 "metadata": {
  "name": "week10_hw.ipynb"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Homework 10, CSE 232\n",
      "#### Due October 29\n",
      "Note: On most of the problem sets through the semester, I'll put a horizontal line with \"Optional\" under it.  Any problems below this section are encouraged - I think they're interesting and will help you learn the subject - but not necessary to complete in order to get credit for the homework."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Problem 1\n",
      "\n",
      "This week's problem is [Google Code Jam Round 1A 2012 - Password Problem](https://code.google.com/codejam/contest/1645485/dashboard).  Here's the problem statement:"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> I have a really long password, and sometimes I make a mistake when I type it. Right now I've typed part of my password, but I might have made some mistakes. In particular, I might have pressed the wrong key while typing one or more of the previous characters. Given how likely I was to get each character right, what should I do?\n",
      "\n",
      "> I have three options:\n",
      "\n",
      "> Finish typing the password, then press \"enter\". I know I'll type the rest of the characters perfectly. If it turns out that one of the earlier characters was wrong, I'll have to retype the whole thing and hit \"enter\" again -- but I know I'll get it right the second time.\n",
      "Hit \"backspace\" some number of times, deleting the last character(s) I typed, and then complete the password and press \"enter\" as in option  1. If one of the characters I didn't delete was wrong, I'll have to retype the whole thing and press \"enter\", knowing I'll get it right the second time.\n",
      "Give up by pressing \"enter\", retyping the password from the start, and pressing \"enter\" again. I know I'll get it right this time.\n",
      "I want to minimize the expected number of keystrokes needed. Each character in the password costs 1 keystroke; each \"backspace\" costs 1 keystroke; pressing \"enter\" to complete an attempt or to give up costs 1 keystroke.\n",
      "\n",
      "> *Note:* The \"expected\" number of keystrokes is the average number of keystrokes that would be needed if the same situation occurred a very large number of times. See the example below.\n",
      "\n",
      "#### Example\n",
      "\n",
      "> Suppose my password is \"guest\" and I have already typed the first two characters, but I had a 40% chance of making a mistake when typing each of them. Then there are four cases:\n",
      "\n",
      "> I typed \"gu\" without error. This occurs with probability 0.6 $\\times$ 0.6 = 0.36.\n",
      "\n",
      "> I typed the 'g' correctly but I made a mistake typing the 'u'. Then I have two letters typed still, but the second one is wrong: \"gX\". (Here, the 'X' character represents a mistyped letter.) This occurs with probability 0.6 $\\times$ 0.4 = 0.24.\n",
      "\n",
      "> I typed the 'u' correctly but I made a mistake typing the 'g': \"Xu\". This occurs with probability 0.4 $\\times$ 0.6 = 0.24.\n",
      "\n",
      "> I made a mistake typing both letters, so I have two incorrect letters: \"XX\". This occurs with probability 0.4 $\\times$ 0.4 = 0.16.\n",
      "\n",
      "> I don't know how many mistakes I actually made, but for any strategy, I can calculate the expected number of keys required to use it. This is shown in the table below:\n",
      "\n",
      "\\begin{equation}\n",
      "\\begin{array}{cccccc}\n",
      " & gu & gX & Xu & XX & Expected \\\\\n",
      " \\textrm{Probability} & 0.36 & 0.24 & 0.24 & 0.16 & - \\\\\n",
      " \\textrm{Keystrokes if I keep typing} & 4 & 10 & 10 & 10 & 7.84 \\\\\n",
      " \\textrm{Keystrokes if I press backspace once} & 6 & 6 & 12 & 12 & 8.4 \\\\\n",
      " \\textrm{Keystrokes if I press backspace twice} & 8 & 8 & 8 & 8 & 8 \\\\\n",
      " \\textrm{Keystrokes if I press enter right away} & 7 & 7 & 7 & 7 & 7 \\\\\n",
      "\\end{array}\n",
      "\\end{equation}\n",
      "\n",
      "> If I keep typing, then there is an 0.36 probability that I will need 4 keystrokes, and an 0.64 probability that I will need 10 keystrokes. If I repeated the trial many times, then I would use 4 keystrokes 36% of the time, and 10 keystrokes the remaining 64% of the time, so the average number of keystrokes needed would be 0.36 $\\times$ 4 + 0.64 $\\times$ 10 = 7.84. In this case however, it is better to just press enter right away, which requires 7 keystrokes.\n",
      "\n",
      "#### Input\n",
      "\n",
      "> The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing two integers, A and B. A is the number of characters that I have already typed, and B is the total number of characters in my password.\n",
      "\n",
      "> This is followed by a line containing A real numbers: $p_1, p_2, \\dots, p_A$. $p_i$ represents the probability that I correctly typed the ith letter in my password. These real numbers will consist of decimal digits and at most one decimal point. The decimal point will never be the first or the last character in a number.\n",
      "\n",
      "#### Output\n",
      "\n",
      "> For each test case, output one line containing \"Case #x: y\", where x is the case number (starting from 1) and y is the expected number of additional keystrokes I need, not counting the letters I have typed so far, and assuming I choose the optimal strategy. y must be correct to within an absolute or relative error of $10^{-6}$.\n",
      "\n",
      "#### Limits\n",
      "\n",
      "> 1 \u2264 T \u2264 20.\n",
      "\n",
      "> 0 \u2264 $p_i$ \u2264 1 for all i.\n",
      "\n",
      "#### Small dataset\n",
      "\n",
      "> 1 \u2264 A \u2264 3.\n",
      "\n",
      "> A < B \u2264 100.\n",
      "\n",
      "#### Large dataset\n",
      "\n",
      "> 1 \u2264 A \u2264 99999.\n",
      "> A < B \u2264 100000."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> *a) The problem describes three strategies. The first strategy is to keep typing the password, retyping the password after if you get it wrong the first time around.  How many keystrokes will this strategy take if you made a mistake in the first $A$ characters?  How about if you got all the first $A$ characters correct?*"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> *b) The second strategy is to press backspace $k$ times, where $k \\in [1, A]$, removing the last $k$ characters of the password, then completing the password and retyping the whole thing if incorrect.  How many keystrokes will this strategy take if there is a mistake in the first $A-k$ characters?  How about if the first $A-k$ characters are correct?*"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> *c) The final strategy is to press enter right now, get the password wrong, and then retype it.  How many keystrokes will this take?*"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> *d) Given the (independent) probabilities $p_k$ that we typed the $k_{th}$ character correctly, explain how to calculate the probability $P_k$ that we got all of the first $k$ characters typed correctly.  How can we calculate this efficiently for all values of k between 1 and A?*"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> *e) Using the expected value calculations we discussed in class and your work above, write an efficient solution to find the best strategy for a given input, submit your solution to the Google Code Jam, and attach it to your homework.*"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "---\n",
      "##### Optional"
     ]
    }
   ],
   "metadata": {}
  }
 ]
}