codejamhelpers documentation¶
A library of helper functions useful for solving Google Code Jam problems.
Contents:

class
codejamhelpers.
Primes
(frontier=None)¶ The prime numbers, prepopulated up to frontier, with lazy evaluation beyond.

__contains__
(n)¶ Test whether n is prime

__getitem__
(i)¶ The ith prime

count
(x)¶ Count the number of primes less than or equal to x


codejamhelpers.
binary_search
(f, t)¶ Given an increasing function \(f\), find the greatest nonnegative integer \(n\) such that \(f(n) \le t\). If \(f(n) > t\) for all \(n \ge 0\), return None.

codejamhelpers.
powers_of_two
()¶ Powers of 2, from 1

codejamhelpers.
minimise_convex
(f)¶ Given a Ushaped (convex and eventually increasing) function f, find its minimum over the nonnegative integers. That is \(m\) such that \(f(m) \le f(n)\) for all \(n\). If there exist multiple solutions, return the largest. Uses binary search on the derivative.

codejamhelpers.
minimise_convex2
(f)¶ Given a Ushaped (convex and eventually increasing) function f, find its minimum over the nonnegative integers. That is \(m\) such that \(f(m) \le f(n)\) for all \(n\). If there exist multiple solutions, return the largest. Uses ternary search.

codejamhelpers.
kth_root
(n, k)¶ Calculate the greatest nonnegative integer \(r\) such that \(r^k \le n\).

codejamhelpers.
trials
(P)¶ Given the individual probabilities \(P_i\) of n independent trials, calculate the probabilities \(Q_k\) that exactly \(0 \le k \le n\) are successful.