week1_hw.ipynb

{
 "metadata": {
  "name": "week1_hw.ipynb"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Homework 1, CSE 232\n",
      "#### Due September 3\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",
      "During lab today, I gave you a Small problem from the Google Code Jam: [Bullseye](https://code.google.com/codejam/contest/dashboard?c=2418487#s=p0). Here's the text of the problem:\n",
      "\n",
      ">Maria starts with $t$ millilitres of black paint, which she will use to draw rings of thickness 1 cm (one centimetre). A ring of thickness 1 cm is the space between two concentric circles whose radii differ by 1 cm.\n",
      "\n",
      ">Maria draws the first black ring around a white circle of radius $r$ cm. Then she repeats the following process for as long as she has enough paint to do so:\n",
      "\n",
      ">Maria imagines a white ring of thickness 1 cm around the last black ring.\n",
      ">Then she draws a new black ring of thickness 1 cm around that white ring.\n",
      ">Note that each \"white ring\" is simply the space between two black rings.\n",
      ">The area of a disk with radius 1 cm is \u03c0 cm$^2$. One millilitre of paint is required to cover area \u03c0 cm$^2$. What is the maximum number of black rings that Maria can draw? Please note that:\n",
      "\n",
      ">Maria only draws complete rings. If the remaining paint is not enough to draw a complete black ring, she stops painting immediately.\n",
      ">There will always be enough paint to draw at least one black ring."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "In the Small problem, both *r* and *t* are less than 1000."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> *a. How much paint will it take to paint the $n$th black ring in terms of $n$ and $r$?*"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> *b. Describe a brute force algorithm to solving the Small problem by iterating through each black ring using the formula derived in part a.  How does this algorithm scale with maximum $n$? What is the largest possible number of black rings Maria can draw under using the Small input limits?*\n",
      "\n",
      "In the Large problem, *r* is allowed to be as large as $10^{18}$, while *t* is allowed to be as large as $2 \\times 10^{18}$.\n",
      "\n",
      "> *c. How does this limit the applicability of a brute force solution?*"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "***\n",
      "####Optional"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> *d. How much paint is needed to paint the first $n$ black rings in terms of $n$ and $r$?  That is, $\\sum\\limits_{i=1}^n P(i, r)$, where $P(n, r)$ is the paint needed for the $n$th ring as calculated in part b.*"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> *e. Describe how you could potentially use this formula to solve this problem in $O(1)$ time.  Implement this solution in your language of choice, attach your solution to your homework, and try to solve both the Small and Large problems with it using the Google Code Jam submission form. Does it work for both input sizes?*"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "> *f. Working with large integers and square root functions can often cause integer overflows and rounding errors, leading to wrong answers even when the algorithm is technically correct.  Describe how to solve this problem in $O(\\mathrm{log }n)$ time using the same formula by repeatedly dividing the search space. Implement this solution, attach it to your homework, and test it on both the Small and Large problems.*"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "####Other Problems of Interest"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "[TOJ 1025. Democracy in Danger](http://acm.timus.ru/problem.aspx?space=1&num=1025)\n",
      "\n",
      "[TOJ 1068. Sum](http://acm.timus.ru/problem.aspx?space=1&num=1068)"
     ]
    }
   ],
   "metadata": {}
  }
 ]
}