HELP | Editorial for Filling the Coffers: ANWCC02

editorial
,
1

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

1 Like
2

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
3

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

1 Like
4

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
5

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

6

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.

7

please try to explain mathematical part of that line.

8

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.