### TooruQuyetCoVOI's blog

By TooruQuyetCoVOI, history, 5 weeks ago,

Find the sum of k distinct quadruples ai + aj + bx + by where the sum is maximized (i, j can be equal)? Four sets i, j, x, y are considered distinct if at least one of the four numbers is different from the corresponding number in the other set.

The first line contains 3 positive integers: n, m, k (n <= 1000, m <= 1000, k ≤ n^2 * m^2).

The second line contains n positive integers: A1, A2, ..., An.

The last line contains m positive integers: B1, B2, ..., Bm (Ai, Bi ≤ 10^6).

• +1

 » 5 weeks ago, # |   +1 Auto comment: topic has been updated by TooruQuyetCoVOI (previous revision, new revision, compare).
 » 5 weeks ago, # | ← Rev. 2 →   +19 Consider $A(x) = \sum_{i = 1}^{n} x^{a_i}$ and $B(x) = \sum_{i = 1}^{m} x^{b_i}$. Consider $A(x)^2 B(x)^2$. Then, without grouping any equal terms together, each of the $n^2m^2$ terms in $A(x)^2 B(x)^2$ corresponds to a unique quadruple. After grouping, you only need the coefficients of some of the highest powers, and this can be done in $O(n + m + A \log A)$ where $A = \max_{i} \max(A_i, B_i)$.
•  » » 4 weeks ago, # ^ |   +1 Ty so much I got it
•  » » 4 weeks ago, # ^ |   0 Actually I comprehend the concept, but I'm currently grappling with devising a solution that satisfies the requirement of O(n + m + AlogA). I'm having difficulty determining the approach to achieve this time complexity, can you help me with this?
•  » » » 4 weeks ago, # ^ |   +3 The polynomials A and B have size O(A) each, and constructing them takes O(n + m) time. Computing the square of their product is doable in O(A log A) using FFT (compute convolution 3 times). Now that you have this product, you keep on subtracting $x^d$ from the polynomial, where d is the degree of the polynomial so far. We need to do this k times. Note that we can group together subtraction of the same $x^i$-s, and thus this can be simulated in O(min(k, A)) time.
•  » » » » 2 weeks ago, # ^ |   0 I think the intended solution is to do $O(n^2 + m^2 + min(k,A))$. Because it is a bit of a bazooka to use FFT for two polynomials which have very few non-zero coefficients, you can instead just loop through all pairs.
 » 4 weeks ago, # | ← Rev. 2 →   +1 I think Technical Solutions Engineer is the best option
 » 2 weeks ago, # |   -11 Enterprise System Engineer Linux