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 non-negative 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 U-shaped (convex and eventually increasing) function f, find its minimum over the non-negative 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 U-shaped (convex and eventually increasing) function f, find its minimum over the non-negative 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 non-negative 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.