st0le

def find_rotation_binary_search(L):
    left,right = 0,len(L) - 1
	while L[left] > L[right]:
		mid = (left + right) / 2
		if L[mid] > L[right]:
			left = mid + 1
		else:
			right = mid
	return left

st0le

import random
L = 10
lst = [random.randint(0,100) for _ in xrange(L)]
lst.sort()
K = random.randint(0,L)
lst = lst[K:] + lst[:K] # rotate by random K

def find_rotation_naive(L):
    for i in xrange(len(L) - 1):
		if L[i] > L[i+1]:

st0le

import pqueue

def dijkstra(graph,src,dst):
	min_dist = dict()        # stores shortest path from src, ie min_dist[u] = w denotes, weight of shortest path (src->u) = w
	prev_vertex = dict()	 # prev_vertex[u], stores the previous node on the shortest path from src to u
	pq = pqueue.pqueue()
	pq.push( (0, src) )
	min_dist[src] = 0        # distance to source is 0. 
	prev_vertex[src] = None  # no previous node for src
	while not pq.empty():

st0le

def max_diff_naive(L):
    max_diff = start = end = 0
    for i in xrange(len(L)):
        for j in xrange(i+1,len(L)):
            if max_diff < L[j] - L[i]:
                start,end = i,j
                max_diff = L[j] - L[i]
    return max_diff,start,end

st0le

def max_diff_linear(L):
    min_index = 0
    max_diff = start = end = 0
    for i in xrange(len(L)):
        if L[i] < L[min_index]: min_index = i
        if max_diff < L[i] - L[min_index]:
            max_diff = L[i] - L[min_index]
            start,end = min_index,i
    return max_diff,start,end

st0le

import sys,graphs,itertools

def prepare_graph():
    diff_by_1 = lambda (x,y): len(x) == len(y) and sum(1 for a,b in zip(x,y) if a != b) == 1
    graph = {}
    for x,y in filter(diff_by_1,itertools.product(words,repeat=2)):
        if x not in graph: graph[x] = []
        if y not in graph: graph[y] = []
        graph[x].append( ( y , 1) )
        graph[y].append( ( x , 1) )

st0le

import random

rand_list = sorted([random.randint(-100,100) for _ in xrange(7)])
K = random.randint(0,200)

def subset_sum(lst,K):
    lst.sort()
    sz = len(lst)
    def subset_sum_helper(index,s):

st0le

import random
r = {random.randint(10,100) for i in xrange(10)}
lst = random.sample(r,len(r))
l = lst[:2] + lst[2:] * 2
random.shuffle(l)

def missing_2_numbers(lst):
    xor = reduce(lambda a,b : a ^ b, lst)
    mask = (xor & -xor) #get the right most set bit.
    

st0le

 
def subset_sum(lst,K):
    lst.sort()
    sz = len(lst)
    def subset_sum_helper(index,s):
        if index == sz or s >= K : return s == K
        return subset_sum_helper(index + 1, s) or subset_sum_helper(index + 1, s + lst[index])
    return subset_sum_helper(0 , 0 )
 

st0le

def subset_sum_dp(lst,K):
    ways = {0}
    lst.sort()
    for v in lst:
        t = set()
        for w in ways:
            nv = v+w
            if nv == K : return True
            if nv < K:
                t.add(v+w)