总结一下用python撸codejam时常用的一些库, 并且给一些简单的例子. 发现用python撸codejam非常合适: codejam的时间要求不严格(4/8分钟), 而且程序只要本地运行. 正好可以使用python简洁的语法和丰富的函数库.

collections

py自带的一些好用的数据结构...
https://docs.python.org/2/library/collections.html

from collections import Counter, deque, defaultdict

itertools

主要是用来穷举的时候它里面一些函数很好用...

https://docs.python.org/2/library/itertools.html

>>> from itertools import product, combinations   
>>> a = 'ABCD'; b='EFG'   
>>> for p in product(a,b):    
print ...

1. Introduction to Intractability

recall model of computation: DFA
a univeral model of computation: turing machine
→ no more powerful model of computation.
Turing machine can compute any function that can be computed by a physically harnessable process of the natural world.

bottom line: turing machine is a simple and universal ...

simplex algo: top 10 algo of the 20th century (ever?).

what is linear programming:
a general problem-solving model that works for:
shortest-path, maxflow, MST, matching, assignment, ...

1. Brewer-'s Problem

toy example: choose products to maximize profit.
...
feasible region: a convex polygon.

⇒ optimum solution appears at an extreme point.

standard ...

Goal: classify problems according to computational requirements.
bad new: for huge number of pbs we don't know...

1. Introduction to Reductions

shifing gears:

  • from individual problems to problem-solving models.
  • from linear/quard to polynomial/exponential pbs
  • from implementation details to conceptual framwork

suppose we could (not) solve pb X ...

1. Introduction to Data Compression

pb: reduce the size of a file, to save space/time for storing/transmitting.
applications: generic file compression(gzip), multimedia (mp3), communication(skype).

From binary data B, ⇒ generate a compressed representation C(B).

lossless compression: get exactly B from C(B)
compression ratio: |C(B ...


1. Regular Expressions

pb: pattern matching.

regular expression

Is a notation to specify a set of strings.
basic operations:

  • concatenation
  • or
  • closure: "0 or more appearances of chars"
  • parentheses


additional operations (added for convinence):

ex. [A-C]+ is equivalent to (A|B|C)(A|B|C)*.

吐槽名句:

2. REs and NFAs ...

今天简单介绍一下优先队列(priority queue, 以下简称PQ)这个数据结构的实现.

PQ又叫"堆"(heap), 但是可能优先队列这个名字更容易记忆它的用途: pq是一种队列, 不过不是先进先出(FIFO), 而是每次出队的元素永远是优先级最高的.

logical structure of PQ

个人感觉"堆"这个名字大概源于PQ的(逻辑上的)形状吧: PQ是一种树(tree), 准确的说, 是一种二叉树(binary tree), 说得再准确一点, 它是一种完全二叉树(complete binary tree): 没错, PQ是一种满足某些条件的完全二叉树.

所谓的"完全二叉树", 要满足:

  • 除了最后一层, 所有层都排满(没有非空节点)
  • 最后一层的所有非空节点都排在左边

一张图可以直观说明, 完全二叉树其实就是长得像这样:

一个完全二叉树能被成为PQ的话, 要满足的条件就是:

对于任何一个节点, 它的优先级都大于左右子节点的优先级.

比如下图 ...

1. Introduction to substring search

"most ingenious algorithm we've seen so far"
pb. having two strings, pattern and text, len(pattern)=M << len(text)=N, try to find pattern in text.

ex. indexOf method of String in java.

2. Brute-Force Substring Search

function signature:
public static int search(String ...

今天总结一下非常有用的快速排序(qsort)算法, 以及由此衍生的一些其他相关算法(Knuth shuffle, quick select, 3-way partition).

快速排序的算法可以用三句话描述:
[Algo]

  • 选择基准项(pivot element, 一般取第一个元素为pivot)
  • 把数组里所有小于pivot的移动到pivot左边, 大于pivot的移动到右边 ⇒ 此时pivot已经位于最终排序时的正确位置
  • 对pivot左右两个数组分别递归进行快速排序

由以上描述可见, qsort是一个递归算法, 我们可以把它的函数声明写成: void qsort(int[] a, int lo, int hi), 表示排序a[lo, hi]之间(闭区间)的所有元素.

quick partition

由上面描述可以见, qsort最关键的是第二步: 把数组元素以pivot分为两部分. 这个操作就是quick partition.

函数声明为: int partition(int[] a, int ...