Блог пользователя Tameshk

Help with Problem from Tehran ICPC site
Автор Tameshk, история, 5 лет назад, По-английски

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]

  • Проголосовать: нравится
  • +19
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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$$$.

→ Ответить