Tameshk's blog

Help with Problem from Tehran ICPC site
By Tameshk, history, 5 years ago, In English

Given two arrays A and B, find the number of different numbers can reach by adding exactly one element in A and exactly one form B. Constraints:|A|,|B| <= 2*10^5 0 <= A_i,B_i <= 2*10^5 No two elements in A and nor from B is same, However may be same numbers in A and B;
For example: A = [1,3,5] B = [1,3,7] ans = 6, [2,4,6,8,10,12]

  • Vote: I like it
  • +19
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Tameshk (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

It's done directly by FFT. Consider 2 polynomials A(x) and B(x) with A(x) = sum of x^A_i and B(x) defined analogously. Then what you're interested in is computing A(x)*B(x) which is precisely what FFT is used for. In addition, I seriously doubt there's any other way to approach it. Karatsuba could work as well but it also aims at faster computing of the product of 2 polynomials. Maybe you could use bitset to try to prune the brute force, but the standard way to go is FFT

→ Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

This may be an overkill, but the problem is straightforward convolution and can be solved using FFT.
Consider two polynomials $$$P_A = \sum{x^{A_i}}$$$ and $$$P_B = \sum{x^{B_i}}$$$.
The answer is the number of terms with positive coefficients in $$$P_A \cdot P_B$$$.

→ Reply