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

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.

Indices and tables