Can someone share the editorial of Filling the Coffers: ANWCC02 question of CodeCharades 2019 contest. asked 22 Jan, 01:16

Assume $ m \le n$, $$ P(x) = \sum_{i=0}^{n1} a_i x^i \\ Q(x) = \sum_{i=0}^{m1} b_i x^i \\ P(x)\cdot Q(x) = \sum_{k=0}^{n+m1} c_kx^k = \sum_{k=0}^{n+m1}\sum_{i+j=k}a_ib_jx^k $$ For $k \ge m1$, $$ c_k = \sum_{j=0}^{m1} a_{kj}b_j $$ ...which is the dot product of $\langle a_{km+1}, a_{km+2}, \cdots, a_k \rangle$ and $\langle b_{m1}, b_{m2}, \cdots, b_0 \rangle$. It should be straightforward to solve the problem now in $\mathcal{O}((n+m) \log (n+m))$ using FFT for polynomial multiplication. answered 22 Jan, 21:57
Thanks for your explanation, but would you please elaborate third step with your solution
(22 Jan, 22:50)
Do you mean $P(x) \cdot Q(x)$? That is just the product of polynomials $P(x)$ and $Q(x)$. My solution, if it helps: 22597272.
(23 Jan, 02:26)
please try to explain mathematical part of that line.
(23 Jan, 10:26)
Try to multiply two polynoms with coefficients from one array and from reversed another and consider result coefficients. It is standart case to use FFT.
(23 Jan, 17:22)
