You are not logged in. Please login at www.codechef.com 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

5★bansal1232
2.8k1419
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.

link

answered 22 Jan, 21:57

meooow's gravatar image

6★meooow ♦
7.1k718
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 numpy.dot to get dot product of $2$ vectors.

link

answered 22 Jan, 10:15

vichitr's gravatar image

5★vichitr
2555
accept rate: 11%

edited 22 Jan, 10:17

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
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×15,680
×2,718

question asked: 22 Jan, 01:16

question was seen: 179 times

last updated: 23 Jan, 17:22