最大化 A[i]*B[i] + A[i]*B[j] + A[j]*B[j], i != j, 给定两个无序列表的正整数
Maximize A[i]*B[i] + A[i]*B[j] + A[j]*B[j], i != j, given two unordered lists of positive integers
你能帮我算一下算法吗：
给定 2 个大小相等的数组 a[] 和 b[]，整数大于或等于 1.
找到不相等的索引 i 和 j (i != j) 使得值 -
max(a[i]*b[i] + a[i] * b[j] + a[j] * b[j], a[i]*b[i] + a[j] * b[i] + a[j] * b[j])
将是最大值。
示例：
a = [1, 9, 6, 6] 和 b = [9, 1, 6, 6].
最大值将在 i = 2 和 j = 3（从零开始的索引）：
a[2]*b[2] + a[2]*b[3] + a[3] * b[3] = 6*6+6*6+6*6 = 108
有没有办法在不到二次方的时间内找到 i 和 j？
同样的问题是在不到二次方的时间内找到 objective 函数值？
谢谢！
是的，有一个 O(n log n) 时间的算法。
如果我们看函数 f(x) = max {a[i] b[i] + a[i] x |一世}，
它描绘出一个较低的（凸面）船体。基本够评价了
f(b[j]) + a[j] b[j] 对于每个 j，有一个关键点
我们需要 i ≠ j.
为了解决这个问题，我们转向增量船体算法
摊销 O(log n) 时间插入。规范算法保持
hull 按排序顺序排列，允许 O(log n) 次查询。从...开始
一个空壳，对于每个索引 i，我们查询 i 然后插入 i。做这个
一次顺序，一次逆序，取最大值
这是我尝试实现 。我认为 i != j 限制使这变得更加复杂，但无论哪种方式，我都欢迎提出改进代码的建议。最后有一个对抗暴力的测试。
线A[i]*x + A[i]*B[i]的上包络构造依赖于安德鲁的单调链凸包算法应用于从线转换的对偶点。
Python代码：
# Upper envelope of lines in the plane
from fractions import Fraction
import collections
def get_dual_point(line):
return (line[0], -line[1])
def get_primal_point(dual_line):
return (dual_line[0], -dual_line[1])
def get_line_from_two_points(p1, p2):
if p1[0] == p2[0]:
return (float('inf'), 0)
m = Fraction(p1[1] - p2[1], p1[0] - p2[0])
b = -m * p1[0] + p1[1]
return (m, b)
def cross_product(o, a, b):
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
# lower_hull has the structure [(dual_point, original_line, leftmost_x, index)]
def get_segment_idx(lower_hull, x):
lo = 0
hi = len(lower_hull) - 1
# Find the index of the first
# x coordinate greater than x
while lo < hi:
mid = lo + (hi - lo + 1) // 2
if lower_hull[mid][2] <= x:
lo = mid
else:
hi = mid - 1
return lo
# Assumes we add points in order of increasing x-coordinates
def add_right_to_lower_hull(lower_hull, point):
while len(lower_hull) > 0 and lower_hull[-1][0][0] == point[0][0] and lower_hull[-1][0][1] > point[0][1]:
lower_hull.pop()
while len(lower_hull) > 1 and cross_product(lower_hull[-2][0], lower_hull[-1][0], point[0]) <= 0:
lower_hull.pop()
if not lower_hull or lower_hull[-1][0][0] != point[0][0]:
lower_hull.append(point)
# Each segment of the lower hull
# in the dual plane is a line intersection
# in the primal plane.
if len(lower_hull) == 1:
lower_hull[0][2] = -float('inf')
else:
line = get_line_from_two_points(lower_hull[-1][0], lower_hull[-2][0])
lower_hull[-1][2] = get_primal_point(line)[0]
return lower_hull
# Assumes we add points in order of decreasing x-coordinates
def add_left_to_lower_hull(lower_hull, point):
while len(lower_hull) > 0 and lower_hull[0][0][0] == point[0][0] and lower_hull[0][0][1] > point[0][1]:
lower_hull.popleft()
while len(lower_hull) > 1 and cross_product(lower_hull[1][0], lower_hull[0][0], point[0]) >= 0:
lower_hull.popleft()
if not lower_hull or lower_hull[0][0][0] != point[0][0]:
lower_hull.appendleft(point)
# Each segment of the lower hull
# in the dual plane is a line intersection
# in the primal plane.
if len(lower_hull) == 1:
lower_hull[0][2] = -float('inf')
else:
line = get_line_from_two_points(lower_hull[0][0], lower_hull[1][0])
lower_hull[1][2] = get_primal_point(line)[0]
return lower_hull
# Maximise A[i] * B[i] + A[i] * B[j] + A[j] * B[j]
def f(A, B):
debug = False
if debug:
print("A: %s" % A)
print("B: %s" % B)
best = -float('inf')
best_idxs = ()
indexed_lines = [((A[i], A[i] * B[i]), i) for i in range(len(A))]
# Convert to points in the dual plane
# [dual_point, original_line, leftmost x coordinate added later, original index]
dual_points = [[get_dual_point(line), line, None, i] for line, i in indexed_lines]
# Sort points by x coordinate ascending
sorted_points = sorted(dual_points, key=lambda x: x[0][0])
if debug:
print("sorted points")
print(sorted_points)
# Build lower hull, left to right
lower_hull = []
add_right_to_lower_hull(lower_hull, sorted_points[0])
for i in range (1, len(sorted_points)):
# Query the point before inserting it
# because of the stipulation that i != j
idx = sorted_points[i][3]
segment_idx = get_segment_idx(lower_hull, B[idx])
m, b = lower_hull[segment_idx][1]
j = lower_hull[segment_idx][3]
candidate = m * B[idx] + b + A[idx] * B[idx]
if debug:
print("segment: %s, idx: %s, B[idx]: %s" % (segment_idx, idx, B[idx]))
if candidate > best:
best = candidate
best_idxs = (idx, j)
add_right_to_lower_hull(lower_hull, sorted_points[i])
if debug:
print("lower hull")
print(lower_hull)
# Build lower hull, right to left
lower_hull = collections.deque()
lower_hull.append(sorted_points[len(sorted_points) - 1])
for i in range (len(sorted_points) - 2, -1, -1):
# Query the point before inserting it
# because of the stipulation that i != j
idx = sorted_points[i][3]
segment_idx = get_segment_idx(lower_hull, B[idx])
m, b = lower_hull[segment_idx][1]
j = lower_hull[segment_idx][3]
candidate = m * B[idx] + b + A[idx] * B[idx]
if debug:
print("segment: %s, idx: %s, B[idx]: %s" % (segment_idx, idx, B[idx]))
if candidate > best:
best = candidate
best_idxs = (idx, j)
add_left_to_lower_hull(lower_hull, sorted_points[i])
if debug:
print("lower hull")
print(lower_hull)
return best, best_idxs
#A = [1, 9, 6, 6]
#B = [9, 1, 6, 6]
#print("")
#print(f(A, B))
# Test
import random
def brute_force(A, B):
best = -float('inf')
best_idxs = ()
for i in range(len(A)):
for j in range(len(B)):
if i != j:
candidate = A[i] * B[i] + A[i] * B[j] + A[j] * B[j]
if candidate > best:
best = candidate
best_idxs = (i, j)
return best, best_idxs
num_tests = 500
n = 20
m = 1000
for _ in range(num_tests):
A = [random.randint(1, m) for i in range(n)]
B = [random.randint(1, m) for i in range(n)]
_f = f(A, B)
_brute = brute_force(A, B)
if _f[0] != _brute[0]:
print("Mismatch")
print(A)
print(B)
print(_f, _brute)
print("Done testing.")
你能帮我算一下算法吗：
给定 2 个大小相等的数组 a[] 和 b[]，整数大于或等于 1.
找到不相等的索引 i 和 j (i != j) 使得值 -
max(a[i]*b[i] + a[i] * b[j] + a[j] * b[j], a[i]*b[i] + a[j] * b[i] + a[j] * b[j])
将是最大值。
示例：
a = [1, 9, 6, 6] 和 b = [9, 1, 6, 6].
最大值将在 i = 2 和 j = 3（从零开始的索引）：
a[2]*b[2] + a[2]*b[3] + a[3] * b[3] = 6*6+6*6+6*6 = 108
有没有办法在不到二次方的时间内找到 i 和 j？ 同样的问题是在不到二次方的时间内找到 objective 函数值？
谢谢！
是的，有一个 O(n log n) 时间的算法。
如果我们看函数 f(x) = max {a[i] b[i] + a[i] x |一世}， 它描绘出一个较低的（凸面）船体。基本够评价了 f(b[j]) + a[j] b[j] 对于每个 j，有一个关键点 我们需要 i ≠ j.
为了解决这个问题，我们转向增量船体算法 摊销 O(log n) 时间插入。规范算法保持 hull 按排序顺序排列，允许 O(log n) 次查询。从...开始 一个空壳，对于每个索引 i，我们查询 i 然后插入 i。做这个 一次顺序，一次逆序，取最大值
这是我尝试实现 i != j 限制使这变得更加复杂，但无论哪种方式，我都欢迎提出改进代码的建议。最后有一个对抗暴力的测试。
线A[i]*x + A[i]*B[i]的上包络构造依赖于安德鲁的单调链凸包算法应用于从线转换的对偶点。
Python代码：
# Upper envelope of lines in the plane
from fractions import Fraction
import collections
def get_dual_point(line):
return (line[0], -line[1])
def get_primal_point(dual_line):
return (dual_line[0], -dual_line[1])
def get_line_from_two_points(p1, p2):
if p1[0] == p2[0]:
return (float('inf'), 0)
m = Fraction(p1[1] - p2[1], p1[0] - p2[0])
b = -m * p1[0] + p1[1]
return (m, b)
def cross_product(o, a, b):
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
# lower_hull has the structure [(dual_point, original_line, leftmost_x, index)]
def get_segment_idx(lower_hull, x):
lo = 0
hi = len(lower_hull) - 1
# Find the index of the first
# x coordinate greater than x
while lo < hi:
mid = lo + (hi - lo + 1) // 2
if lower_hull[mid][2] <= x:
lo = mid
else:
hi = mid - 1
return lo
# Assumes we add points in order of increasing x-coordinates
def add_right_to_lower_hull(lower_hull, point):
while len(lower_hull) > 0 and lower_hull[-1][0][0] == point[0][0] and lower_hull[-1][0][1] > point[0][1]:
lower_hull.pop()
while len(lower_hull) > 1 and cross_product(lower_hull[-2][0], lower_hull[-1][0], point[0]) <= 0:
lower_hull.pop()
if not lower_hull or lower_hull[-1][0][0] != point[0][0]:
lower_hull.append(point)
# Each segment of the lower hull
# in the dual plane is a line intersection
# in the primal plane.
if len(lower_hull) == 1:
lower_hull[0][2] = -float('inf')
else:
line = get_line_from_two_points(lower_hull[-1][0], lower_hull[-2][0])
lower_hull[-1][2] = get_primal_point(line)[0]
return lower_hull
# Assumes we add points in order of decreasing x-coordinates
def add_left_to_lower_hull(lower_hull, point):
while len(lower_hull) > 0 and lower_hull[0][0][0] == point[0][0] and lower_hull[0][0][1] > point[0][1]:
lower_hull.popleft()
while len(lower_hull) > 1 and cross_product(lower_hull[1][0], lower_hull[0][0], point[0]) >= 0:
lower_hull.popleft()
if not lower_hull or lower_hull[0][0][0] != point[0][0]:
lower_hull.appendleft(point)
# Each segment of the lower hull
# in the dual plane is a line intersection
# in the primal plane.
if len(lower_hull) == 1:
lower_hull[0][2] = -float('inf')
else:
line = get_line_from_two_points(lower_hull[0][0], lower_hull[1][0])
lower_hull[1][2] = get_primal_point(line)[0]
return lower_hull
# Maximise A[i] * B[i] + A[i] * B[j] + A[j] * B[j]
def f(A, B):
debug = False
if debug:
print("A: %s" % A)
print("B: %s" % B)
best = -float('inf')
best_idxs = ()
indexed_lines = [((A[i], A[i] * B[i]), i) for i in range(len(A))]
# Convert to points in the dual plane
# [dual_point, original_line, leftmost x coordinate added later, original index]
dual_points = [[get_dual_point(line), line, None, i] for line, i in indexed_lines]
# Sort points by x coordinate ascending
sorted_points = sorted(dual_points, key=lambda x: x[0][0])
if debug:
print("sorted points")
print(sorted_points)
# Build lower hull, left to right
lower_hull = []
add_right_to_lower_hull(lower_hull, sorted_points[0])
for i in range (1, len(sorted_points)):
# Query the point before inserting it
# because of the stipulation that i != j
idx = sorted_points[i][3]
segment_idx = get_segment_idx(lower_hull, B[idx])
m, b = lower_hull[segment_idx][1]
j = lower_hull[segment_idx][3]
candidate = m * B[idx] + b + A[idx] * B[idx]
if debug:
print("segment: %s, idx: %s, B[idx]: %s" % (segment_idx, idx, B[idx]))
if candidate > best:
best = candidate
best_idxs = (idx, j)
add_right_to_lower_hull(lower_hull, sorted_points[i])
if debug:
print("lower hull")
print(lower_hull)
# Build lower hull, right to left
lower_hull = collections.deque()
lower_hull.append(sorted_points[len(sorted_points) - 1])
for i in range (len(sorted_points) - 2, -1, -1):
# Query the point before inserting it
# because of the stipulation that i != j
idx = sorted_points[i][3]
segment_idx = get_segment_idx(lower_hull, B[idx])
m, b = lower_hull[segment_idx][1]
j = lower_hull[segment_idx][3]
candidate = m * B[idx] + b + A[idx] * B[idx]
if debug:
print("segment: %s, idx: %s, B[idx]: %s" % (segment_idx, idx, B[idx]))
if candidate > best:
best = candidate
best_idxs = (idx, j)
add_left_to_lower_hull(lower_hull, sorted_points[i])
if debug:
print("lower hull")
print(lower_hull)
return best, best_idxs
#A = [1, 9, 6, 6]
#B = [9, 1, 6, 6]
#print("")
#print(f(A, B))
# Test
import random
def brute_force(A, B):
best = -float('inf')
best_idxs = ()
for i in range(len(A)):
for j in range(len(B)):
if i != j:
candidate = A[i] * B[i] + A[i] * B[j] + A[j] * B[j]
if candidate > best:
best = candidate
best_idxs = (i, j)
return best, best_idxs
num_tests = 500
n = 20
m = 1000
for _ in range(num_tests):
A = [random.randint(1, m) for i in range(n)]
B = [random.randint(1, m) for i in range(n)]
_f = f(A, B)
_brute = brute_force(A, B)
if _f[0] != _brute[0]:
print("Mismatch")
print(A)
print(B)
print(_f, _brute)
print("Done testing.")