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[i],x,B[i])
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[i],x,B[i])
if min > d: min = d
return min
--
http://mail.python.org/mailman/listinfo/python-list
