# Problem

## Constraints

1. I have a collection of curves, $$C$$. It is a two dimensional array. The inner array contains rational numbers, where the next is greater or equal to the previous.

$$C_{k.i} = v\\ \{k \in \mathbb{Z}: 0 \le k \le 5\}\\ \{i \in \mathbb{Z}: 0 \le i \le 99\}\\ \{v \in \mathbb{N}: 0 \le v \le 1\}\\ C_{n.i} \le C_{n.j}\\ \{j \in \mathbb{Z}: i \le j \le 99\}$$

2. I have $$n$$ levels.

$$\{n \in \mathbb{Z}: 0 \le n \le 5 * 99\}$$

### Example

C = [[i / 100 for i in range(100)]] * 5
n = 20


For a given $$n$$ split it into five non-negative integer indexes. Which are used to index each curve and sum the result to get the total, $$t$$.

$$n = a + b + c + d + e\\ t = C_{1.a} + C_{2.b} + C_{3.c} + C_{4.d} + C_{5.e}$$

For each $$n$$ find the maximum $$t$$ for a given $$n$$. And what the values for $$a$$, $$b$$, $$c$$, $$d$$ and $$e$$ are.

# Solution

The way I solved this was through brute force:

1. Build list of tuples to store the maximum, $$o$$.
These tuples are (total, list of products).
2. Find the value for all products of $$a$$, $$b$$, $$c$$, $$d$$ and $$e$$.
3. For each product find the total of the curves, $$t$$.
1. If $$o_{n.0} = t$$ append [(a, b, c, d, e)] to $$o_{n.1}$$.
2. Otherwise if $$o_{n.0} \lt t$$ set $$o_{n}$$ to (t, [(a, b, c, d, e)]).
4. Output $$o$$.

In Python this can be expressed as: (variable names correlate with the ones defined above)

import itertools

o = [(-1, [])] * 495
for prod in itertools.product(range(100), repeat=5):
n = sum(prod)
t = sum(c[i] for c, i in zip(C, prod))
if o[n] == t:
o[n].append(prod)
elif o[n] < t:
o[n] = (t, [prod])


This runs in $$ki^k$$ time, which is rather slow.

# Question

I think the performance can be improved by using caching or a fancy algorithm. Can this algorithm's performance be reduced by an order of magnitude?

# Ideas

I though running through all values of $$n$$ adding the highest value $$v$$ to a running total. And adding the running total to the output.

This would run in $$O(kn)$$ time.

But this doesn't work correctly as if there are any curves that start off with a small gradient then the gradient increases to overtake all the other curves. It wouldn't be selected.

I thought about finding the maximum value a curve can be at the provided level. Then running through output and the maximum curve from $$n$$ backwards to see if there are any other totals that are greater than the current one.

This seems like it might work, and might run in $$O(n^2)$$ time, which is significantly smaller than $$O(ki^k)$$.

However I think it has similar problems to the above solution that I can't think of yet.

I've thought about vectorizing the curve into, $$l$$, straight lines. I'm not sure what this complexity is, but I'll call it $$v$$. From this it is easy to compare vectors to see which have greater starting points, and then a greater coefficient. Precomputing the intersections, $$s$$, also allows you to know when to switch to a different vector efficiently.

I've not fully thought this through, but it seems like it could be something like $$O((lk + s)n + (lk)^2 + v)$$.

It's easy to achieve $$O(n^4)$$ running time: iterate over all possible values of $$a,b,c,d$$, set $$e=n-a-b-c-d$$, compute $$C_a+C_b+C_c+C_d+C_e$$, and keep the best one found so far.

You can achieve $$O(n^3)$$ running time and $$O(n^2)$$ space with a meet-in-the-middle algorithm:

Step 1. Create an empty hash table. For each $$d,e$$ such that $$d+e\le n$$, add an entry to a hash table keyed on $$d+e$$ mapping to the value $$C_d+C_e$$; if it already has an entry for the key $$d+e$$, replace the existing entry if $$C_d+C_e$$ is larger than whatever was previously there, otherwise do nothing. (Save the value of $$d,e$$ whenever you update the entry, too.)

Step 2. For each combination $$a,b,c$$ such that $$a+b+c \le n$$, look up the key $$n-a-b-c$$ in the hash table. This gives you $$d,e$$ that maximizes $$C_d+C_e$$, subject to the requirement that $$d+e=n-a-b-c$$, i.e., that $$a+b+c+d+e=n$$. Now compute $$C_a+C_b+C_c+C_d+C_e$$. Keep the best combination you ever see.

You can achieve $$O(n^2)$$ time and space by keeping Step 1 above and replacing Step 2 with

Step 2'. For each combination $$a,r,s$$ such that $$a+r+s=n$$, look up the key $$r$$ in the hash table to find $$b,c$$ such that $$b+c=r$$ and look up the key $$s$$ in the hash table to find $$d,e$$ such that $$d+e=s$$. Compute $$C_a+C_b+C_c+C_d+C_e$$ and keep the best combination you ever see. You can iterate over all such combinations $$a,r,s$$ by iterating over $$a,r$$ such that $$a+r \le n$$, then setting $$s=n-a-r$$. There are $$O(n^2)$$ such combinations of $$a,r,s$$, and this algorithm does $$O(1)$$ work per combination, so the total running time is $$O(n^2)$$.

• @Peilonrayz, I meant what I wrote. $n$ is part of the input; $i$ isn't; so I'm not sure what $O(i^5)$ would mean. – D.W. May 1 '19 at 21:06
• @user50829, I don't understand your objection. Can you elaborate? I edited the answer to make the running time analysis more explicit. I also realized that I had reused the variable $t$ for something different than you used it for, which was confusing, so I edited my answer to fix that. I don't know what you mean by the "size" of $t$. I don't think the size of $t$ (whatever that means) is relevant to my Step 2'. It is relevant how large $r$ can get, but here $0 \le r \le n$, i.e., $O(n)$. – D.W. Jun 10 at 22:18