×

HELP | Editorial for Filling the Coffers: ANWCC02

 1 Can someone share the editorial of Filling the Coffers: ANWCC02 question of CodeCharades 2019 contest. asked 22 Jan, 01:16 2.8k●1●4●19 accept rate: 16%

 2 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. answered 22 Jan, 21:57 6★meooow ♦ 7.1k●7●18 accept rate: 48% 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) meooow ♦6★ 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)
 1 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. answered 22 Jan, 10:15 5★vichitr 255●5 accept rate: 11% 1 Why do you need FFT for this method? Also, I doubt this work in time for M close to N/2. (22 Jan, 21:27) meooow ♦6★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,680
×2,718