← All problems

Sorting X+Y (Pairwise Sums)

Given sorted or unsorted sets X={x1,,xn}X=\{x_1,\ldots,x_n\} and Y={y1,,yn}Y=\{y_1,\ldots,y_n\} of real numbers, output the multiset X+Y={xi+yj:1i,jn}X+Y=\{x_i+y_j:1\leq i,j\leq n\} in nondecreasing order. Determine whether this can be done in O(n2)O(n^2) time in a standard real-comparison model.

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li