HELP | Editorial for Filling the Coffers: ANWCC02

Can someone share the editorial of Filling the Coffers: ANWCC02 question of CodeCharades 2019 contest.

1 Like

If there are N vaults and M keys. There are at most N-M+1 ways to get the coins.
So for each way, apply fft to get dot product of two vectors and take maximum. In python, you can use numpy.dot to get dot product of 2 vectors.

1 Like

Why do you need FFT for this method? Also, I doubt this work in time for M close to N/2.

1 Like

Assume m \le n,

P(x) = \sum_{i=0}^{n-1} a_i x^i \\ Q(x) = \sum_{i=0}^{m-1} b_i x^i \\ P(x)\cdot Q(x) = \sum_{k=0}^{n+m-1} c_kx^k = \sum_{k=0}^{n+m-1}\sum_{i+j=k}a_ib_jx^k

For k \ge m-1,

c_k = \sum_{j=0}^{m-1} a_{k-j}b_j

…which is the dot product of \langle a_{k-m+1}, a_{k-m+2}, \cdots, a_k \rangle and \langle b_{m-1}, b_{m-2}, \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.

2 Likes

Thanks for your explanation, but would you please elaborate third step with your solution

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.

please try to explain mathematical part of that line.

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.

//