A fastest algorithm optimization challenge This is my first experiment with an asymptotic complexity challenge although I am happy with answers entirely in code as long as they come with an explanation of their time complexity.

I have the following problem.

Consider tasks T_1, ... T_n and procs M_1, ... , M_m.  Each task takes a certain amount of time to perform depending on the procs. 

Each task also costs a certain amount to perform depending on the procs.

The tasks have to be done in strict order (they can't be done in parallel) and it takes time to change proc.  A task can't be moved from one proc to another after it has been started. 

Finally, each task must be completed by a certain time. 

the task

The objective is to give an algorithm (or some code) that given five tables of the form above, minimizes the total cost to complete all the tasks while making sure all the tasks are completed by their deadlines. If this isn't possible we just report that it can't be done.

score

You should give the big Oh complexity of your solution in terms of the variables n, m and d, where d is the last deadline.  There should be no unnecessary constants in your big Oh complexity. So O(n/1000) should be written as O(n), for example. 

Your score is calculated simply by setting n = 100, m = 100 and d = 1000 into your stated complexity.  You want the smallest score possible.

tie breaker

In the case of a tie, the first answer wins.



added notes

log in the time complexity of an answer will be taken base 2.

score board


10^202 from KSFT  (Python) First submitted so gets the bounty.
10^202 from Dominik Müller (Scala)
Score: 10^202

I kinda wish we had LaTeX support now...

Since no one else has answered, I thought I'd try, even though is isn't very efficient. I'm not sure what the big O of it is, though.

I think it works. At least, it does for the only test case posted.

It takes input like in the question, except without the machine or task number labels, and with semicolons instead of line breaks.

import itertools
time = [[int(j) for j in i.split()] for i in raw_input().split(";")]
cost = [[int(j) for j in i.split()] for i in raw_input().split(";")]
nmachines=len(time)
ntasks=len(time[0])
switchtime = [[int(j) for j in i.split()] for i in raw_input().split(";")]
switchcost = [[int(j) for j in i.split()] for i in raw_input().split(";")]
deadline = [int(i) for i in raw_input().split()]
d={}
m=itertools.product(range(nmachines),repeat=ntasks)
for i in m:
    t=-switchtime[i[-1]][i[0]]
    c=-switchcost[i[-1]][i[0]]
    e=0
    meetsdeadline=True
    for j in range(ntasks):
        t+=switchtime[i[e-1]][i[e]]+time[i[e]][j]
        c+=switchcost[i[e-1]][i[e]]+cost[i[e]][j]
        e+=1
        if t&gt;deadline[j]:
            meetsdeadline=False
    if meetsdeadline:
        d[(c,t)]=i
print min(d.keys()),d[min(d.keys())]