Happy 2π Day!

I'm totally not missing the point here...

Problems to Give to Your Enemies

1. There are 9 cards numbered 1 to 9. Ada and Bob play a game where they alternate selecting cards (without replacement) until someone has three distinct cards summing to 15, with Ada going first. a) Prove that Bob does not have a winning strategy. b) Does Ada have a winning strategy? If so, what is it?
2. Are there positive integer solutions to $x^3 + y^3 = 9z^3$ other than $(1,2,1)$ and $(2, 1, 1)$?
3. Prove that for all non-negative real numbers $a, b, c$ we have $(a^2 + b^2 + c^2)^2 \ge 3(a^3b + b^3 c + c^3 a)$, and determine when equality holds.
4. Find all real numbers $r$ such that $n^r$ is an integer for all positive integers $n$.
5. Does there exist a positive integer $n$ such that $n, 2n, \ldots, 2015n$ all have the same multiset of nonzero digits?
6. Find all ordered triples of non-negative integers $(a,b,c)$ such that $a^2+2b+c$, $b^2+2c+a$, and $c^2+2a+b$ are all perfect squares.

ACM-ICPC World Finals 2015 Recap

World Finals 2015 Recap
Harvard 3 - Calvin Deng, Johnny Ho, David Liu

We solved 8 problems with a penalty of 1056, good for 19th place. 

Order of Solving:
Problem - Penalty (wrong submissions)
A - 00:15
D - 00:39
F - 01:24
I - 01:39 (+1)
C - 02:11 (+1)
L - 02:28
H - 03:30
E - 04:50

Problem A: Amalgamated Artichokes (solved in 15 minutes, 1 submission)
    * Solved quickly
    * Solved by everyone; Coded by Calvin in 5(?) minutes
    * Algorithm: Simple loop, maintain the maximum price encountered so far.
    * Notes:
        * Was too slow in realizing it was easy

Problem B: Asteroids (not solved, no submissions)
    * Notes:
        * Guessed that it was ternary search with intersection area,
        * Again, unsure if this is correct
        * NOTE FOR NEXT YEAR: need triangle intersection / polygon intersection code. (more geometry in general)

Problem C: Catering (solved in 131 minutes, 2 submissions)
    * Solved fairly quickly.
    * Solved by Johnny / Calvin; Coded by Johnny in 30 mins
    * Algorithm: Min-cost max flow
    * Notes:
        * Could’ve been solved more quickly
        * Wasted time not being sure if it was correct
        * Wasted time/submission fixing min > max, this should’ve been clear

Problem D: Cutting Cheese (solved in 39 minutes, 1 submission)
    * Solved fairly quickly
    * Solved by Calvin; Coded by Calvin in 20 mins
    * Algorithm: Binary search with volume computations

Problem E: Evolution in Parallel (solved in 290 minutes, 1 submission)
    * Solved very slowly
    * Solved by Calvin; Coded by Johnny w/ Calvin pair coding in 20 mins
    * Algorithm: Greedy Algorithm, with a twist. Maintain three lists: left list, right list, middle list. Sort by length in decreasing order, and add to the middle list when you can; otherwise, add to whichever list fits and move the middle list into the other list (then clear the middle list).
    * Notes:
        * Didn’t get greedy solution until half an hour or left
        * Didn’t realize we could greedy 

Problem F: Keyboarding (solved in 84 minutes, 1 submission)
    * Solved fairly quickly
    * Solved by Calvin; Coded by Johnny in 30 mins
    * Algorithm: Simple BFS; the state is (x, y, number of letters typed).
    * Notes:
        * Wasted time debating solution and not coding completely to specification
        * Didn’t realize could move multiple steps at a time, should’ve been clear if we read the problem more carefully

Problem G: Pipe Stream (not solved, no submissions)
    * No clue, realized that it was hard early

Problem H: Qanat (solved in 210 minutes, 1 submission)
    * Solved by Calvin and David; Coded by Calvin in 15 minutes
    * Solved somewhat slowly
    * Algorithm: finding formula for each shaft location based on its neighboring shaft locations. More precisely: let $a_0 = 0, a_1, ..., a_n, a_{n+1} = w$ be the locations of the shafts. Then $a_i = (a_{i - 1} + a_{i + 1}) * c$, where I think $c = 1 - h^2 / w^2$? Afterwards, we can first assume $a_1 = 1$ and calculate $a_{n + 1}$, and then scale linearly to fit.
    * Notes:
        * Took a while to solve, was easy to code though

Problem I: Ship Traffic (solved in 99 minutes, 2 submissions)
    * Solved by Johnny fairly quickly
    * Coded by Johnny in 20 mins
    * Algorithm: Simple interval sorting and merging.
    * Waited to solve for no reason because nobody else solved it
        * First solve by MIT at 53 minutes, Johnny solved it considerably before then.
    * Slightly tripped up by tricky math
    * First submission’s bug was stupid, involved flipping a pair and pair

Problem J: Tile Cutting (not solved, no submissions)
    * Solved by Johnny / David fairly quickly.
    * Algorithm: Basic FFT + Max range queries. Some easy math gives that the number of ways to get an area of $n$ is the sum of $\tau(i)\tau(n - i)$ from $i = 1,..., n-1$, where $\tau(n)$ is the number of divisors of $n$.
    * Notes:
        * Unfortunately, we did not have FFT code, so we wasted time trying to derive FFT (this was not fruitful).
        * NOTE FOR NEXT YEAR: Need to add FFT (probably won't appear again, but this is for the sake of completeness).

Problem K: Tours (not solved, no submissions)
    * Notes:
        * Didn’t make substantial progress in solving
        * Turned out to not be that hard, required splicing on bridges and then isolating nodes that disconnect other nodes

Problem L: Weather Report (solved in 148 minutes, 1 submission)
    * Solved by Calvin; Coded by Johnny w/ Calvin pair coding.
    * We wasted time testing the problem at the beginning, did not realize discreteness mattered a lot
    * Turned out to be Huffman encoding w/ repetitions, solved moderately 
    * quickly
    * Was unsure of time complexity, so we waited after solving it.
        * I think it can be shown pretty easily that the program should run in 
          time (something about bounding the sum of log(probabilities) + 
          log(frequencies)).

Problem M: Window Manager (not solved in 4 submissions)
    * Solved pretty quickly
    * Notes:
        * Moderately complicated implementation problem
        * Johnny wasted large amount of coding time (60+ mins)
            * Started Coding M after submitting L, took short breaks to allow E and H to be coded.
        * Did not realize reflection/rotation tricks to minimize coding until late
        * Did not think carefully about solution before coding

Best-of-7 Series: 3-0 Comebacks

Since it's NBA playoffs season, a common fact that gets thrown around is that no NBA team has ever come back from a 3-0 deficit to win a best-of-7 series. Of course, the NHL and MLB also employ a best-of-7 format (though the MLB only does it for 3 series a year), and both of these leagues have had (at least) one team come back from a 3-0 hole. 

Through fall 2014, NHL teams have performed such a comeback 4 times out of 178 tries (2.25%), NBA teams have come back 0 times out of 110 (0%), and MLB teams (go Red Sox!) have come back 1 time out of 34 (2.94%), for an overall rate of 5 times out of 322 (1.55%). [1]

I thought I'd go through a quick exercise on how likely it is for teams to come back from a 3-0 hole in a best-of-seven series. 

1. Warmup: Team A has a $50$ percent chance of winning any particular game in a best-of-7 series. What is the probability that Team A loses the series, given that it wins the first three games?
2. Team A has a $p$ chance of winning any given game in a best-of-7 series. What is the probability that Team A wins the first three games?
3. Now we don't know anything about $p$, other than the fact that it is drawn from a uniform distribution on $[0,1]$. What is the probability that Team A wins the first three games?
4. Again, $p$ is drawn from a uniform distribution on $[0,1]$. What is the probability that Team A wins the first three games but then loses the next four games?
5. Given that $p$ is drawn from a uniform distribution, what is the conditional probability of Team A losing the series given that it wins the first three games?

If you work these exercises out correctly, you should have gotten the following answers:

1. $\frac{1}{16}$
2. $p^3$
3. $\frac{2}{5}$
4. $\frac{1}{315}$
5. $\frac{1}{126}$

Under this model, the probability of NBA teams going 0-for-110 is $\left(\frac{125}{126}\right)^{110}$, or about 41.6%, so (given this model) it's not too surprising that such a comeback has never happened. 

In reality, NBA/NHL/MLB teams in the playoffs are usually more evenly matched than this model would suggest: for example,  you don't ever see an MLB team being given less than a $\frac{1}{3}$ chance of winning a particular game. Therefore we would expect the distribution for $p$ to be much more concentrated around $\frac{1}{2}$ (compared to the uniform distribution). This in turn should increase the conditional probability of coming back from a 3-0 deficit. The extreme case of this would be when $p$ is fixed at $\frac{1}{2}$, and as we saw there, the condition probability of a 3-0 comeback gets as high as $\frac{1}{16}$.

This model also doesn't account for the home/away split, but my intuition is that that would probably also increase the conditional probability of such a comeback happening. Indeed, the overall comeback rate for 3-0 series is higher than what this simplified model predicts.

In any case, we should be probably be surprised that a 3-0 comeback has never happened in the NBA, but at the same time, don't expect one to happen any time soon.

[1] http://www.whowins.com/tables/up30.html