minfuds - coding puzzle

A

alphonse23

Would anybody be up to helping me solve this? It's one of the questions on Codility. According to them, it should only take 30 mins.

Two non-empty zero-indexed arrays A and B, each consisting of N integers, are given. Four functions are defined based on these arrays:
F(X,K) = A[K]*X + B[K]
U(X) = max{ F(X,K) : 0 ≤ K < N }
D(X) = min{ F(X,K) : 0 ≤ K < N }
S(X) = U(X) − D(X)
Write a function:
double solution(int A[], int B[], int N);
that, given two arrays A and B consisting of N integers each, returns the minimum value of S(X) where X can be any real number.
For example, given the following arrays A and B consisting of three elements each:
A[0] = -1 B[0] = 3
A[1] = 1 B[1] = 0
A[2] = 0 B[2] = 2
the function should return 0.5 because:
U(X) = −1*X + 3 if X ≤ 1
U(X) = 0*X + 2 if 1 ≤ X ≤ 2
U(X) = 1*X + 0 if 2 ≤ X
and:
D(X) = 1*X + 0 if X ≤ 1.5
D(X) = −1*X + 3 if 1.5 ≤ X
so for X = 1.5, function S(X) is equal to 0.5 and this is the minimum value of this function.
Assume that:
N is an integer within the range [1..100,000];
each element of array A is an integer within the range [−1,000..1,000];
each element of array B is an integer within the range [−1,000..1,000].
Complexity:
expected worst-case time complexity is O(N*log(N));
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.

I'm not sure how to solve it. I feel like it's the equivalent of finding the minimum of a function on a graph. I'd know how to do that in algebra/calculus, but not with code. Also, I'm not sure why their example skipped A[2] = 0 and B[2] = 2 for D(X).

This is as far as I got:

def solution(A, B):
# write your code here...
min = 0
return min

def S(A,B,x):
return U(A,B,x) - D(A,B,x)

def F(a,x,b):
return a*x + b

def U(A,B,x):
max = F(A[0],x,B[0])
for i in range(1,len(A)):
u = F(A,x,B)
if max < u: max = u
return max

def D(A,B,x):
min = F(A[0],x,B[0])
for i in range(1,len(A)):
d = F(A,x,B)
if min > d: min = d
return min
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,733
Messages
2,569,440
Members
44,832
Latest member
GlennSmall

Latest Threads

Top