3
$\begingroup$

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

Task

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][0] == t:
        o[n][1].append(prod)
    elif o[n][0] < 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)$.

$\endgroup$
2
$\begingroup$

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,t,u$ such that $a+t+u=n$, look up the key $t$ in the hash table to find $b,c$ such that $b+c=t$ and look up the key $u$ in the hash table to find $d,e$ such that $d+e=u$. Compute $C_a+C_b+C_c+C_d+C_e$ and keep the best combination you ever see. (Note that you can iterate over all such combinations $a,t,u$ by iterating over $a,t$ such that $a+t \le n$, then setting $u=n-a-t$.)

$\endgroup$
  • $\begingroup$ Oh wow, this is insane. :O I'm assuming that $O(n^*)$ is meant to be $O(i^*)$. $\endgroup$ – Peilonrayz May 1 at 18:36
  • $\begingroup$ @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. $\endgroup$ – D.W. May 1 at 21:06
  • $\begingroup$ Ok, that both does and doesn't make sense to me. However as my understanding of big-O is made up, I'll bow to your knowledge. $\endgroup$ – Peilonrayz May 1 at 21:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.