You are not logged in. Please login at to post your questions!


HELP | Editorial for Filling the Coffers: ANWCC02

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

asked 22 Jan, 01:16

bansal1232's gravatar image

accept rate: 16%

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

meooow's gravatar image

6★meooow ♦
accept rate: 48%

edited 23 Jan, 02:23

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

(22 Jan, 22:50) bansal12325★

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) bansal12325★

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) batura_dima5★

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 to get dot product of $2$ vectors.


answered 22 Jan, 10:15

vichitr's gravatar image

accept rate: 11%

edited 22 Jan, 10:17


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

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 22 Jan, 01:16

question was seen: 179 times

last updated: 23 Jan, 17:22