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).
Auto comment: topic has been updated by TooruQuyetCoVOI (previous revision, new revision, compare).
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)$$$.
Ty so much I got it
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?
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.
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.
I think Technical Solutions Engineer is the best option
Enterprise System Engineer Linux