CareerCup

How about dynamic programming:

f[i] the number of sentence made from s[:i]
f[0]=1
f[i]=\sum_j{f[j]*(s[j:i] in dictionary)}

return f[-1] as the result.

The cost would be o(n2)

Use Python and cost is o(log2(n))

def square(x):
		if x<0:
			return square(-x)
		else:
			return mul(x,x)
		
	def mul(x, y):
		if y==1:
			return x
		elif y==0:
			return 0
		else:
Return mul(x,y>>1)<<1+mul(x,y-(y>>1)<<1)

Can't we use Kmeans algorithm for this purpose?

I also think this is the dynamic programming problem.

/**
* we define the following function f(int []a, int k, Char [] f)
* where a is the set of players used
* k is the required # of followers
* f is list of current followers
* output is the # player used.
* f(a, k, f)=min_i {f(a U i, k, merge(f, arr[i]))}
*/

/**
    * Given 3 Arrays of integer sorted in ascending order, get the sum of minimum difference using one element from each array. 
    * The simple way has complexity O(n^3). However, we use the knowledge that, if a[i]=min(a[i],b[j],c[k]), then the best possible step is i++. By doing this way, the complexity is O(n) or more exactly O(3n)
    */
    public static void minDifference(int [] arr1, int []arr2, int []arr3)
    {
        if (arr1==null || arr1.length<1 || arr2==null || arr2.length<1 || arr3==null || arr3.length<1)
        {
            System.out.println("Illegal input");
            return;
        }
        long min=Long.MAX_VALUE;
        long tmp;
        int i, ii, j, jj, k, kk;
        i=0;
        j=0;
        k=0;
        ii=0;
        jj=0;
        kk=0;
        while(i<arr1.length && j<arr2.length && k<arr3.length)
        {
            // check the best until now
            tmp=(long) Math.abs(arr1[i]-arr2[j])+Math.abs(arr2[j]-arr3[k])+Math.abs(arr1[i]-arr3[k]);
            if (min>tmp)
            {
                min=tmp;
                ii=i;
                jj=j;
                kk=k;
            }
            // this is the best of possible
            if (tmp<=0)
            {
            	break;
            }
            // find next step
            // we know that, if a[i]=min(a[i],b[j],c[k]), then the best possible step is i++
            if (i<arr1.length-1 && arr1[i]<=arr2[j] && arr1[i]<=arr3[k])
            {
                i++;
            }
            else if (j<arr2.length-1 && arr2[j]<=arr1[i] && arr2[j]<=arr3[k])
            {
                j++;
            }
            else if (k<arr3.length-1 && arr3[k]<=arr1[i] && arr3[k]<=arr2[j])
            {
                k++;
            }
            else
            {
                // though it should never be reached
                break;
            }
        }
        System.out.println("The sum of the minimum differences is "+min+": a["+ii+"]="+arr1[ii]+", b["+jj+"]="+arr2[jj]+" and c["+kk+"]="+arr3[kk]);
    }