5
\$\begingroup\$

Problem Description

Given:

  • a function \$f(a, b, c, d, e) = \frac{a \times b}c + \frac de\$
  • an array \$x = [x_1, x_2, x_3, x_4, ..., x_n]\$ of non-distinct integers
  • a target value \$k\$

What is the most efficient way, in terms of worst-case \$n\$, to find 5 distinct indices \$x_a, x_b, x_c, x_d, x_e\$ from \$x\$ such that \$f(x[x_a], x[x_b], x[x_c], x[x_d], x[x_e]) = k\$?

Example solutions

Example 1 (single solution):

\$x = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], k = 5\$

Solution 1:

\$[1, 4, 2, 9, 3]\$ as \$f(x[1], x[4], x[2], x[9], x[3])\$ evaluates to \$5\$.

Example 2 (multiple solutions):

\$x = [0, -1, 1, -1, 0, -1, 0, 1], k = 0\$

Solution 2 (of many solutions):

\$[1, 2, 3, 5, 7]\$ OR \$[0, 1, 2, 4, 7]\$

Example 3 (no solution):

\$x = [0, -1, 1, -1, 0, -1, 0, 1], k = 8\$

Solution 3:

\$-1\$ (no solution)

Example 4 (intermediary floats):

\$x = [2, 3, 5, 4, 5, 1], k = 2\$

Solution 4:

\$[2, 3, 5, 4, 5]\$

| improve this question | | | | |
\$\endgroup\$
  • \$\begingroup\$ Are you given a function with some number of variables an array and a third value? Also, I think the most efficient way is just brute force permutations from the array. \$\endgroup\$ – fəˈnɛtɪk Jun 12 '18 at 22:09
  • \$\begingroup\$ @fəˈnɛtɪk brute force with early stopping for branches of values larger than k? Also, the interchangeability of a*b == b*a seems important? \$\endgroup\$ – Seanny123 Jun 12 '18 at 22:14
  • \$\begingroup\$ @fəˈnɛtɪk The function is fixed. I think there might be some way to optimize this solution like two sum, but I haven't been able to figure out how yet. \$\endgroup\$ – versatile parsley Jun 12 '18 at 22:15
  • 1
    \$\begingroup\$ What exactly does the array contain? Floats? Integers? Positive integers? \$\endgroup\$ – Arnauld Jun 12 '18 at 23:36
  • 2
    \$\begingroup\$ Do we know if k is always an integer? it is not specified in the question. \$\endgroup\$ – fəˈnɛtɪk Jun 21 '18 at 16:17
1
\$\begingroup\$

Python3, O(n^3 log n)

from math import gcd
from functools import reduce

def lcm(x,y):
    return x//gcd(x,y)*y

def label(l):
    res=[(v,i) for i,v in enumerate(l)]
    res.sort()
    return res

def sortcombine(l):
    l.sort()
    res=[]
    oldval=None
    for val,how in l:
        if val==oldval:
            res[-1][1].append(how)
        else:
            oldval=val
            res.append((val,[how]))
    return res

def getabc(L,xl):
    N=len(xl)
    res=[]
    lasta=None
    for ai in range(N):
        a,al=xl[ai]
        if a==lasta:
            continue
        lasta=a
        lastb=None
        for bi in range(ai+1,N):
            b,bl=xl[bi]
            if b==lastb:
                continue
            lastb=b
            lastc=None
            for c,cl in xl:
                if c in [0,lastc] or cl in [al,bl]:
                    continue
                lastc=c
                res.append((L//c*a*b,(al,bl,cl)))
    return sortcombine(res)

def getde(L,xl):
    res=[]
    xl.reverse()
    lastd=None
    for d,dl in xl:
        if lastd==d:
            continue
        lastd=d
        laste=None
        for e,el in xl:
            if e in [0,laste] or el==dl:
                continue
            laste=e
            res.append((L//e*d,(dl,el)))
    return sortcombine(res)

def solve(l,k):
    xl=label(l)
    L=reduce(lcm,[v for v in l if v!=0],1)
    k*=L
    abc=getabc(L,xl)
    de=getde(L,xl)
    i=0
    j=len(de)-1
    while i<len(abc) and j>=0:
        v1,ls1=abc[i]
        v2,ls2=de[j]
        s=v1+v2
        if s==k:
            for l1 in ls1:
                s=set(l1)
                for l2 in ls2:
                    if s.isdisjoint(l2):
                        return list(l1+l2)
            i+=1
            j-=1
        elif s<k:
            i+=1
        else:
            j-=1
    return None

Try it online!

Multiply the equation by the LCM of the x values to avoid floating point or fractions. Find all possible values of ab/c (using ab=ba but that's only for a factor of 1/2) and d/e, sort them and try to add them to the wanted result. The sorting means we don't have to try all combinations.

There are O(n^3) possible values for ab/c, sorting them gives the log. The other steps are faster than that.

The while loop may be repeated O(n^3) times, but the case s==k can only occur O(n^2) times. If we don't find a solution and stop in this case, then the sizes of ls1 and ls2 (number of ways to obtain the corresponding value) must be in O(n) resp. O(1) (except in the case when the value is 0, but luckily that doesn't happen O(n) times).

| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ (but I have no proof that this is the most efficient way) \$\endgroup\$ – Christian Sievers Jun 23 '18 at 14:43
  • \$\begingroup\$ How does this determine that it isn't using the same element twice between AB/C and D/E \$\endgroup\$ – fəˈnɛtɪk Jun 24 '18 at 14:42
  • \$\begingroup\$ @fəˈnɛtɪk That's in the isdisjoint call. And there are a lot of yet unmentioned details how it handles repeated elements: group and label the elements, i.e. replace [1,2,1,...] with [(1,0),(1,1),(2,0),...], and use the low labels for abc and (by reversing the list) the high labels for de, so if there is intersection then that combination is really not possible. \$\endgroup\$ – Christian Sievers Jun 24 '18 at 20:02
  • \$\begingroup\$ (now changed the labels to be the indices, so in the above example we get [(1,0),(1,2),(2,1),...]) \$\endgroup\$ – Christian Sievers Jun 29 '18 at 23:02

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.